// Sample program 
// Draws a bunch of points
// With a triangulation on those points
//
// Your job is to locate the triangle in 
// which the user clicks, using a Kirkpatrick hierarchy
//
// Original by:  Robert Hochberg
// April 4, 2007
//	
// modified by:
// 

import java.io.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import java.awt.image.*;
import javax.swing.*;

public class Kirk {
    static int POINTWID = 2; // size of points

    // the x and y arrays hold the coordinates
    // the B array is the order of the points in the polygon
    // You want to fill the C array with the simple polygon
    static double x[] = new double[200];

    static double y[] = new double[200];

    static int iIndex[] = new int[300];

    static int jIndex[] = new int[300];

    static int edgesNeeded = 0;

    static KirkFrame myFrame;

    static int numPoints = 11;

    public static void main(String args[]) {
	makeTriangulation();

	// Create the frame to draw on
	myFrame = new KirkFrame();
	myFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
	myFrame.setSize(600, 600);
	myFrame.setVisible(true);
    }

    public static void makeTriangulation() {
	int numBoundary = 4 + (int) (numPoints / 10);
	int numInterior = numPoints - numBoundary;
	int i, j, k;			// counters
	double shortestLength[] = new double[300];

	// Build the corners
	x[0] = 0; y[0] = 0;
	x[1] = 1; y[1] = 0;
	x[2] = 1; y[2] = 1;
	x[3] = 0; y[3] = 1;

	// Build the other boundary points && (k >= 0)){
	int bottomNum = (int) (numBoundary / 4);
	int rightNum  = (int) (2*numBoundary / 4) - bottomNum;
	int topNum    = (int) (3*numBoundary / 4) - bottomNum - rightNum;
	int leftNum   = numBoundary - bottomNum - rightNum - topNum;
	i = 4;
	for(j = 0; j < bottomNum; j++){	// bottom
	    x[i] = 1 / (bottomNum + 1);
	    y[i] = 0;
	    i++;
	}
	for(j = 0; j < rightNum; j++){	// right
	    x[i] = 1;
	    y[i] = 1 / (rightNum + 1);
	    i++;
	}
	for(j = 0; j < topNum; j++){	// top
	    x[i] = 1 / (topNum + 1);
	    y[i] = 1;
	    i++;
	}
	for(j = 0; j < leftNum; j++){	// left
	    x[i] = 0;
	    y[i] = 1 / (leftNum + 1);
	    i++;
	}

	System.out.println("Added boundary.  i = " + i);
	// Calculate the number of edges our triangulation will need 

	edgesNeeded = i - 3 + 3*(numPoints - i);
	System.out.println("Edges Needed = " + edgesNeeded);
	for(k = 0; k < edgesNeeded; k++)
	    shortestLength[k] = 2; // 2 = infinity

	// Build the interior points
	while(i < numPoints){
	    System.out.println("Added point " + i + ", x = " + x[i] + ", y = " + y[i]);
	    x[i] = Math.random();
	    y[i] = Math.random();
	    i++;
	}

	// Add the edges of the triangulation
	for(i = 0; i < numPoints - 1; i++)
	    for(j = i + 1; j < numPoints; j++)
		if((x[i] != x[j]) && (y[i] != y[j])){ 

		    double currentLength = dis(i, j);
		    if(currentLength < shortestLength[edgesNeeded - 1]){
			k = edgesNeeded - 2;
			while((k >= 0) && (currentLength < shortestLength[k])){
			    shortestLength[k + 1] = shortestLength[k];
			    iIndex[k + 1] = iIndex[k];
			    jIndex[k + 1] = jIndex[k];
			    k--;
			}
			iIndex[k + 1] = i;
			jIndex[k + 1] = j;
			shortestLength[k + 1] = currentLength; 
		    }
		}
    }



    public static double dis(int i, int j) {
	return Math.sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j])
			 * (y[i] - y[j]));
    }

    public static boolean crosses(double a, double b, double c, double d,
				  double e, double f, double g, double h) {
	double sgn1a, sgn1b, sgn2a, sgn2b;
	// System.out.println("In crosses, with numpoints = " + countPoints);
	double det1a = (c - a) * (f - b) - (e - a) * (d - b);
	if (det1a < 0)
	    sgn1a = -1;
	else
	    sgn1a = 1;
	double det1b = (c - a) * (h - b) - (g - a) * (d - b);
	if (det1b < 0)
	    sgn1b = -1;
	else
	    sgn1b = 1;
	double det2a = (e - g) * (b - h) - (a - g) * (f - h);
	if (det2a < 0)
	    sgn2a = -1;
	else
	    sgn2a = 1;
	double det2b = (e - g) * (d - h) - (c - g) * (f - h);
	if (det2b < 0)
	    sgn2b = -1;
	else
	    sgn2b = 1;
	if ((sgn1a * sgn1b < 0) && (sgn2a * sgn2b < 0)) {
	    // System.out.println("("+a+","+b+")-("+c+","+d+
	    // ") Crosses ("+e+","+f+")-("+g+","+h+")");
	    return true;
	} else
	    return false;
    }

    public static class KirkFrame extends JFrame {
	public static JSlider numPointsSlider;

	public KirkFrame() {
	    super("Create you own Simple Polygon");
	    Container content = getContentPane();
	    content.setLayout(new java.awt.BorderLayout());
	    JTabbedPane tabbedPane = new JTabbedPane();
	    tabbedPane.setPreferredSize(new java.awt.Dimension(300, 400));
	    tabbedPane.addTab("Triangulation", new KirkPanel());
	    content.add(tabbedPane, java.awt.BorderLayout.CENTER);

	    // Slider for the number of points
	    numPointsSlider = new JSlider(
					  javax.swing.SwingConstants.HORIZONTAL, 3, 100, 11);
	    numPointsSlider
		.addChangeListener(new javax.swing.event.ChangeListener() {
			public void stateChanged(
						 javax.swing.event.ChangeEvent evt) {
			    numPointsSliderStateChanged(evt);
			}
		    });
	    content.add(numPointsSlider, java.awt.BorderLayout.SOUTH);
	}

	private void numPointsSliderStateChanged(
						 javax.swing.event.ChangeEvent evt) {
	    numPoints = numPointsSlider.getValue();
	    makeTriangulation();
	    repaint();
	}
    }

    public static class KirkPanel extends JPanel {
	public void paintComponent(Graphics g) {
	    super.paintComponent(g);
	    Graphics2D g2 = (Graphics2D) g;

	    // First set the scaling to fit the window
	    Dimension size = getSize();
	    int Xwid = (int) (0.90 * size.width);
	    int Ywid = (int) (0.90 * size.height);

	    // First draw the segments
	    g2.setColor(Color.red);
	    for (int i = 0; i < edgesNeeded; i++)
		g2.drawLine((int) (Xwid * x[iIndex[i]]), 
			    (int) (Ywid * y[iIndex[i]]),
			    (int) (Xwid * x[jIndex[i]]), 
			    (int) (Ywid * y[jIndex[i]]));


	    // Now draw the points
	    System.out.println("NumPoints = " + numPoints);
	    for (int i = 0; i < numPoints; i++) {
		g2.fillRect((int) (Xwid * x[i]) - POINTWID, (int) (Ywid * y[i])
			    - POINTWID, 2 * POINTWID + 1, 2 * POINTWID + 1);
	    }
	}
    }
}