这个delaunay三角测量代码如何工作？
我有这个Java代码，它带有一组Point in输入，返回一组代表Delaunay三角剖分的图形边缘。
我想知道用于执行此操作的策略（如果存在），使用的算法名称。
在此代码中，GraphEdge包含两个awt Point并表示三角剖分中的边，GraphPoint扩展Awt Point，并在TreeSet对象中返回最终三角剖分的边。
我的目的是了解这种方法的工作原理：
public TreeSet getEdges(int n, int[] x, int[] y, int[] z) 在这个三角测量的完整源代码下面：
import java.awt.Point; import java.util.Iterator; import java.util.TreeSet; public class DelaunayTriangulation { int[][] adjMatrix; DelaunayTriangulation(int size) { this.adjMatrix = new int[size][size]; } public int[][] getAdj() { return this.adjMatrix; } public TreeSet getEdges(int n, int[] x, int[] y, int[] z) { TreeSet result = new TreeSet(); if (n == 2) { this.adjMatrix[0][1] = 1; this.adjMatrix[1][0] = 1; result.add(new GraphEdge(new GraphPoint(x[0], y[0]), new GraphPoint(x[1], y[1]))); return result; } for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n; j++) { for (int k = i + 1; k < n; k++) { if (j == k) { continue; } int xn = (y[j] - y[i]) * (z[k] - z[i]) - (y[k] - y[i]) * (z[j] - z[i]); int yn = (x[k] - x[i]) * (z[j] - z[i]) - (x[j] - x[i]) * (z[k] - z[i]); int zn = (x[j] - x[i]) * (y[k] - y[i]) - (x[k] - x[i]) * (y[j] - y[i]); boolean flag; if (flag = (zn < 0 ? 1 : 0) != 0) { for (int m = 0; m < n; m++) { flag = (flag) && ((x[m] - x[i]) * xn + (y[m] - y[i]) * yn + (z[m] - z[i]) * zn 0)) { int n = pointsSet.size(); int[] x = new int[n]; int[] y = new int[n]; int[] z = new int[n]; int i = 0; Iterator iterator = pointsSet.iterator(); while (iterator.hasNext()) { Point point = (Point)iterator.next(); x[i] = (int)point.getX(); y[i] = (int)point.getY(); z[i] = (x[i] * x[i] + y[i] * y[i]); i++; } return getEdges(n, x, y, z); } return null; } }
看起来像这里描述的http://en.wikipedia.org/wiki/Delaunay_triangulation ：
在d维欧氏空间中找到一组点的Delaunay三角剖分的问题可以转换为在（d + 1）维空间中找到一组点的凸包的问题，通过给出每个点p an额外坐标等于| p | 2，取凸包的底边，并通过删除最后一个坐标映射回d维空间。
在你的例子中， d是2。
向量(xn,yn,zn)是向量的交叉积(point i -> point j)和(point i -> point k)或换句话说垂直于三角形的向量(point i, point j, point k) 。
flag的计算检查该三角形的法线是否指向负z方向，以及所有其他点是否都在与三角形法线相反的一侧（相反，因为其他点需要在三角形的平面上方，因为我们是感兴趣的是凸包的底部 ）。 如果是这种情况，三角形(i,j,k)是3D凸包的一部分，因此x和y分量（3D三角形在x，y平面上的投影）是（2D）的一部分Delaunay三角剖分。