三角剖分算法

Question

我决定创建一个简单的演示，将多边形划分为三角形集。这是我到目前为止所得到的：

给出了形成多边形边缘的顺序顶点列表（P1）（在大多数情况下多边形不是凸形）；需要一个三角形集

遍历多边形P1内的所有顶点并找到一个（v），它将满足下一个子句：

1. 从多边形中删除v并将新顶点保存到P2 之前的顶点到v 连接到其下一个表格 不穿越任何P2的线 边缘

2. v不在P2内

   如果满足这些条件，我们可以将P1替换为（P2 + triangle（prev（v），v，next（v））），然后重复此操作，直到P1包含3个以上的顶点。

   因此，问题是：该算法正确吗？如何使用最明显，最简单的方法使用C / C ++实施该算法？

Answer 1

我想你描述了耳朵剪切方法。在 http://cs.smith.edu/~Orourke/书籍/ ftp.html ;这是在C 中描述的书中描述的代码计算几何中的计算几何。

Answer 2

似乎我已经完成了该算法的实现。请验证某人。谢谢！ 通用标签

Answer 3

我还不能发表评论，所以我写了这个作为答案。

我尝试了该代码，它可以工作，但是我必须首先在下面的行中更正错误。该行位于类的 push（）函数中的 for 循环中： 通用标签

您没有传递点，而是传递了向量本身的空白元素。我将行更改为 通用标签

它奏效了。