最小化和简化 2D 三角形网格

Question

目标：
我有一个 2D 表面上的许多三角形的列表，表示为

std::vector<QPolygonF>

。我想将此列表转换为另一个具有相同轮廓但没有三角形重叠的三角形列表。换句话说，我想合并重叠的三角形：

问题：
这个过程有名字吗？使用 Qt 做到这一点的最佳方法是什么？如果 Qt 本身不支持，是否有一个众所周知的算法可以实现？

Answer 1

我会使用诸如this之类的算法来查找线条相交的位置。如果两个交点也有一个共享顶点，则您已经创建了一个三角形。您还需要跟踪每个三角形覆盖的区域。看来你想保留最大的三角形。如果一个大三角形完全覆盖了一个较小的三角形，则可以删除较小的三角形。我在你的图表中看到的唯一问题是你在第二次转换中通过随机选择使用右下三角形的顶点创建的最小矩形（与musicamante一致）。如果您使用随机顶点来创建新三角形，为什么不从所有暴露的顶点中围绕图的周边形成每个可能的三角形？如果你想使用一种算法，你需要对其用法保持一致。

我认为这不一定是编程问题，更多的是算法问题。也许先用Python解决它，然后用C++/qt实现？