9

私はこの Java コードを持っています。この Java コードは、一連の Point in input を使用して、Delaunay 三角形分割を表す一連のグラフのエッジを返します。

これを行うためにどのような戦略が使用されたか、存在する場合は使用されたアルゴリズムの名前を知りたいです。

このコードでは、GraphEdge は 2 つの 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);
             }

           }

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

1 に答える 1

8

ここで説明されているように見えますhttp://en.wikipedia.org/wiki/Delaunay_triangulation：

d次元ユークリッド空間で点のセットのドロネー三角形分割を見つける問題は、各点pを与えることにより、（d + 1）次元空間で点のセットの凸包を見つける問題に変換できます。 | 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凸包の一部であるため、xandyコンポーネント（3D三角形のx、y平面への投影）は（2D）ドロネー三角形分割の一部です。

于 2011-04-28T21:23:41.043 に答える