/*

A fun little Java Applet, by Orion Lawlor 12/97.



This class depends on my TriApplet class, and

shows how to easily draw a convex hull around a 

set of wandering points.



It uses an inefficent O(n*n) algorithm.

*/

import java.awt.*;

import AnimApplet;

import TriApplet;

import Tri;



public class ConvexHull extends TriApplet

{

	protected void performTask(Graphics g)

	{

		int connectPts[]=new int[ndots+3];

		int nconn=0;

		int i;

		int topPt=0;

		double topHt=100000;

		for (i=0;i<ndots;i++)

		{

			Tri p=(Tri)dots.elementAt(i);

			if (topHt>p.y)

			{

				topPt=i;

				topHt=p.y;

			}

		}

		int curpt=topPt;

		double curangle=Math.PI/2;

		connectPts[nconn++]=curpt;

		do {

			Tri curTri=(Tri)dots.elementAt(curpt);

			int nextpt=0;

			double nextang=10;

			for (i=0;i<ndots;i++)

				if (curpt!=i)

				{

					Tri iTri=(Tri)dots.elementAt(i);

					double angle=Math.atan2(-(iTri.y-curTri.y),iTri.x-curTri.x);

					angle=curangle-angle;

					if (angle<0.001) angle+=2*Math.PI;

					if (nextang>angle)

					{

						nextang=angle;

						nextpt=i;

					}

				}

			curangle-=nextang;

			curpt=nextpt;

			connectPts[nconn++]=curpt;

		}

		while ((topPt)!=curpt&&(nconn<(ndots+3)));

		

		for (i=1;i<nconn;i++)

		{

			Tri p2=(Tri)dots.elementAt(connectPts[i-1]);

			Tri p=(Tri)dots.elementAt(connectPts[i]);

			g.drawLine((int)p.x,(int)p.y,(int)p2.x,(int)p2.y);

			g.drawString((new Integer(i)).toString(),(int)(p.x+p2.x)/2,(int)(p.y+p2.y)/2);

		}

	}

}