这个delaunay三角测量代码如何工作？ [英] How does this code for delaunay triangulation work?

问题描述

我有这个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; 
 
公共类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]）））; 
 
返回结果; 
} 
 
 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]）; 
布尔标志; 
 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; 
} 
 
} 
 
} 
 
返回结果; 
} 
 
 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 ++; 
} 
 
返回getEdges（n，x，y，z）; 
} 
 
返回null; 
} 
} 
  

解决方案

看起来喜欢这里描述的 http://en.wikipedia.org/wiki/Delaunay_triangulation ：

在d维欧氏空间中找到一组点的Delaunay三角剖分的问题可以转换为找到凸包的问题（d + 1）维空间中的一组点，通过给每个点p一个等于| p | 2的额外坐标，取凸包的底部，并通过删除最后一个映射回到d维空间在这个例子中， d 是2。

b
$ b

向量（xn，yn，zn）是向量的叉积（点i - > ;点j）和（点i - >点k）或换句话说垂直于三角形的矢量 （点i，点j ，点k）。

计算标志检查这是否正常三角形指向负z方向，以及所有其他点是否都在与三角形法线相反的一侧（相反，因为其他点需要在三角形的平面上方，因为我们对底部感兴趣凸壳体）。如果是这种情况，三角形（i，j，k）是3D凸包的一部分，因此 x 和 y 组件（3D三角形投影到x，y平面上）是（2D）Delaunay三角剖分的一部分。

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.

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.

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;
   }
 }

解决方案

Looks like what is described here 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.

In your example d is 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).

The calculation of flag checks 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 side of the convex hull). If this is the case, the triangle (i,j,k) is part of the 3D convex hull and therefore the x and y components (the projection of the 3D triangle onto the x,y plane) is part of the (2D) Delaunay triangulation.

这篇关于这个delaunay三角测量代码如何工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！