构造多边形的轮廓（尤其是三角剖分）

Question

[我将如何构造仅由三角形组成的2d多边形的轮廓，它可以具有孔，并且外部轮廓可以是凹凸的，而孔也可以是凹凸的。

从I'm reading over here看来，这恰恰是三角剖分问题的反面。您知道有关此类问题的文章吗？

八叉树/四叉树与此有关吗？

Answer 1

我想您具有以三个点为一组的数据形式，这些数据构成一个“实心”三角形，这些三角形沿边邻接，并且将成为完整形状的角的所有顶点也是所有顶点的顶点触及这一点的三角形。然后，您只需要查找所有未加倍的边缘，即不属于两个相邻的三角形。

Answer 2

我认为您可以通过创建表示三角形集合的拓扑数据结构，然后使用该结构在边界上的三角形边缘上依次迭代来解决您的问题。

Answer 3

这里是在三角形网格上运行的实现，如this answer中所述，找到并连接所有非双精度边。