import java.applet.Applet;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.util.ArrayList;
import java.util.Iterator;

public final class Gabrielgraph extends Applet {

	public void init() {
		this.setSize(400, 400);
		this.setForeground(Color.RED);
		this.addMouseListener(new MouseHelper());
	}

	public void paint(Graphics g) {
		Iterator<Point> piterator = this.points.iterator();
		while(piterator.hasNext()) {
			Point p = piterator.next();
			g.fillOval((int)p.getX(), (int)p.getY(), 5, 5);
		}
		Iterator<Point> eiterator = this.edges.iterator();
		while(eiterator.hasNext()) {
			Point p1 = eiterator.next();
			Point p2 = eiterator.next();
			g.drawLine((int)p1.getX(), (int)p1.getY(), (int)p2.getX(), (int)p2.getY());
		}
	}

	private void calculate(java.util.List<Point> points, java.util.List<Point> edges) {
	    edges.clear();
	    for(int i = 0; i < points.size(); ++i) {
		for(int j = 0; j < points.size(); ++j) {
		    boolean isGabriel = true;
		    for(int k = 0; k < points.size(); ++k) {
			if(i != j && i != k && j != k &&
			   Math.pow(d(points.get(i), points.get(j)), 2) >=
			   Math.pow(d(points.get(i), points.get(k)), 2)
			   + Math.pow(d(points.get(j), points.get(k)), 2)) {
			    isGabriel = false;
			    break;
			}
		    }
		    if (isGabriel) {
			// Kante markieren
			edges.add(points.get(i));
			edges.add(points.get(j));		    
		    }
		}
	    }
	}


	private double d(Point p1, Point p2) {
		return Math.sqrt(Math.pow(p2.getX() - p1.getX(), 2) +
				Math.pow(p2.getY() - p1.getY(), 2));
	}

	private java.util.List<Point> points = new ArrayList<Point>();
	private java.util.List<Point> edges = new ArrayList<Point>();

	private class MouseHelper extends MouseAdapter {

		public void mouseClicked(MouseEvent clicked) {
			points.add(clicked.getPoint());
			calculate(points, edges);
			repaint();
		}
	}
}