5

我正在使用 Unity，但解决方案应该是通用的。我将通过鼠标点击获得用户输入，它定义了一个封闭的不规则多边形的顶点列表。这些顶点将定义平面 3D 网格的外边缘。

要在 Unity 中以程序方式生成网格，我必须指定所有顶点以及它们如何连接以形成三角形。

因此，对于凸多边形来说，这很简单，我只需制作具有顶点 1、2、3 和 1、3、4 等的三角形，形成类似孔雀尾巴的东西。

但是对于凹多边形来说，它并不是那么简单。有没有找到内部三角形的有效算法？

4

3 回答 3

6

您可以使用受约束的Delaunay 三角剖分（实现起来并非易事！）。Triangle和CGAL中提供了良好的库实现，提供了高效的O(n*log(n))实现。

如果顶点集很小，剪耳算法也是一种可能，尽管它不一定会给你一个 Delaunay 三角剖分（它通常会产生次优三角形）并在O(n^2). 不过，实现自己很容易。

由于输入顶点存在于 3d 空间中的平面上，因此您可以通过投影到平面上，计算 2d 中的三角剖分，然后将相同的网格拓扑应用于 3d 顶点集来获得 2d 问题。

于 2012-11-13T22:14:06.153 回答
2

我已经实现了如下的剪耳算法：

  1. 遍历顶点，直到找到凸顶点 v
  2. 检查多边形上的任何点是否位于三角形 (v-1,v,v+1) 内。如果有，则需要沿顶点 v 以及离线最远的点 (v-1, v+1) 划分多边形。递归地评估两个分区。
  3. 如果顶点 v 周围的三角形不包含其他顶点，则将三角形添加到输出列表并删除顶点 v，重复直到完成。

笔记：

  1. 即使在处理 3D 面时，这本质上也是 2D 操作。要考虑 2D 中的问题，只需忽略绝对值最大的人脸法线的矢量坐标。（这就是您将 3D 面“投影”到 2D 坐标中的方式）。例如，如果面具有法线 (0,1,0)，您将忽略 y 坐标并在 x,z 平面中工作。
  2. 要确定哪些顶点是凸的，首先需要知道多边形的缠绕。您可以通过找到多边形中最左边的（最小的 x 坐标）顶点来确定这一点（通过找到最小的 y 来打破平局）。这样的顶点总是凸的，所以这个顶点的缠绕给你多边形的缠绕。
  3. 您可以使用有符号三角形面积方程确定绕组和/或凸度。请参阅：http ://softsurfer.com/Archive/algorithm_0101/algorithm_0101.htm 。根据多边形的缠绕，所有凸三角形都具有正面积（逆时针缠绕）或负面积（顺时针缠绕）。
  4. 三角形中的点公式由有符号三角形面积公式构成。请参阅：如何确定一个点是否在二维三角形中？.
  5. 在需要确定哪个顶点 (v) 离直线最远的第 2 步中，您可以通过形成三角形 (L0, v, L1) 并检查哪个具有最大面积（绝对值，除非您'假设一个特定的缠绕方向）
  6. 该算法对于自相交多边形没有很好的定义，并且由于浮点精度的性质，您可能会遇到这种情况。可以为稳定性实施一些保护措施： - 一个点不应被视为在您的三角形内，除非它是一个凹点。（这种情况表明自相交，你不应该沿着这个顶点划分你的集合）。您可能会遇到分区完全凹入的情况（即它的缠绕方式与原始多边形的缠绕方式不同）。这个分区应该被丢弃。
  7. 由于该算法是循环的并且涉及对集合进行分区，因此使用带有数组进行存储的双向链表结构非常有效。然后，您可以将集合划分为 0(1)，但是该算法仍然具有平均 O(n^2) 运行时间。最佳案例运行时间实际上是需要多次分区的集合，因为这会迅速减少比较次数。
于 2012-11-15T10:42:12.870 回答
1

有一个用于对凹多边形进行三角剖分的社区脚本，但我没有亲自使用它。作者声称它适用于 3D 点和 2D。

如果我想将问题限制在 2D 上，我过去使用过的一种技巧是使用主成分分析来找到 3D 数据中变化最大的 2 个轴，并将它们设为我的“X”和“Y”。

于 2012-11-14T14:54:45.463 回答