假设我有一组点，它们之间有线/边。所有这些边都在我的点的凸包中创建了不重叠的三角形。所有点都连接到三角形。
如何有效地检查哪些点是哪个三角形的一部分？我可以检查每条边的入射点，并逐渐构建一个三重点，但这听起来非常慢（o（n^2）？）。有没有像线绳之类的东西可以做到这一点？
欢呼。
如果你有一个像你描述的那样的二维设置，那么你就有一个完全三角化的平面图（当你排除端点时没有相交的边），它跨越了你的点的凸包。在这种情况下，如果根据边与顶点的角度对每个顶点周围的边进行圆形排序，那么可以肯定的是，每对相邻边都会形成一个三角形。此外，如果对每个顶点执行此过程，每个三角形都可以通过这种方式找到。当您在所有顶点上迭代时，每个三角形将被找到3次。您可以使用哈希表来检测重复项，也可以在识别重复项时对所有三角形进行排序。如果使用哈希表，则如果有V个顶点，则总体复杂度为O（V log d），其中d是顶点的最大阶数（因为边的总数在顶点数中是线性的，因为有平面图）。因此，绝对最坏情况是O（V log V），如果对所有三角形进行排序以找到重复的三角形，这也是最坏情况（因为三角形的最大数量在顶点数量上也是线性的）。唯一需要注意的是，您需要知道每个顶点的相邻顶点（即附带边）。
边定义了一个无向图G，三角形是G和length=3中的循环集。
几何三角测量通常具有相对较低的节点度（度d是与每个节点相邻的边的数量，d<=10是几何三角测量的典型值），因此，这里有一种相当有效的O(n*d^3)算法，可用于构造三角形集。
-
设置类似图形的数据结构，支持访问每个节点附近的边列表。
-
在所有节点上迭代。考虑与给定节点
i相邻的所有边对。对于与i相邻的一对给定边，我们有一个潜在的节点三元组i,j,k。如果存在连接节点j,k的边，则该三元组是三角形，可以通过扫描j,k的边列表来检查。
(2)的天真实现将生成重复的三角形。维护三角形的哈希表，以在考虑重复的三元组时拒绝它们。
我假设边定义了一个有效的不相交三角测量，是不相交的，等等。
希望这能有所帮助。