网格简化

Question

5

我有数千个三角形连接成一个2D网格，表示水流。这个网格是Delaunay三角剖分。我需要将三角形合并成最少量的简单多边形，以使每个多边形都不允许有内部孔洞。输出的多边形应该是相同的形状。

是否有已知的算法可以完成这个任务？

- tommy chheng

你能使用 BFS 进行检查下一个三角形是否与多边形的其余部分在同一平面内吗？（如果是，则将其标记为已遍历并添加到多边形中，否则不执行任何操作）这可能会存在问题，但我暂时没有看出来。 - glebm

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tommy chheng · Answer 1

回答自己的问题 :)

我发现最好的方法是使用多边形联合方法，类似于不相交子集合并。这里有一篇关于快速实现的博客文章，利用了空间索引的优势。