smallestcirclecom.java

生成指定点数的随机点

		double rad,tem;//Radius of the circle and a temporary parameter
		double recx,recy;//Coordinates of the up-left corner of the rectangle which contains the circle
		boolean isinside=true;//Check if the point is inside the Circle
		int[] position;//Store the radii of enclosing circles
		for(int i=0;i<x.length;i++)
		{
			for(int j=i+1;j<x.length;j++)
			{
				for(int k=j+1;k<x.length;k++)
				{
					dbx1=x[i];
					dby1=y[i];
					dbx2=x[j];
					dby2=y[j];
					dbx3=x[k];
					dby3=y[k];
					mx12=(dbx1+dbx2)/2.0;
					my12=(dby1+dby2)/2.0;
					mx23=(dbx2+dbx3)/2.0;
					my23=(dby2+dby3)/2.0;
					k12=-(dbx1-dbx2)/(dby1-dby2);
					k23=-(dbx2-dbx3)/(dby2-dby3);
					midx=((my23-my12)-(k23*mx23-k12*mx12))/(k12-k23);
					midy=k12*(midx-mx12)+my12;//Caculate the coordinates of the center of the circle determined by three points
					tem=(dbx1-midx)*(dbx1-midx)+(dby1-midy)*(dby1-midy);
					rad=Math.sqrt(tem);//Get the radius of the circle
					recx=midx-rad;
					recy=midy-rad;
					Ellipse2D.Double ellipse=new Ellipse2D.Double(recx,recy,rad*2.0,rad*2.0);
					//Get every possible circle
					for(int l=0;l<x.length;l++)//Check if all the other points is inside the circle
					{
						if(l==i||l==j||l==k)
							continue;
						if(!ellipse.contains(x[l],y[l]))
						{
							isinside=false;
							break;
						}
					}
					if(isinside)//Store the enclosing circles 
					{
						cxs.addElement(new Integer((int)midx));
						cys.addElement(new Integer((int)midy));
						rs.addElement(new Integer((int)rad));
					}
					isinside=true;//Refresh "isinside"
				}
			}
		}
		
		position=new int[rs.toArray().length];//Get the array of the radii
		for(int num=0;num<position.length;num++)
		{
			position[num]=((Integer)rs.get(num)).intValue();
		}
		Arrays.sort(position);//Sort the array
		
		for(int m=0;m<cxs.size();m++)
		{
			if(((Integer)rs.get(m)).intValue()==position[0])//Search for the smallest radius
			{
				centerx=((Integer)cxs.get(m)).intValue();
				centery=((Integer)cys.get(m)).intValue();
				radius=((Integer)rs.get(m)).intValue();
			}
		}
	}//End of method:searchThree
}//End of class:MiniCircle

class MiniCircle2
{
    LinkedList points=new LinkedList();
    Ellipse2D.Double miniCircle;
	
	public void refresh()//Clean old points before restart
	{
		points=new LinkedList();
		System.gc();
		miniCircle=null;
	}
    public void makePoints(int number)// Generate random points of given number.
	{
		Random random=new Random();
		for(int i=0;i<number;i++)
		{
			Point p=new Point(random.nextInt(300)+200,random.nextInt(300)+150);
			points.add(p);
		}
	}// End of method:makePoints
	
	public Ellipse2D.Double getMiniCircle(LinkedList P)
	{
		LinkedList R=new LinkedList();
		
		return getBoundaryCircle(P,R);//Get the smallest circle
	}// End of method:getMiniCircle2
	
	public Ellipse2D.Double getBoundaryCircle(LinkedList P,LinkedList R)
	//Return a circle enclosing P with R on its boundary
	{
		Point p;
		Ellipse2D.Double bcircle=new Ellipse2D.Double();
		if((P.size()==0)||(R.size()==3))
		{
			return getCircle(R,R.size());
		}
		else
		{
			p=(Point)(P.removeLast());
			bcircle=getBoundaryCircle(P,R);
			if(!bcircle.contains(p))
			{
				R.add(p);
				bcircle=getBoundaryCircle(P,R);
				R.removeLast();
				P.addFirst(p);
			}
			else P.addLast(p);
			return bcircle;
		}
	}//End of method:getBoundaryCircle
	
	public Ellipse2D.Double getCircle(LinkedList R,int length)
	//Return a circle with "length" points(R) on its boundary
	{
		double x,y;
		double k1,k2;//Slope of the line determined by two out of the three points
		double m1x,m1y,m2x,m2y;//Coordinates of the middle point of two out of the three points
		Point2D.Double center=new Point2D.Double();//The center of the circle
		double radius;//Radius of the circle
		Ellipse2D.Double circle;
		
		if(length==0)
		{
			x=0;
			y=0;
			center.setLocation(x, y);
			radius=0;
		}
		
		else if(length==1)
		{
			x=((Point)R.get(0)).getX();
			y=((Point)R.get(0)).getY();
			center.setLocation(x, y);
			radius=0;
		}
		
		else if(length==2)
			{
			x=(((Point)R.get(0)).getX()+((Point)R.get(1)).getX())/2.0;
			y=(((Point)R.get(0)).getY()+((Point)R.get(1)).getY())/2.0;
			center.setLocation(x, y);
			radius=(Math.sqrt(Math.pow(((Point)R.get(0)).getX()-((Point)R.get(1)).getX(),2.0)
					        +Math.pow(((Point)R.get(0)).getY()-((Point)R.get(1)).getY(),2.0)))/2.0;
			}
		
		else
		{
			m1x=(((Point)R.get(0)).getX()+((Point)R.get(1)).getX())/2.0;
			m1y=(((Point)R.get(0)).getY()+((Point)R.get(1)).getY())/2.0;
			m2x=(((Point)R.get(1)).getX()+((Point)R.get(2)).getX())/2.0;
			m2y=(((Point)R.get(1)).getY()+((Point)R.get(2)).getY())/2.0;
			k1=-(((Point)R.get(0)).getX()-((Point)R.get(1)).getX())/(((Point)R.get(0)).getY()-((Point)R.get(1)).getY());
			k2=-(((Point)R.get(1)).getX()-((Point)R.get(2)).getX())/(((Point)R.get(1)).getY()-((Point)R.get(2)).getY());
			x=((m2y-m1y)-(k2*m2x-k1*m1x))/(k1-k2);
			y=k1*(x-m1x)+m1y;//Caculate the coordinates of the center of the circle determined by three points
			center.setLocation(x, y);
			radius=Math.sqrt(Math.pow((((Point)R.get(0)).getX()-x),2.0)+Math.pow((((Point)R.get(0)).getY()-y),2.0));
		}
		
		circle=new Ellipse2D.Double(x-radius,y-radius,radius*2.0,radius*2.0);
		return circle;
    }
}//End of method:getCircle

class DrawPanel extends JPanel//Generate the drawing area
{
	/**
	 * 
	 */
	private static final long serialVersionUID = 7883625626728462343L;

	public void paint(Graphics g)
	{
		if(SmallestCircleCom.target1.isfinished)//Draw the points and circle
		{
			g.setColor(getBackground());
			g.fillRect(getX(), getY(), getWidth(), getHeight());//Cover the last circle and points
			g.setColor(Color.BLACK);
			for(int i=0;i<SmallestCircleCom.target1.x.length;i++)//Draw the points
		    {
			  g.fillOval(SmallestCircleCom.target1.x[i]-1, SmallestCircleCom.target1.y[i]-1, 2, 2);
		    }
			  g.setColor(Color.GREEN);
			  g.drawOval(SmallestCircleCom.target1.centerx-SmallestCircleCom.target1.radius,
				         SmallestCircleCom.target1.centery-SmallestCircleCom.target1.radius,
				         SmallestCircleCom.target1.radius*2,SmallestCircleCom.target1.radius*2);//Draw the Circle
		      g.setColor(Color.BLUE);
			  g.fillOval(SmallestCircleCom.target1.centerx-2,SmallestCircleCom.target1.centery-2, 4, 4);//Draw the center point
			  g.setColor(Color.BLACK);
		}
		if(SmallestCircleCom.target2.miniCircle!=null)//Draw the points and circle
		{
			int x,y;
			g.setColor(getBackground());
			g.fillRect(getX(), getY(), getWidth(), getHeight());//Cover the last circle and points
			g.setColor(Color.BLACK);
		  
			for(int i=0;i<SmallestCircleCom.target2.points.size();i++)//Draw the points
		    {
			   x=((Point)(SmallestCircleCom.target2.points.get(i))).x;
			   y=((Point)(SmallestCircleCom.target2.points.get(i))).y;
			   g.fillOval(x-1, y-1, 2, 2);
		    }
			g.setColor(Color.MAGENTA);
			g.drawOval((int)SmallestCircleCom.target2.miniCircle.getX(),(int)SmallestCircleCom.target2.miniCircle.getY(),
	      	           (int)SmallestCircleCom.target2.miniCircle.getWidth(),(int)SmallestCircleCom.target2.miniCircle.getHeight());//Draw the Circle
		    g.setColor(Color.RED);
		    g.fillOval((int)SmallestCircleCom.target2.miniCircle.getCenterX()-2,
		    		(int)SmallestCircleCom.target2.miniCircle.getCenterY()-2, 4, 4);//Draw the center point
		    g.setColor(Color.BLACK);
		}
	}//End of method:paint
}//End of class:DrawPanel