algorithm - 从边/线构造三角形的有效方法？

Question

假设我有一组点，它们之间有线/边。所有这些边都在我的点的凸包内创建了不重叠的三角形。所有点都连接到三角形。

如何有效地检查哪些点属于哪个三角形？我可以检查每条边的入射点并逐渐构建三元组点，但这听起来非常慢 (o(n^2)?)。是否有像 linesweep 之类的东西可以做到这一点？

干杯。

Answer 1

如果你有一个像你描述的二维设置，那么你有一个完全三角化的平面图(当你排除端点时没有相交的边缘)跨越你的点的凸包。在这种情况下，如果您根据每个顶点与顶点形成的角度对每个顶点周围的边进行循环排序，那么您肯定知道每对相邻边构成一个三角形。此外，如果对每个顶点执行此过程，则可以通过这种方式找到每个三角形。当您遍历所有顶点时，每个三角形将被找到 3 次。您可以使用哈希表来检测重复项，或者在完成识别重复项后对所有三角形进行排序。如果您使用哈希表，那么如果您有 V 个顶点，则总体复杂度为 O(V log d)，其中 d 是顶点的最大度数(因为边的总数与顶点数成线性关系，因为您有一个平面图)。所以绝对最坏的情况是 O(V log V)，如果你对所有三角形进行排序以查找重复项，这也是最坏的情况(因为三角形的最大数量也与顶点数量成线性关系)。唯一需要注意的是，您需要知道每个顶点的相邻顶点(即附带边)。