smallestcirclecom.java

生成指定点数的随机点

//////////////////////////////////////////////////////////////
//
//SmallestCircleCom.java
//
//Created by CAO Song
//
//////////////////////////////////////////////////////////////
//Readme:
//  This program is designed to compare the results of finding
//the smallest enclosing ball with two different algorithms.

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Container;
import java.awt.Graphics;
import java.awt.GridLayout;
import java.awt.Point;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Point2D;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Random;
import java.util.Vector;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JTextField;

public class SmallestCircleCom extends JPanel implements ActionListener
{
    /**
	 * 
	 */
	private static final long serialVersionUID = -2468943794242724022L;
	private JLabel text1=new JLabel("Please enter the number of points:");//Set up GUI
    private JTextField text2=new JTextField();
    private JButton but=new JButton("Go!");
    private JLabel lab=new JLabel("Used time:");
    private JLabel lab1=new JLabel("Algorithm1's results:");
    private JLabel lab2=new JLabel("Algorithm2's results:");
    
	private long start1,finish1;
	private long start2,finish2;
	private int time1,time2;//Name time references
    
	private int pointcount;//Name the number of points
	static MiniCircle1 target1=new MiniCircle1();//Create a new MiniCircle1 Object target1
	static MiniCircle2 target2=new MiniCircle2();//Create a new MiniCircle2 Object target2
    static Container drawpanel=new DrawPanel();//Create a new DrawPanel Object drawpanel 
    
    public SmallestCircleCom()//Constructor of SmallestCircleCom
    {
     	setLayout(new GridLayout(3,1));
    	JPanel textpane=new JPanel(new GridLayout(1,3));
    	JPanel labpane=new JPanel(new GridLayout(3,1));
    	
    	textpane.add(text1);
    	textpane.add(text2);
    	textpane.add(but);
    	
    	labpane.add(lab);
    	labpane.add(lab1);
    	labpane.add(lab2);
    	
    	text2.addActionListener(this);
    	but.addActionListener(this);	
    	
    	add(textpane);
    	add(labpane);
    }// End of method:SmallestCircleCom
    
	public void actionPerformed(ActionEvent e)
	{
		try
		{
		   pointcount=Integer.parseInt(text2.getText());//Get the number from text2
		   if(pointcount<=0)//Ensure the number is positive
			   throw new Exception();
		   target2.makePoints(pointcount);//Generate the points
		   
		   target1.x=new int [pointcount];
		   target1.y=new int [pointcount];          
		   for(int i=0;i<pointcount;i++)
		   {
			   target1.x[i]=((Point)(target2.points.get(i))).x;
			   target1.y[i]=((Point)(target2.points.get(i))).y;
		   }//Copy the points from target2 to target1
			
           start1=System.currentTimeMillis();
           target1.getMiniCircle();//Calculate the smallest circle with algorithm1
		   finish1=System.currentTimeMillis();
		   time1=(int)(finish1-start1);//Calculate the time used with algorithm1
		   
		   start2=System.currentTimeMillis();
		   target2.miniCircle=target2.getMiniCircle(target2.points);//Calculate the smallest circle with algorithm2
		   finish2=System.currentTimeMillis();
		   time2=(int)(finish2-start2);//Calculate the time used with algorithm2
		
		   lab.setText("DONE!  Used time by Algorithm1: "+time1+" milliseconds." +
				       "       Used time by Algorithm2: "+time2+" milliseconds." );
		   lab1.setText("Algorithm1's results: center("+target1.centerx+","+target1.centery+") , radius="+target1.radius);
		   lab2.setText("Algorithm2's results: center("+(int)target2.miniCircle.getCenterX()+","+(int)target2.miniCircle.getCenterY()+") , radius="+(int)(SmallestCircleCom.target2.miniCircle.getWidth()/2));
		   
		   drawpanel.paint(drawpanel.getGraphics());
		   target1.refresh();
		   target2.refresh();
		   target1.x=null;
		   target1.y=null;
		   System.gc();//Refresh target1 and target2
		}
		catch(Exception exception)
		{
			lab.setText("Input Error!");
		}
	}// End of method:actionPerformed
	
	public void paint(Graphics g)
	{
		super.paint(g);//Paint GUI
	}// End of method:paint
	
	public static void main(String[] args)
	{
		JFrame frame=new JFrame("Find the smallest enclosing circle!(Comparing two Algorithms)");
		frame.setLayout(new BorderLayout());
		Container controls=new SmallestCircleCom();
		frame.add(controls,BorderLayout.SOUTH);
		frame.add(drawpanel,BorderLayout.CENTER);
		
		frame.setSize(700,750);
	    frame.setVisible(true);
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
	}//End of method:main
}//End of class:SmallestCircle2

class MiniCircle1//Calculate the Smallest Circle with algorithm1
{
    int[] x,y;//Store the Random Points
	int centerx,centery;//Store the position of the center of the smallest circle
	int radius;//Store the radius of the smallest circle
	private Vector cxs=new Vector();
	private Vector cys=new Vector();//Store the position of the enclosing circles in 3-point searching
	private Vector rs=new Vector();//Store the radius of the enclosing circles in 3-point searching
	static boolean isfinished=false;//Check if the procedure is finished
	
	public void refresh()//Clean old points before restart
	{
		cxs=new Vector();
		cys=new Vector();
		rs=new Vector();
		isfinished=false;
		System.gc();
	}
	public void makePoints(int number)// Generate random points of given number.
	{
		x=new int[number];
		y=new int[number];
		Random random=new Random();
		for(int i=0;i<x.length;i++)
		{
			x[i]=random.nextInt(300)+200;
			y[i]=random.nextInt(300)+150;
		}
	}// End of method:makePoints
	
	public void getMiniCircle()
	{
		if(!searchTwo())//Search for the smallest circle
	    	searchThree();
		isfinished=true;
	}// End of method:getMiniCircle
	
	public boolean searchTwo()//Search circles with 2 points on their boundaris
	{
		double dbx1,dbx2,dby1,dby2;//Coordinates of the two points
		double midx,midy;//Coordinates of the middle point of the two points
		double diam,tem;//Diameter 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
		for(int i=0;i<x.length;i++)
		{
			for(int j=i+1;j<x.length;j++)
			{
				dbx1=x[i];
				dby1=y[i];
				dbx2=x[j];
				dby2=y[j];
				midx=(dbx1+dbx2)/2.0;
				midy=(dby1+dby2)/2.0;
				tem=(dbx1-dbx2)*(dbx1-dbx2)+(dby1-dby2)*(dby1-dby2);
				diam=Math.sqrt(tem);
				recx=midx-diam/2.0;
				recy=midy-diam/2.0;
				Ellipse2D.Double ellipse=new Ellipse2D.Double(recx,recy,diam,diam);
				//Get every possible circle
				for(int k=0;k<x.length;k++)
				{
					if(k==i||k==j)
						continue;
					if(!ellipse.contains(x[k],y[k]))
					{
						isinside=false;
						break;
					}
				}
				if(isinside)
				{
					centerx=(int)midx;
					centery=(int)midy;
					radius=(int)(diam/2.0);
					return true;
				}
				isinside=true;//Refresh "isinside"
			}
		}
		return false;
	}//End of method:searchTwo
	
	public void searchThree()//Search circles with 3 points on their boundaries
	{
		double dbx1,dbx2,dby1,dby2,dbx3,dby3;//Coordinates of the three points
		double k12,k23;//Slope of the line determined by two out of the three points
		double mx12,my12,mx23,my23;//Coordinates of the middle point of two out of the three points
		double midx,midy;//Coordinates of the center point of the circle