/*
 *  mincircle.java
 *  ==============
 *
 *  Compute the smallest circle enclosing a set of points.
 *  Also known as the smallest enclosing circle problem.
 *
 *  Shripad Thite (thite@uiuc.edu)
 *  November 26, 2000
 *
 */

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

import GraphicsUtil;
import dPoint;
import dCircle;



public
class mincircle
extends Applet
{
    //... Constants
    private static final int MAXNUM = 13;

    private static final int POINTSIZE = 2;
    private static final int POINTSIZE2 = POINTSIZE<<1;

    private static final int PICKTOLERANCE = POINTSIZE2;


    //... User-interface
    private int mouseX=0, mouseY=0;
    private Dimension appSize;

    private int pp;  // index of point being dragged
    private boolean inDragMode=false;

    //... Array of points
    private dPoint[] p;
    private int   n=0;

    private dPoint[]  bndry;

    //... Center and radius of minimum enclosing circle.
    private dPoint minCenter = new dPoint(0,0);
    private double minRadius;



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

	//... Get the applet window size.
	appSize = this.getSize();

	//... Allocate memory.
	p = new dPoint[MAXNUM];
	bndry = new dPoint[3];

	return;
    }


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

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

		//... Find the point (if any) that was picked.
		if( pickpoint( mouseX, mouseY ) )
		    inDragMode = true;
		else
		    {
			if( n < MAXNUM )
			    {
				p[n++] = new dPoint(mouseX, mouseY);
				updateSolution();
				repaint();
			    }
		    }
	    }
	else if( eID == MouseEvent.MOUSE_RELEASED )
	    {
		inDragMode = false;
		pp = -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 )
		    {
			p[pp].x = eX;
			p[pp].y = eY;

			updateSolution();
			repaint();
		    }
	    }
	else
	    super.processMouseMotionEvent( e );

	return;
    }


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


public
    void paint( Graphics g )
    {
	//... Draw the points.
	for( int i = 0;  i < n;  i++ )
	    {
		g.setColor( Color.blue );
		g.drawOval( (int)(p[i].x - POINTSIZE), 
			    (int)(p[i].y - POINTSIZE), 
			    POINTSIZE2, POINTSIZE2 );
		g.setColor( Color.red );
		g.drawString( Integer.toString(i+1), 
			      (int)(p[i].x + POINTSIZE2), 
			      (int)(p[i].y + POINTSIZE2) );
	    }

	//... Draw the circle.
	g.setColor( Color.yellow );
	g.drawOval( (int)(minCenter.x - minRadius),
		    (int)(minCenter.y - minRadius),
		    (int)(2*minRadius), (int)(2*minRadius) );

	return;
    }



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


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

	return false;
    }



private
    double distance( dPoint p1, dPoint p2 )
    {
	return Math.sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) );
    }



    //...
    // Given three points defining a circle,
    // compute the center and radius of the circle.
    //...

private
    dCircle findCenterRadius( dPoint p1, dPoint p2, dPoint p3 )
    {
	double x = (p3.x*p3.x * (p1.y - p2.y) 
		    + (p1.x*p1.x + (p1.y - p2.y)*(p1.y - p3.y)) 
		    * (p2.y - p3.y) + p2.x*p2.x * (-p1.y + p3.y)) 
	    / (2 * (p3.x * (p1.y - p2.y) + p1.x * (p2.y - p3.y) + p2.x 
		    * (-p1.y + p3.y)));

	double y = (p2.y + p3.y)/2 - (p3.x - p2.x)/(p3.y - p2.y) 
	    * (x - (p2.x + p3.x)/2);

	dPoint c = new dPoint( x, y );
	double r = distance(c, p1);

	return new dCircle( c, r );
    }


    //...
    // Compute the center and radius of the smallest circle
    // enclosing the n points in P, such that the m points
    // in B lie on the boundary of the circle.
    //...

private
    dCircle minCircle( int n, dPoint[] p, int m, dPoint[] b )
    {
	dPoint c = new dPoint(-1,-1);
	double r = 0;


	//... Compute the smallest circle defined by B.
	if( m == 1 )
	    {
		c = new dPoint( b[0] );
		r = 0;
	    }
	else if( m == 2 )
	    {
		c = new dPoint( (b[0].x+b[1].x)/2, (b[0].y+b[1].y)/2 );
	        r = distance( b[0], c );
	    }
	else if( m == 3 )
		return findCenterRadius( b[0], b[1], b[2] );


	dCircle minC = new dCircle( c, r );

	//... Now see if all the points in P are enclosed.
	for( int i = 0;  i < n;  i++  )
	    if( distance(p[i], minC.c) > minC.r )
		{
		    //... Compute B <--- B union P[i].
		    b[m] = new dPoint( p[i] );

		    //... Recurse
		    minC = minCircle( i, p, m+1, b );
		}

	return minC;
    }


private
    void updateSolution()
    {
	dCircle minC = minCircle( n, p, 0, bndry );
	minCenter = minC.c;
	minRadius = minC.r;

	return;
    }

} // end class mincircle