java - How does this code for delaunay triangulation work? -

i have java code set of point in input return set of graph's edge represent delaunay triangulation.

i know strategy used this, if exist, name of algorithm used.

in code graphedge contains 2 awt point , represent edge in triangulation, graphpoint extends awt point, , edges of final triangulation returned in treeset object.

my purpose understand how method works:

public treeset getedges(int n, int[] x, int[] y, int[] z) 

below complete source code of 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;      }       (int = 0; < n - 2; i++) {        (int j = + 1; j < n; j++) {          (int k = + 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) {              (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 = 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 described here http://en.wikipedia.org/wiki/delaunay_triangulation :

the problem of finding delaunay triangulation of set of points in d-dimensional euclidean space can converted problem of finding convex hull of set of points in (d + 1)-dimensional space, giving each point p coordinate equal |p|2, taking bottom side of convex hull, , mapping d-dimensional space deleting last coordinate.

in example d 2.

the vector (xn,yn,zn) cross product of vectors (point -> point j) , (point -> point k) or in other words vector perpendicular triangle (point i, point j, point k).

the calculation of flag checks whether normal of triangle points towards negative z direction , whether other points on side opposite normal of triangle (opposite because other points need above triangle's plane because we're interested in bottom side of convex hull). if case, triangle (i,j,k) part of 3d convex hull , therefore x , y components (the projection of 3d triangle onto x,y plane) part of (2d) delaunay triangulation.