问题标签 [triangulation]

试图三角化一组简单的 2d 多边形，我想出了这个算法：

• 1）对于多边形中的每个顶点，计算两个链接边之间的角度
• 2）通过减少相对于多边形内部的角度对顶点进行排序
• 3）如果集合中的顶点少于3个，我们就完成了
• 4) 取集合中的最后一个顶点，输出由它和它的两个邻居组成的三角形
• 5）从集合中移除顶点
• 6）更新两个邻居的角度
• 7) 跳转到 2

我已经对其进行了测试，发现它甚至可以在非常大且复杂的简单二维多边形上工作（它不适用于带有孔的多边形或自相交的多边形）。

是否存在会产生退化结果的极端情况？

这个算法是已知的吗？

如果不是，我想确定这个算法是坚如磐石的，但我没有数学背景来证明它。

非常感谢。

我正在尝试计算从 AP（接入点）到 iPhone 的粗略距离。几个常数：

1）我已经解决了寻找和确定附近AP信号强度的问题（必须使用私有API，不用担心这不会在App Store中出现）

2) 所有 AP 的品牌和型号相同

现在给定一个 APs RSSI，我怎样才能得到一个粗略的距离？

示例：RSSI 为 -60，我还需要什么其他信息才能达到一定距离？

谢谢！

我已经应用了 GPS，它给了我当前位置的纬度和经度，但问题是在某些特定区域 GPS 不提供位置。任何人都可以建议我基于细胞信号或wifi信号的三角测量技术教程。

给定三角形 T的顶点V1 (x1,y1,z1)，如果我知道它位于三角形 Tp 的投影范围内，我必须通过它的 x,y 坐标找到一个点的 z 坐标。V2 (x2,y2,z2)V3 (x3,y3,z3)(x,y)(x1,y1), (x2,y2), (x3,y3)

实际上，3D 中的三角形平面由方程定义：Ax+By+Cz+D=0，我可以发现z = (D-Ax-By)/C 问题是 A、B、C、D 太昂贵而无法在运行时计算：

是否可以使用opengl着色器计算A、B、C、D？是否有优化算法来查找平面系数？

我有这个Java代码，输入中的一组Point返回一组代表Delaunay三角剖分的图形边缘。

我想知道使用了什么策略来做到这一点，如果存在的话，使用的算法的名称。

在这段代码中，GraphEdge 包含两个 awt Point 并表示三角剖分中的一条边，GraphPoint 扩展了 Awt Point，最终三角剖分的边在 TreeSet 对象中返回。

我的目的是了解此方法的工作原理：

在此三角测量的完整源代码下方：

I'm in need of help solving an issue, the problem came up doing one of my small robot experiments, the basic idea, is that each little robot has the ability to approximate the distance, from themselves to an object, however the approximate I'm getting is way too rough, and I'm hoping to calculate something more accurate.

So:
Input: A list of vertex (v_1, v_2, ... v_n), a vertex v_* (robots)
Output: The coordinates for the unknown vertex v_* (object)

Each vertex v_1 to v_n's coordinates are well known (supplied by calling getX() and getY() on the vertex), and its possible to get the approximate range to v_* by calling; getApproximateDistance(v_*), function getApproximateDistance() returns two variables variables, that is; minDistance and maxDistance. - The actual distance lies in between these.

So what I've been trying to do to obtain the coordinates for v_*, is to use trilateration, however I can't seem to find a formula for doing trilateration with limits (lower and upperbound), so that's really what I'm looking for (not really good enough at math, to figure it out myself).

Note: is triangulation the way to go instead?
Note: I would possibly love to know a way to do, performance/accuracy trade-offs.

An example of data:

Picture to show data: http://img52.imageshack.us/img52/6414/unavngivetcb.png

It's obvious that the approximate for v_1 can be better, than [0.5; 1], as the figure that the above data creates is small cut of a annulus (limited by v_3), however how would I calculate that, and possibly find the approximate within that figure (this figure is possibly concave)?

Would this be better suited for MathOverflow?

我们正在尝试在无头的 GNU/linux 服务器上使用 GLU 的曲面细分功能。我们想为此使用 PyOpenGL，但问题是它在调用 gluNewTess 时崩溃（分段错误）

gdb backtrace 说它在 glGetError 中，这让我认为 GLU tesselation 需要 GL 上下文？或者它只是 PyOpenGL 中的一些错综复杂的东西？

我试图找到一些关于如何在无头（和虚拟化）机器上初始化 GL 上下文的信息，但没有运气。感谢您提供有关这些主题的任何信息。

我决定创建一个简单的演示，将多边形划分为三角形集。这是我到目前为止所得到的：

给定一个顺序顶点列表（P1）形成多边形边（多边形在大多数情况下不是凸的）；需要一个三角形集

遍历多边形 P1 内的所有顶点并找到一个 (v)，它将满足下一个子句：

1. 从多边形中删除 v 并将新的 v 保存到 P2前一个顶点到 v 连接到它的下一个形成一条不跨越任何 P2 边的线

2. v 不在 P2 内

如果满足这些，我们可以将 P1 替换为 (P2 + triangle( prev(v), v, next(v)) ) 并重复此操作，直到 P1 包含超过 3 个顶点。

所以，问题是：这个算法是否正确，以及如何使用 C/C++ 以最明显和最简单的方式实现它？

在使用 GNU Triangulated Surface Library 进行约束 Delaunay 三角剖分时，我遇到了一些间歇性断言失败。我在不同的时间看到了以下每一个：

Gts:ERROR:cdt.c:974:remove_intersected_vertex: 代码不应该到达 Gts:ERROR:cdt.c:896:remove_intersected_edge: 断言失败: (下一个) Gts:ERROR:cdt.c:887:remove_intersected_edge: 断言失败: （o2 == 0。）

我查看了 cdt.c，但我所能弄清楚的是它们来自对 gts_delaunay_add_constraint 的调用。

有人可以解释约束可能有什么问题，这会导致这些断言失败吗？

当我尝试对一组随机顶点进行三角剖分时，会发生断言失败。不幸的是，它只发生在大量顶点和约束的情况下，因此很难找出失败输入的模式。使用 GTS 的代码即使输入错误也不会崩溃，因此最好防止这些断言失败，否则我将不得不禁用断言。

编辑：尝试删除所有相交约束（存储在edges）：

仍然得到相同的断言失败。

给定一个点集（即一个 3XN 顶点数组），我如何使用 matlab 对其进行三角测量？假设点集确实代表了对象的某个表面，并且不包含任何噪声。

编辑：选择的答案提供了一种创建网格四面体的方法。我在寻找三角测量；对于我的凸形状的具体情况，凸包（convhulln按照答案评论中的建议使用）就足够了。