我需要对一个多边形进行三角剖分，这个多边形可以是凸的，也可以是凹的，但它没有孔在其中，objective-c中是否有代码或库来完成这项工作?
在Objective-C中对凹多边形进行三角剖分的最佳方法是耳夹方法。它需要以下步骤:
1。遍历多边形中的每个顶点，并将凸点存储在数组中。-这比听起来难多了。
你需要找到最左边的点(如果有相等的x轴，取最下面的点)。
确定是顺时针还是逆时针。如果是逆时针，用double angle = atan2(c.y - b.y, c.x - b.x) - atan2(a.y - b.y, a.x - b.x)求AB和BC之间的夹角，其中B是顶点。
使用angle *= 180 / M_PI将角度从弧度转换为度数。如果角度为负，则将角度加360度。
最后，如果角度为<180度，将顶点存储在数组中。
2。查找凸点数组中每个点的耳朵
一个点被认为是一个"耳朵"，如果在由该点和相邻顶点组成的三角形内没有顶点。您将需要遍历所有点，并确定多边形中的一个点是否位于由点ABC组成的三角形中。你可以通过求第四个点的质心坐标来求。看确定点是否在三角形内。将耳朵存储在数组中。
3。对形状进行三角测量
去掉每个耳朵，在相邻点之间画一条对角线。发现任何新的凸点，并确定是否有更多的耳朵。添加任何新的耳朵到数组的末尾，并继续这个步骤，直到只剩下3个点(1个三角形)。详见http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf