我需要对可能是凸面或凹面的多边形进行三角剖分，但其中没有孔，是否有用于 Objective-c 的代码或库来完成这项工作？
问问题
919 次
1 回答
1
在 Objective-C 中对凹多边形进行三角剖分的最佳方法是剪耳法。它需要以下步骤：
1. 遍历多边形中的每个顶点并将凸点存储在一个数组中 ——这比听起来要难。
您将需要找到最左边的点（如果 x 坐标相等，则取最底点）。
确定要顺时针还是逆时针。如果逆时针方向，则使用double angle = atan2(c.y - b.y, c.x - b.x) - atan2(a.y - b.y, a.x - b.x)其中 B 为顶点找到 AB 和 BC 之间的角度。
使用 将角度从弧度转换为度数angle *= 180 / M_PI。如果角度为负，则将角度增加 360 度。
最后，如果角度 < 180 度，则将顶点存储在数组中。
2. 在你的凸点数组中找到每个点的耳朵
如果点和相邻顶点形成的三角形内没有顶点，则该点被认为是“耳朵”。您将需要遍历所有点并确定多边形中的一个点是否位于由点 ABC 形成的三角形中。您可以通过找到第四个点的重心坐标来做到这一点。查看确定点是否在三角形内。将耳朵存储在一个数组中。
3.三角化形状
取下每只耳朵并在相邻点之间画一条对角线。发现任何新的凸点并确定是否有更多的耳朵。将任何新耳朵添加到阵列的末尾并继续此步骤，直到只剩下 3 个点（1 个三角形）。有关详细信息，请参阅http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
于 2015-07-02T11:39:30.613 回答