Delaunay.java

/*************************************************************************
 *  Compilation:  javac Delaunay.java
 *  Execution:    java Delaunay
 *  Dependencies: InteractiveDraw.java DrawListener.java Draw.java
 * 
 *  Plots the points that the user clicks, and draws the
 *  Delaunay triangulation. 
 *
 *  Limitations
 *  -----------
 *   - this algorithm takes N^4 time in worst case and N^3 in best case
 *     (possible to improve Delaunay triangulation to N log N)
 *   - assumes no degeneracies (e.g., no 4 points are cocircular)
 *   - at most 1000 points
 *
 *************************************************************************/

import java.awt.Color;

public class Delaunay implements DrawListener {
    private int SIZE = 512;
    private int MAXN = 1000;                    // maximum number of points
    private int N = 0;                          // number of points
    private Point[] points = new Point[MAXN];   // user-selected points
    private InteractiveDraw d;                  // the drawing GUI

    // create an empty Delaunay triangulation GUI
    public Delaunay() {
        d = new InteractiveDraw(SIZE, SIZE);
        d.setScale(0, 0, SIZE, SIZE);
        d.addListener(this);
        d.show();
    }

    // callback when the user clicks at (x, y)
    public void mousePressed(double x, double y) {
        points[N++] = new Point(x, y);
        d.clear(Color.lightGray);
        d.setColor(Color.black);
        for (int i = 0; i < N; i++) points[i].draw(d);
        d.setColor(Color.blue);


        // determine if i-j-k is a circle with no interior points 
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                for (int k = j+1; k < N; k++) {
                    boolean isTriangle = true;
                    for (int a = 0; a < N; a++) {
                        if (a == i || a == j || a == k) continue;
                        if (points[a].inside(points[i], points[j], points[k])) {
                           isTriangle = false;
                           break;
                        }
                    }
                    if (isTriangle) {
                        points[i].drawTo(points[j], d);
                        points[i].drawTo(points[k], d);
                        points[j].drawTo(points[k], d);
                    }
                }
            }
        }

        d.show();
    }

    // other callbacks
    public void keyTyped(char c) { d.save("delaunay" + c + ".png"); }
    public void mouseDragged(double x, double y) { }
    public void mouseReleased(double x, double y) { }


    // test client
    public static void main(String args[]) {
        Delaunay delaunay = new Delaunay();
    }
   
}