What do the inputs on the function getEdges mean?

Question

I found a method to do Delaunay triangulation, but I don't quite understand what the inputs int[] x, int[] y, int[] z are.

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;
    }
    // n = Number of points
    // adjMatrix = what point is connected to what (double)

    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])));
                    result.add(new GraphEdge(new GraphPoint(x[j], y[j]), new GraphPoint(x[k], y[k])));
                    result.add(new GraphEdge(new GraphPoint(x[k], y[k]), new GraphPoint(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;
    }
}

Micromega · Accepted Answer · 2016-08-09T12:10:21.930

1

Like in your comment it transform the problem and lifts the points to a paraboloid then takes the bottom convex hull and project it back to 2d by omitting the third co-ordinate.

edited Aug 09 '16 at 12:10

answered Aug 09 '16 at 12:01

Micromega

12,486
7
35
72

Too add to this and directly answer the question, x[] and y[] are the x y coords for the points, and z is x^2 + y^2 – doominabox1 Aug 10 '16 at 15:30
Thank you! I also want to add this. Finding the convex hull of a 3d object seems to be very complicated:http://stackoverflow.com/questions/18416861/how-to-find-convex-hull-in-a-3-dimensional-space – Micromega Aug 10 '16 at 16:10
1

This code seems to be somewhere in the order of n^3 time wise, know of a better way to do triangulation? – doominabox1 Aug 11 '16 at 03:24
IMO it's O(n log n): https://books.google.fr/books?id=duT2fcnQeJMC&pg=PA227&lpg=PA227&dq=time+complexity+of+delaunay+triangulation&source=bl&ots=vl5FasABtn#v=onepage&q=time%20complexity%20of%20delaunay%20triangulation&f=false. There is a O(n) algorithm https://web.cs.wpi.edu/~matt/courses/cs563/talks/triang.html – Micromega Aug 11 '16 at 14:58

What do the inputs on the function getEdges mean?

1 Answers1