从一组线中找到所有三角形（Delaunay 图）

Question

我在处理过程中使用网格库来创建基于点数组的三角形网格。我的问题是这个库只能 return 一组构成三角形的线，而不是三角形本身。有谁知道如何得到所有的三角形？

and here's a picture for refrence

Answer 1

好问题。首先，解决方案是采用可以为您提供所需格式结果的库。你需要 Delaunay 三角剖分不是 Delaunay 图，这个库提供的。

从提供的结果库中获取三角形是可能的，非常简单。如果内图点有 n 边（getLinked() 方法），而不是 n 三角形的一部分。三角形的其他边计算为按角度对边进行排序。如果点在外部（在凸包上）则一对边之间的角度更大超过 180 度并且在那对三角形上不存在。

算法是这样的：

for each point p1:
  neighbours = delaunay.getLinked(p1)
  sort neighbours by angle to point p1
  for i=0 to size(neighbours)
    p2 = neighbours[i]
    p3 = neighbours[(i+1) % size(neighbours)]
    if (angle(p3, p1) - angle(p2, p1)) % 360deg > 180deg:
      continue  # Outer triangle
    if p2 > p1 and p3 > p1:
      continue  # Already processed
    print result triangle (p1, p2, p3)

检查(p2, p3 > p1)是去掉相同的三角形，因为每个三角形都生成三次。

从一组线中找到所有三角形（Delaunay 图）

finding all triangles from an array of lines (Delaunay diagram)

arrays

grid

processing

mesh

delaunay