shy*_*cha 2 c algorithm math triangulation computational-geometry
我决定创建一个简单的演示,将多边形划分为三角形集.到目前为止我得到的是:
给出顺序顶点列表(P1)形成多边形边缘(多边形在多数情况下不是凸面); 需要一个三角形集
遍历多边形P1内的所有顶点并找到一个(v),这将满足下一个子句:
从多边形中移除v并将新的一个保存到P2前一个顶点到v连接到它的下一个顶点,形成一条不穿过任何P2边的线
v不在P2内
如果满足这些,我们可以用(P2 + 三角形(prev(v),v,next(v))替换P1 并重复此动作,直到P1包含多于3个顶点.
所以,问题是:这个算法是否正确以及如何使用C/C++以最明显和最简单的方式实现它？