import java.awt.event.*;
import java.awt.*;
import java.applet.*;
import java.lang.Math;
import java.util.Vector;
public class Nearest extends Applet implements ActionListener
{
DrawCanvas canvas; // Main canvas
TextField MessageText; // Text field used to display messages
TextField knnText; // Text field to show the number of Nearest neighbor to search
TextField nPointText; // Text field to show the number of points in the data set
Button ResetButton;
Button RandomButton;
Button NormalRandomButton;
Button NNButton; // Button to switch mode between Search NN/edit point
Button AddNNButton; // Increase Nearest neighbor to search
Button RemoveNNButton; // Decrease Nearest neighbor to search
Button SimButton; // Activate a simulation
public void init()
{
Rectangle bound = getBounds();
add(new Label("Number of points:"));
nPointText = new TextField(4);
nPointText.setText("0");
nPointText.setEditable(false);
add(nPointText);
add(new Label("Number of Nearest neighbor to search:"));
knnText = new TextField(3);
knnText.setText("1");
knnText.setEditable(false);
add(knnText);
AddNNButton = new Button("+");
RemoveNNButton = new Button("-");
AddNNButton.addActionListener(this);
RemoveNNButton.addActionListener(this);
add(AddNNButton);
add(RemoveNNButton);
MessageText = new TextField("Welcome to the nearest neighbor applet!!");
MessageText.setEditable(false);
canvas = new DrawCanvas(MessageText, nPointText);
canvas.setSize(bound.width-10,bound.height-140);
add(canvas);
ResetButton = new Button("Reset Points");
add(ResetButton);
ResetButton.addActionListener(this);
RandomButton = new Button("Uniform Dist");
add(RandomButton);
RandomButton.addActionListener(this);
NormalRandomButton = new Button("Normal Dist");
add(NormalRandomButton);
NormalRandomButton.addActionListener(this);
add(new Label("Switch mode:"));
NNButton = new Button("Nearest Neighbor");
add(NNButton);
NNButton.addActionListener(this);
add(new Label("Simulate a 1000 random tests points:"));
SimButton = new Button("Go Simulation!!!");
add(SimButton);
SimButton.addActionListener(this);
add(MessageText);
}
public void destroy()
{
remove(canvas);
}
public void paint(Graphics g)
{
Rectangle bound = getBounds();
g.setColor(Color.lightGray);
g.draw3DRect(0, 0, bound.width-1, bound.height-1, true);
}
public void actionPerformed(ActionEvent e)
{
if(e.getSource() == ResetButton)
{
MessageText.setText("Points reset");
canvas.resetPoints();
}
else if(e.getSource() == SimButton)
{
canvas.DoSimulation();
}
else if(e.getSource() == RandomButton)
{
MessageText.setText("Random Points generated");
canvas.randomPoints(100);
}
else if(e.getSource() == NormalRandomButton)
{
MessageText.setText("Normal Random points generated");
canvas.normalRandomPoints(100);
}
else if(e.getSource() == NNButton)
{
if(canvas.getClickMode() == DrawCanvas.ADDPOINTS)
{
MessageText.setText("Search mode");
canvas.setClickMode(DrawCanvas.FINDNEAREST);
NNButton.setLabel("Edit Points");
ResetButton.setEnabled(false);
RandomButton.setEnabled(false);
NormalRandomButton.setEnabled(false);
}
else
{
MessageText.setText("Edit mode");
canvas.setClickMode(DrawCanvas.ADDPOINTS);
NNButton.setLabel("Nearest Neighbor");
ResetButton.setEnabled(true);
RandomButton.setEnabled(true);
NormalRandomButton.setEnabled(true);
}
}
else if(e.getSource() == AddNNButton)
{
canvas.setKN(canvas.getKN()+1);
knnText.setText(String.valueOf(canvas.getKN()));
}
else if(e.getSource() == RemoveNNButton)
{
canvas.setKN(canvas.getKN()-1);
knnText.setText(String.valueOf(canvas.getKN()));
}
}
public String getAppletInfo()
{
return "A simple drawing program.";
}
}
class DrawCanvas extends Canvas implements MouseListener
{
// Define the constant we will need
public static final int FINDNEAREST = 0;
public static final int ADDPOINTS = 1;
// Nearest Neighbor finder
NNFinder nnfind;
int kn;
// Flag to indicate the mode of operation (state)
int mode;
boolean DrawAllFlag;
// Dynamic array of points
Vector points;
// Current point (for nearest neighbor)
Point point;
TextField MessageText;
TextField nPointText;
public DrawCanvas(TextField mtext, TextField nptstext)
{
mode = ADDPOINTS;
DrawAllFlag = false;
points = new Vector();
MessageText = mtext;
nPointText = nptstext;
kn = 1;
setBackground(Color.white);
addMouseListener(this);
}
public void setKN(int k)
{
if(k > 0 && k < points.size()) kn = k;
}
public int getKN()
{
return kn;
}
public void setClickMode(int newmode)
{
// Erase the current point
point = null;
mode = newmode;
if(mode == FINDNEAREST)
{
nnfind = new NNFinder(points);
}
// Redraw all the DrawPanel
DrawAllFlag = true;
repaint();
}
public void DoSimulation()
{
Dimension dim = getSize();
Point pc, point;
int k, i;
double res = 0.0, brute;
nnfind = new NNFinder(points);
for(i=0; i < 1000; i++)
{
point = new Point( (int)(Math.random()*(double)dim.width),
(int)(Math.random()*(double)dim.height));
// Find the first nearest neighbor
pc = nnfind.FindFirstNN(point);
if(kn > 1)
{
for(k = 1; k < kn; k++)
// Find the next nearest neighbor
pc = nnfind.FindNextNN();
}
res += (double)nnfind.getCompare();
}
res /= 1000.0;
// We compute the brute force number
for(k=0,brute=0.0; k < kn; k++) brute += (double)(nnfind.ndata - k);
MessageText.setText("Average Number Of Compare: "+(int)res+"/"+(int)brute+" ("
+ (int)(res*100/brute)+"%)");
}
public int getClickMode()
{
return mode;
}
public void resetPoints()
{
points.removeAllElements();
point = null;
DrawAllFlag = true;
// Update the number of point text field
nPointText.setText("0");
repaint();
}
public void randomPoints(int npts)
{
Dimension dim = getSize();
int npoints = points.size();
//points.removeAllElements();
points.ensureCapacity(npoints+npts);
for(int i = 0; i < npts; i++)
{
Point p = new Point((int)(Math.random()*(double)dim.width),
(int)(Math.random()*(double)dim.height));
points.addElement(p);
}
// Set the redraw of all points
DrawAllFlag = true;
point = null;
// Update the number of point text field
nPointText.setText(String.valueOf(npoints+npts));
repaint();
}