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

Question

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

如何有效地检查哪些点属于哪个三角形？我可以检查每个边缘的事件点并逐渐构建三个点，但这听起来非常慢（o（n ^ 2）？）。有没有像 lineweep 这样的东西来做到这一点？

干杯。

Answer 1

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

Answer 2

边定义了一个无向图G，三角形是其中的一组G循环length=3。

几何三角剖分通常具有相对较低的节点度数（度数d是与每个节点相邻的边的数量，d<=10对于几何三角剖分来说是典型的），因此，这是一种O(n*d^3)可用于构造三角形集的相当有效的算法。

1. 设置一个类似图的数据结构，支持访问与每个节点相邻的边列表。

2. 遍历所有节点。考虑与给定节点相邻的所有边对i。对于与 相邻的给定边对i，我们有一个潜在的节点三元组i,j,k。如果有一条边连接节点j,k，这个三元组就是一个三角形，可以通过扫描 的边列表来检查j,k。

重复的三角形将由(2). 维护一个三角形哈希表，以拒绝考虑重复的三元组。

我假设边缘定义了一个有效的不相交三角剖分，不相交等。

希望这可以帮助。