A concave polygon to triangles.

Poly.java

import java.io.*;
import java.util.*;
import java.util.List;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class Poly extends JPanel {

	public static void main(String[] args) {
		JFrame frame = new JFrame();
		frame.getContentPane().add(new Poly());
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.setBounds(100, 100, 640, 480);
		frame.setTitle("Polygon to trinagles");
		frame.setVisible(true);
	}

	private ArrayList<Point> vertices = new ArrayList<>();
	private ArrayList<Triangle> triangles;
	
	public Poly() {
		super();
		addMouseListener(new MouseAdapter() {
			@Override
			public void mousePressed(MouseEvent e) {
				if (triangles == null) {
					vertices.add(new Point(e.getX(), e.getY()));
					repaint();
				}
			}
		});
		
		setLayout(new FlowLayout(FlowLayout.CENTER));
		
		JButton clearBtn = new JButton("Reset");
		JButton  playBtn = new JButton("Run");
		JButton  saveBtn = new JButton("Save");
		JButton  loadBtn = new JButton("Load");

		clearBtn.addActionListener(new ActionListener() {
			@Override
			public void actionPerformed(ActionEvent e) { clear(); }
		});

		playBtn.addActionListener(new ActionListener() {
			@Override
			public void actionPerformed(ActionEvent e) {
				if(vertices.size() < 3) {
					return;
				}
				repaint();
				triangles = new ArrayList<Triangle>();
				long start = System.nanoTime();
				polygonToTriangles(vertices, triangles);
				System.err.println("Elapsed time:"+ (System.nanoTime() - start));
				System.err.println("number of triangles:"+ triangles.size());
			}
		});
		
		saveBtn.addActionListener(new ActionListener() {
			@Override
			public void actionPerformed(ActionEvent e) {
				try (ObjectOutputStream out =
						new ObjectOutputStream(new FileOutputStream("poly.bin"))) {
					out.writeObject(vertices);
				} catch(IOException ex) {
					ex.printStackTrace();
				}
			}
		});
		
		loadBtn.addActionListener(new ActionListener() {
			@Override
			public void actionPerformed(ActionEvent e) {
				clear();
				try (ObjectInputStream in = new ObjectInputStream(new FileInputStream("poly.bin"))) {
					 vertices = (ArrayList<Point>) in.readObject();
				} catch(Exception ex) {
					ex.printStackTrace();
				}
			}
		});
		
		add(clearBtn);
		add(playBtn);
		add(saveBtn);
		add(loadBtn);
	}

	@Override
	public void paintComponent(Graphics g0) {
		super.paintComponent(g0);
		Graphics2D g = (Graphics2D) g0;

		if (triangles == null) {
			g.setColor(Color.CYAN);
			for (int i = 0; i < vertices.size(); ++i) {
				Point p0 = vertices.get(i);
				Point p1 = vertices.get((i + 1) % vertices.size());
				g.drawLine(p0.x, p0.y, p1.x, p1.y);
			}
		}
		else {
			final int[] xs = new int[3];
			final int[] ys = new int[3];
			for (int i = 0; i < triangles.size(); ++i) {
				final Triangle tri = triangles.get(i);
				xs[0] = tri.a.x; ys[0] = tri.a.y;
				xs[1] = tri.b.x; ys[1] = tri.b.y;
				xs[2] = tri.c.x; ys[2] = tri.c.y;
				
				g.setColor(Color.YELLOW);
				g.fillPolygon(xs, ys, 3);
				g.setColor(Color.BLUE);
				g.drawPolygon(xs, ys, 3);
			}
		}
		
		for (int i = 0; i < vertices.size(); ++i) {
			Point p = vertices.get(i);
			
			g.setColor(Color.RED);
			g.fillOval(p.x - 3, p.y - 3, 7, 7);
			
			g.setColor(Color.BLACK);
			g.drawString(""+ i, p.x - 3, p.y - 3);	
		}
		
	}

	void clear() {
		repaint();
		triangles = null;
		vertices.clear();
	}

	static double polygonArea(java.util.List<Point> points) {
		double area = 0;
		for (int i = 0; i < points.size(); ++i) {
			area += exteriorProduct(
                    points.get(i),
                    points.get((i + 1) % points.size()));
		}
		return area * 0.5;
	}
	

	static double exteriorProduct(Point p0, Point p1) {
		return  p0.x * p1.y - p1.x * p0.y;
	}
	
	static boolean isEmptyTriangle(Point a, Point b, Point c, Link list, boolean clockwise) {
		Link link = list;
		do {
			final Point p = link.b;
			if (p != a && p != b && p != c) {
				if (isClockwise(b, a, p) != clockwise &&
				   isClockwise(a, c, p) != clockwise &&
				   isClockwise(c, b, p) != clockwise) {
					return false;
				}
		    }
		} while ((link = link.next) != list);
		return true;
	}

	static boolean isClockwise(Point a, Point b, Point c) {
		return 0 <= (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
	}

	static boolean isClockwise(java.util.List<Point> points) {
		return 0 <= polygonArea(points);
	}

	static class Triangle {
		Point a;
		Point b;
		Point c;

        Triangle() {}
		Triangle(Point a, Point b, Point c) {
			this.a = a;
			this.b = b;
			this.c = c;
		}
	}

	static void polygonToTriangles(List<Point> points, List<Triangle> triangles) {
       		final boolean clockwise = isClockwise(points);
		final TreeSet<Link> set = new TreeSet<>();

	        Link list = new Link();
        	{
           	 Link prev = list;
	            for (int i = 0; i < points.size(); ++i) {
	                int pred = (i == 0 ? points.size(): i) - 1;
	                int succ = (i + 1) % points.size();
	
	                Link next = new Link();
	                prev.next = next;
	                next.prev = prev;
	
	                next.a = points.get(pred);
	                next.b = points.get(i);
	                next.c = points.get(succ);
	
	                if(next.isClockwise() == clockwise) {
	                    set.add(next);
	                }
	                prev = next;
	            }
	            list = prev.next =
	            list.next;
	            list.prev = prev;
	        }
	
	outer:
		while (!set.isEmpty()) {
			Iterator<Link> i = set.iterator();
			boolean found = false;
			while (i.hasNext()) {
				Link link = i.next();
				Point a = link.a;
				Point b = link.b;
				Point c = link.c;
				if (isEmptyTriangle(a, b, c, link, clockwise)) {
					found = true;
					i.remove();
					Link prev = link.prev;
					Link next = link.next;
					set.remove(prev);
					set.remove(next);
					triangles.add(new Triangle(a, b, c));
					if (next.next == prev /*prev == next*/) {
						break outer;
					}
					prev.c = c; prev.distance = -1;
					next.a = a; next.distance = -1;
					prev.next = next;
					next.prev = prev;
					if (prev.isClockwise() == clockwise) set.add(prev);
					if (next.isClockwise() == clockwise) set.add(next);
					break;
				}
			}
			if (!found) {
				throw new IllegalStateException("found == false");
			}
		}
	}

	static class Link extends Triangle implements Comparable<Link> {
		
		Link prev;
		Link next;
		int distance = -1;
		
		@Override
		public int compareTo(Link that) {
			if (this == that) {
				return 0;
			}
			int delta = getDistance() - that.getDistance();
			return delta != 0 ? delta: hashCode() - that.hashCode(); // <(^_^;)
		}
		
		int getDistance() {
			if (distance == -1) {
				distance = (int) a.distanceSq(c);
			}
			return distance;
		}
		
		boolean isClockwise() { return Poly.isClockwise(a, b, c); }
	}
	
}

This looks really good!
How robust is it?
How does it compare to Delaunay Triangulation etc.?

I'm using this to triangulate paths generated by a marching-squares algorithm, for 2D terrain generation. It works great except for when there is a hole in the path I am trying to triangulate. In this case, the "not found" case is triggered in polygonToTriangles:

if (!found) { throw new IllegalStateException("found == false"); }

Is this triangulation algorithm supposed to handle polygon holes?