找到线阵列中的所有三角形（Delaunay图）

Question

即时使用Mesh库处理以创建基于点阵列的三角形网格。 我的问题是，这个库只能返回组成三角形的线条而不是三角形本身。 没有人知道如何获得所有的三角形？

库是在这里：http://leebyron.com/mesh/

and here's a picture for refrence

Answer 1

好问题。首先，解决方案是采取可以给你想要的格式的图书馆。你需要 Delaunay三角剖分而不是Delaunay图，这个库提供了什么。

可以从结果库中获取三角形提供很简单。如果内部图示点具有边缘（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）是去除相同trinagles，由于每个三角形产生三次。