java delaunay 三角剖分的这段代码是如何工作的？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5825089/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How does this code for delaunay triangulation work?
提问by tulkas85
I have this Java code that with a set of Point in input return a set of graph's edge that represent a Delaunay triangulation.
我有这个 Java 代码，输入中的一组 Point 返回一组表示 Delaunay 三角剖分的图的边。
I would like to know what strategy was used to do this, if exist, the name of algorithm used.
我想知道使用什么策略来做到这一点，如果存在，使用的算法名称。
In this code GraphEdge contains two awt Point and represent an edge in the triangulation, GraphPoint extends Awt Point, and the edges of final triangulation are returned in a TreeSet object.
这段代码中GraphEdge包含两个awt Point，代表三角剖分中的一条边，GraphPoint扩展了Awt Point，最终三角剖分的边在一个TreeSet对象中返回。
My purpose is to understand how this method works:
我的目的是了解这种方法是如何工作的：
public TreeSet getEdges(int n, int[] x, int[] y, int[] z)
below the complete source code of this triangulation :
在此三角剖分的完整源代码下方：
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);
}
}
if (!flag)
{
continue;
}
result.add(new GraphEdge(new GraphPoint(x[i], y[i]), new GraphPoint(x[j], y[j])));
//System.out.println("----------");
//System.out.println(x[i]+" "+ y[i] +"----"+x[j]+" "+y[j]);
result.add(new GraphEdge(new GraphPoint(x[j], y[j]), new GraphPoint(x[k], y[k])));
//System.out.println(x[j]+" "+ y[j] +"----"+x[k]+" "+y[k]);
result.add(new GraphEdge(new GraphPoint(x[k], y[k]), new GraphPoint(x[i], y[i])));
//System.out.println(x[k]+" "+ y[k] +"----"+x[i]+" "+y[i]);
this.adjMatrix[i][j] = 1;
this.adjMatrix[j][i] = 1;
this.adjMatrix[k][i] = 1;
this.adjMatrix[i][k] = 1;
this.adjMatrix[j][k] = 1;
this.adjMatrix[k][j] = 1;
}
}
}
return result;
}
public TreeSet getEdges(TreeSet pointsSet)
{
if ((pointsSet != null) && (pointsSet.size() > 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;
}
}
回答by Andre Holzner
Looks like what is described here http://en.wikipedia.org/wiki/Delaunay_triangulation:
看起来像这里描述的内容http://en.wikipedia.org/wiki/Delaunay_triangulation：
The problem of finding the Delaunay triangulation of a set of points in d-dimensional Euclidean space can be converted to the problem of finding the convex hull of a set of points in (d + 1)-dimensional space, by giving each point p an extra coordinate equal to |p|2, taking the bottom side of the convex hull, and mapping back to d-dimensional space by deleting the last coordinate.
通过给每个点 p额外坐标等于|p|2，取凸包的底边，并通过删除最后一个坐标映射回d维空间。
In your example dis 2.
在你的例子中d是 2。
The vector (xn,yn,zn)is the cross product of the vectors (point i -> point j)and (point i -> point k)or in other words a vector perpendicular to the triangle (point i, point j, point k).
向量(xn,yn,zn)是向量的叉积(point i -> point j)和(point i -> point k)一个矢量垂直于所述三角形或者换句话说(point i, point j, point k)。
The calculation of flagchecks whether the normal of this triangle points towards the negative z direction and whether all other points are on the side opposite to the normal of the triangle (opposite because the other points need to be above the triangle's plane because we're interested in the bottom sideof the convex hull). If this is the case, the triangle (i,j,k)is part of the 3D convex hull and therefore the xand ycomponents (the projection of the 3D triangle onto the x,y plane) is part of the (2D) Delaunay triangulation.
的计算flag检查这个三角形的法线是否指向负 z 方向，以及所有其他点是否在三角形法线的对面（相反，因为其他点需要在三角形平面上方，因为我们感兴趣在凸包的底部）。如果是这种情况，则三角形(i,j,k)是 3D 凸包的一部分，因此x和y分量（3D 三角形在 x,y 平面上的投影）是 (2D) Delaunay 三角剖分的一部分。
