给定一个不规则多边形的顶点列表，如何创建内部三角形来高效地构建平面3D网格？

Question

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

为了按程序生成统一的网格，我必须指定所有顶点以及它们如何连接以形成三角形。

所以，对于凸多边形来说，这很简单，我只需要制作顶点为1,2,3，然后是1,3,4的三角形，形成类似孔雀尾巴的形状。

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

Answer 1

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

如果我想把问题限制在二维，我过去使用过的一个技巧是使用主成分分析来找到我的三维数据中变化最大的两个轴，并使它们成为我的“X”和“Y”。

Answer 2

我实现了如下的削耳算法：

1. 在顶点上迭代，直到找到凸顶点v
2. 检查多边形上的任何点是否位于三角形（v-1，v，v 1）内。如果有，则需要沿顶点v和距离直线最远的点（v-1，V1）分割多边形。递归地计算两个分区
3. 如果围绕顶点v的三角形不包含其他顶点，请将该三角形添加到输出列表中，并删除顶点v，重复此操作直到完成

注意事项：

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

Answer 3

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

如果顶点集很小，也可以使用耳朵裁剪算法，尽管它不一定会给出Delaunay三角剖分（通常会生成次优三角形），并且运行在O（n^2）中。不过，自己实现是相当容易的。

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