/*
 *  ShortestPathApplet.java
 *  =======================
 *
 *  Shripad Thite (thite@uiuc.edu)
 *  October 19, 2000
 *
 */

import java.applet.*;
import java.awt.*;
import java.awt.event.*;
import GraphicsUtil;

class dPoint
{
    public double x, y;

public
    dPoint( double iX, double iY )
    {
	x = iX;
	y = iY;
	return;
    }

public
    dPoint( int iX, int iY )
    {
	x = iX;
	y = iY;
	return;
    }
}


public
class ShortestPathApplet
extends Applet
{
    private static final int MAXV = 10;
    private static final int MAXH = MAXV;
    private static final int POINTSIZE = 2;
    private static final int PICKTOLERANCE = 8;

    private int mouseX=10, mouseY=10;
    private Point pp = new Point(-1,-1);
    private boolean inDragMode=false;

    //... Family of "vertical" lines
    private dPoint vOrigin;
    private dPoint [] vFamilyIn;
    private dPoint [] vFamily;
    private int nv=0;

    //... Family of "horizontal" lines
    private dPoint hOrigin;
    private dPoint [] hFamilyIn;
    private dPoint [] hFamily;
    private int nh=0;

    //... Vertex set
    private dPoint[][] v;

    //... Distance matrix
    private double[][] d;
    private Point[][] pred;


public
    void init()
    {
	this.enableEvents( AWTEvent.MOUSE_EVENT_MASK | AWTEvent.MOUSE_MOTION_EVENT_MASK | AWTEvent.KEY_EVENT_MASK );

	Dimension size = this.getSize();
	vOrigin = new dPoint(size.width >> 1, 0);
	hOrigin = new dPoint(0, size.height >> 1);

	vFamilyIn = new dPoint[MAXV];
	vFamily = new dPoint[MAXV];
	for( int i = 0;  i < MAXV;  i++ )
	    {
		vFamilyIn[i] = new dPoint(0,0);
		vFamily[i] = new dPoint(0,0);
	    }

	hFamilyIn = new dPoint[MAXH];
	hFamily = new dPoint[MAXH];
	for( int j = 0;  j < MAXH;  j++ )
	    {
		hFamilyIn[j] = new dPoint(0,0);
		hFamily[j] = new dPoint(0,0);
	    }

	v = new dPoint[MAXH][MAXV];
	for( int i = 0;  i < MAXH;  i++ )
	    for( int j = 0;  j < MAXV;  j++ )
		v[i][j] = new dPoint(0,0);

	d = new double[MAXH][MAXV];

	pred = new Point[MAXH][MAXV];
	for( int i = 0;  i < MAXH;  i++ )
	    for( int j = 0;  j < MAXV;  j++ )
		pred[i][j] = new Point(0,0);

	return;
    }


public
    void processMouseEvent( MouseEvent e )
    {
	int eID = e.getID();

	if( eID == MouseEvent.MOUSE_PRESSED )
	    {
		mouseX = e.getX();
		mouseY = e.getY();

		//... Find the endpoint where the mouse was clicked.
		if( pickpoint( mouseX, mouseY ) )
		    inDragMode = true;
		else
		    {
			inDragMode = false;

			if( e.isShiftDown() )
			    {
				if( nh < MAXH )
				    {
					hFamilyIn[nh] = new dPoint(mouseX, mouseY);
					hFamily[nh] = new dPoint(mouseX, mouseY);
					nh++;
					updatelines();
					shortestpath();
					repaint();
				    }
			    }
			else
			    {
				if( nv < MAXV )
				    {
					vFamilyIn[nv] = new dPoint(mouseX, mouseY);
					vFamily[nv] = new dPoint(mouseX, mouseY);
					nv++;
					updatelines();
					shortestpath();
					repaint();
				    }
			    }
		    }
	    }
	else if( eID == MouseEvent.MOUSE_RELEASED )
	    {
		inDragMode = false;
		pp.x = pp.y = -1;
	    }
	else
	    super.processMouseEvent( e );

	return;
    }


public
    void processMouseMotionEvent( MouseEvent e )
    {
	int eX = e.getX();
	int eY = e.getY();

	if( e.getID() == MouseEvent.MOUSE_DRAGGED )
	    {
		if( inDragMode )
		    {
			if( pp.x >= 0 )
			    {
				vFamilyIn[pp.x].x = eX;
				vFamilyIn[pp.x].y = eY;
			    }
			else if( pp.y >= 0 )
			    {
				hFamilyIn[pp.y].x = eX;
				hFamilyIn[pp.y].y = eY;
			    }

			updatelines();
			shortestpath();
			repaint();
		    }
	    }
	else
	    super.processMouseMotionEvent( e );

	return;
    }


public
    void processKeyEvent( KeyEvent e )
    {
	super.processKeyEvent( e );
	return;
    }


public
    void paint( Graphics g )
    {
	//... Draw the vertical lines
	g.setColor( Color.red );
	g.drawOval( (int)vOrigin.x - POINTSIZE, (int)vOrigin.y - POINTSIZE, POINTSIZE<<1, POINTSIZE<<1 );
	// g.drawString( "p", (int)vOrigin.x, (int)vOrigin.y );
	for( int i = 0;  i < nv;  i++ )
	    {
		g.drawLine( (int)vOrigin.x, (int)vOrigin.y, (int)vFamily[i].x, (int)vFamily[i].y );
		g.drawString( Integer.toString(i+1), (int)vFamily[i].x, (int)vFamily[i].y );
		g.drawOval( (int)vFamily[i].x - POINTSIZE, (int)vFamily[i].y - POINTSIZE, POINTSIZE<<1, POINTSIZE<<1 );
	    }


	//... Draw the horizontal lines
	g.setColor( Color.blue );
	g.drawOval( (int)hOrigin.x - POINTSIZE, (int)hOrigin.y - POINTSIZE, POINTSIZE<<1, POINTSIZE<<1 );
	// g.drawString( "q", (int)hOrigin.x, (int)hOrigin.y );
	for( int j = 0;  j < nh;  j++ )
	    {
		g.drawLine( (int)hOrigin.x, (int)hOrigin.y, (int)hFamily[j].x, (int)hFamily[j].y );
		g.drawString( Integer.toString(j+1), (int)hFamily[j].x, (int)hFamily[j].y );
		g.drawOval( (int)hFamily[j].x - POINTSIZE, (int)hFamily[j].y - POINTSIZE, POINTSIZE<<1, POINTSIZE<<1 );
	    }


	//... Now draw the shortest path tree
	g.setColor( Color.yellow );
	for( int row = nh-1;  row >= 0;  row-- )
	    for( int col = nv-1;  col >= 0;  col-- )
		{
		    int nextrow = pred[row][col].y;
		    int nextcol = pred[row][col].x;

		    //... Draw thick lines!
		    GraphicsUtil.drawLine( g, (int)v[row][col].x, (int)v[row][col].y, (int)v[nextrow][nextcol].x, (int)v[nextrow][nextcol].y, 4 );
		}


	//... Draw the points of intersection
	g.setColor( Color.black );
	for( int i = 0;  i < nh;  i++ )
	    for( int j = 0;  j < nv;  j++ )
		g.drawOval( (int)v[i][j].x - POINTSIZE, (int)v[i][j].y - POINTSIZE, POINTSIZE<<1, POINTSIZE<<1 );

	return;
    }


private
    boolean pickpoint( int x, int y )
    {
	for( int i = 0;  i < nh;  i++ )
	    if( (Math.abs(x - hFamilyIn[i].x) < PICKTOLERANCE) && (Math.abs(y - hFamilyIn[i].y) < PICKTOLERANCE) )
		{
		    pp.y = i;
		    pp.x = -1;
		    return true;
		}

	for( int j = 0;  j < nv;  j++ )
	    if( (Math.abs(x - vFamilyIn[j].x) < PICKTOLERANCE) && (Math.abs(y - vFamilyIn[j].y) < PICKTOLERANCE) )
		{
		    pp.y = -1;
		    pp.x = j;
		    return true;
		}

	return false;
    }

    //---------------------------------------------------------

private
    dPoint ComputeIntersection( int i, int j )
    {
	//... Intersection of i-th horizontal and j-th vertical lines.
	double mh = (hFamily[i].y - hOrigin.y) / (hFamily[i].x - hOrigin.x);
	double mv = (vFamily[j].y - vOrigin.y) / (vFamily[j].x - vOrigin.x);
	double x = (vOrigin.y - hOrigin.y + mh * hOrigin.x - mv * vOrigin.x) / (mh - mv);
	double y = hOrigin.y + mh * (x - hOrigin.x);
	return new dPoint( x, y );
    }


private
    double distance( int row1, int col1, int row2, int col2 )
    {
	//... Compute the distance between points v[row1][col1]
	//... and v[row2][col2].
	return Math.sqrt( (v[row2][col2].x - v[row1][col1].x)*(v[row2][col2].x - v[row1][col1].x) + (v[row2][col2].y - v[row1][col1].y)*(v[row2][col2].y - v[row1][col1].y) );
    }


private
    boolean isCCW( dPoint p1, dPoint p2, dPoint p3 )
    {
	double det=0;
	det += p2.x*p3.y - p2.y*p3.x;
	det -= p1.x*p3.y - p1.y*p3.x;
	det += p1.x*p2.y - p1.y*p2.x;
	return( det > 0 );
    }


private
    void updatelines()
    {
	//... Copy the arrays
	for( int i = 0;  i < nh;  i++ )
	    {
		hFamily[i].x = hFamilyIn[i].x;
		hFamily[i].y = hFamilyIn[i].y;
	    }
	for( int j = 0;  j < nv;  j++ )
	    {
		vFamily[j].x = vFamilyIn[j].x;
		vFamily[j].y = vFamilyIn[j].y;
	    }


	//... Sort the horizontal family by decreasing slope.
	for( int i = 0;  i < nh-1;  i++ )
	    for( int j = i+1;  j < nh;  j++ )
		if( isCCW( hFamily[i], hOrigin, hFamily[j] ) )
		    {
			//... Swap!
			dPoint temp = hFamily[i];
			hFamily[i] = hFamily[j];
			hFamily[j] = temp;
		    }


	//... Sort the vertical family by increasing slope.
	for( int i = 0;  i < nv-1;  i++ )
	    for( int j = i+1;  j < nv;  j++ )
		if( !isCCW( vFamily[i], vOrigin, vFamily[j] ) )
		    {
			//... Swap!
			dPoint temp = vFamily[i];
			vFamily[i] = vFamily[j];
			vFamily[j] = temp;
		    }

	//... Compute the vertex set
	for( int i = 0;  i < nh;  i++ )
	    for( int j = 0;  j < nv;  j++ )
		v[i][j] = ComputeIntersection( i, j );

	return;
    }


private
    void shortestpath()
    {
	//... Now compute the shortest paths from (0,0)
	//... to every other vertex.

	//... Initialize!
	for( int i = 0;  i < nh;  i++ )
	    for( int j = 0;  j < nv;  j++ )
		{
		    d[i][j] = Double.POSITIVE_INFINITY;  //... Infinity!
		    pred[i][j].y = i;
		    pred[i][j].x = j;
		}
	d[0][0] = 0;

	for( int iter = 0;  iter <= (nh-1)*(nv-1);  iter++ )
	    for( int i = 0;  i < nh;  i++ )
		for( int j = 0;  j < nv;  j++ )
		{
		    //... Try the North neighbor (i-1,j) first.
		    if( i > 0 )
			{
			    double newdist = d[i-1][j] + distance(i-1,j,i,j);
			    if( newdist < d[i][j] )
				{
				    d[i][j] = newdist;
				    pred[i][j].y = i-1;
				    pred[i][j].x = j;
				}
			}

		    //... Try the West neighbor (i,j-1) next.
		    if( j > 0 )
			{
			    double newdist = d[i][j-1] + distance(i,j-1,i,j);
			    if( newdist < d[i][j] )
				{
				    d[i][j] = newdist;
				    pred[i][j].y = i;
				    pred[i][j].x = j-1;
				}
			}
		}
	return;
    }

} // end class ShortestPathApplet