///////////////////////////////////////////////////////////
// Editing Nearest Neighbor decision rule using          //
// Voronoi diagram, Gabriel graph or Relative Neighbor   //
// graph.                                                //
//                                                       //
// Sergei Savchenko (savs@cs.mcgill.ca)                  //
///////////////////////////////////////////////////////////

import java.awt.*;
import java.lang.Math;

///////////////////////////////////////////////////////////
// Representation for a line.                            //
///////////////////////////////////////////////////////////

class Line
{
 private double a,b,c;
 private double inter_x,inter_y;

 // Construct a line perpendicular to a vector N: N(X-O)=0
 // Nx(x-Ox)+Ny(y-Oy)=0
 // Nxx-NxOx+Nyy-NyOy=0
 // A=Nx B=Ny C=-NxOx-NyOy

 Line(double x1,double y1,double x2,double y2)
 {
  double ox=(x1+x2)/2,oy=(y1+y2)/2;
  double nx=x2-x1,ny=y2-y1;
  a=nx; b=ny; c=-nx*ox-ny*oy;
 }

 // Seeking intersection of two lines: |A1 B1||x| = |C1|
 //                                    |A2 B2||y|   |C2|
 //                     |A1 B1|
 //  no solution if det |A2 B2| =0
 //  otherwise by Cramer's rule:
 //
 //          |C1 B1|       |B2 A2|
 //  x = det |C2 B2| / det |B1 A1|
 //
 //          |A1 C1|       |B2 A2|
 //  y = det |A2 C2| / det |B1 A1|

 boolean intersection(Line l)
 {
  double det;

  if((det=a*l.b - l.a*b)==0.0) return(false);
  else
  {
   inter_x=-(c*l.b - l.c*b)/det;
   inter_y=-(a*l.c - l.a*c)/det;
   return(true);
  }
 }

 double intersection_x() { return(inter_x); }
 double intersection_y() { return(inter_y); }
}

///////////////////////////////////////////////////////////
// Representation for a Diagram.                         //
///////////////////////////////////////////////////////////

class Diagram
{
 public String status;
 public int size;
 public int nodes_x[],nodes_y[],nodes_kind[];
 public double nodes_xd[],nodes_yd[];
 public boolean nodes_viable[];
 public int no_nodes;
 public int mid_x[],mid_y[],v1[],v2[],v3[];
 public int t1[],t2[],t3[];
 public boolean c1[],c2[],c3[];
 public int no_mid;
 public int dis_x,dis_y;
 public int g1[],g2[];
 public int no_gab;

 Diagram(int sz)
 {
  status="";
  size=sz;
  no_nodes=0;

  nodes_x=new int[size];
  nodes_y=new int[size];
  nodes_xd=new double[size];
  nodes_yd=new double[size];

  nodes_kind=new int[size];
  nodes_viable=new boolean[size];

  mid_x=new int[size]; mid_y=new int[size];
  v1=new int[size]; v2=new int[size]; v3=new int[size];
  t1=new int[size]; t2=new int[size]; t3=new int[size];
  c1=new boolean[size]; c2=new boolean[size]; c3=new boolean[size];
  no_mid=0;
  g1=new int[size]; g2=new int[size];
  no_mid=0;
 }

 void empty()
 {
  no_nodes=0;
  no_mid=0;
  no_gab=0;
 }

 void reset() { no_mid=0; no_gab=0; }

 void show_voronoi(Graphics g)
 {
  int i;

  for(i=0;i<no_nodes;i++)
  {
   g.setColor(Color.red);
   if(!nodes_viable[i]) g.drawOval(nodes_x[i]-5,nodes_y[i]-5,11,11);
   g.setColor(Color.black);
   if(nodes_kind[i]==0) g.drawRect(nodes_x[i]-3,nodes_y[i]-3,7,7);
   else g.fillOval(nodes_x[i]-3,nodes_y[i]-3,7,7);
   g.drawString(" "+i,nodes_x[i],nodes_y[i]);
  }

  for(i=0;i<no_mid;i++)
  {
   g.setColor(Color.gray);

   g.drawLine(nodes_x[v1[i]],nodes_y[v1[i]],nodes_x[v2[i]],nodes_y[v2[i]]);
   g.drawLine(nodes_x[v2[i]],nodes_y[v2[i]],nodes_x[v3[i]],nodes_y[v3[i]]);
   g.drawLine(nodes_x[v3[i]],nodes_y[v3[i]],nodes_x[v1[i]],nodes_y[v1[i]]);

   if(c1[i]) g.setColor(Color.red); else g.setColor(Color.black);
   if(t1[i]!=-1)
    g.drawLine(mid_x[i],mid_y[i],mid_x[t1[i]],mid_y[t1[i]]);
   else
   {
    computeDistance(v1[i],v2[i],v3[i],mid_x[i],mid_y[i]);
    g.drawLine(mid_x[i],mid_y[i],dis_x,dis_y);
   }

   if(c2[i]) g.setColor(Color.red); else g.setColor(Color.black);
   if(t2[i]!=-1)
    g.drawLine(mid_x[i],mid_y[i],mid_x[t2[i]],mid_y[t2[i]]);
   else
   {
    computeDistance(v2[i],v3[i],v1[i],mid_x[i],mid_y[i]);
    g.drawLine(mid_x[i],mid_y[i],dis_x,dis_y);
   }

   if(c3[i]) g.setColor(Color.red); else g.setColor(Color.black);
   if(t3[i]!=-1)
    g.drawLine(mid_x[i],mid_y[i],mid_x[t3[i]],mid_y[t3[i]]);
   else
   {
    computeDistance(v3[i],v1[i],v2[i],mid_x[i],mid_y[i]);
    g.drawLine(mid_x[i],mid_y[i],dis_x,dis_y);
   }
  }
 }

 void show_graph(Graphics g)
 {
  int i;

  for(i=0;i<no_nodes;i++)
  {
   g.setColor(Color.red);
   if(!nodes_viable[i]) g.drawOval(nodes_x[i]-5,nodes_y[i]-5,11,11);
   g.setColor(Color.black);
   if(nodes_kind[i]==0) g.drawRect(nodes_x[i]-3,nodes_y[i]-3,7,7);
   else g.fillOval(nodes_x[i]-3,nodes_y[i]-3,7,7);
   g.drawString(" "+i,nodes_x[i],nodes_y[i]);
  }

  g.setColor(Color.black);
  for(i=0;i<no_gab;i++)
  {
   g.drawLine(nodes_x[g1[i]],nodes_y[g1[i]],nodes_x[g2[i]],nodes_y[g2[i]]);
  }

  for(i=0;i<no_mid;i++)
  {
   g.setColor(Color.red);

   if(c1[i])
    if(t1[i]!=-1)
     g.drawLine(mid_x[i],mid_y[i],mid_x[t1[i]],mid_y[t1[i]]);
    else
    {
     computeDistance(v1[i],v2[i],v3[i],mid_x[i],mid_y[i]);
     g.drawLine(mid_x[i],mid_y[i],dis_x,dis_y);
    }

   if(c2[i])
    if(t2[i]!=-1)
     g.drawLine(mid_x[i],mid_y[i],mid_x[t2[i]],mid_y[t2[i]]);
    else
    {
     computeDistance(v2[i],v3[i],v1[i],mid_x[i],mid_y[i]);
     g.drawLine(mid_x[i],mid_y[i],dis_x,dis_y);
    }

   if(c3[i])
    if(t3[i]!=-1)
     g.drawLine(mid_x[i],mid_y[i],mid_x[t3[i]],mid_y[t3[i]]);
    else
    {
     computeDistance(v3[i],v1[i],v2[i],mid_x[i],mid_y[i]);
     g.drawLine(mid_x[i],mid_y[i],dis_x,dis_y);
    }
  }
 }

 boolean signArea(int v1,int v2,int v3)
 {
  if(((nodes_xd[v1]*(nodes_yd[v2]-nodes_yd[v3])+
       nodes_xd[v2]*(nodes_yd[v3]-nodes_yd[v1])+
       nodes_xd[v3]*(nodes_yd[v1]-nodes_yd[v2]))/2)>=0) return(true);
  else return(false);
 }

 void computeDistance(int v1,int v2,int v3,int mx,int my)
 {
  double dx=nodes_xd[v2]-nodes_xd[v1];
  double dy=nodes_yd[v2]-nodes_yd[v1];
  double lng=200./Math.sqrt(dx*dx+dy*dy);

  if(signArea(v1,v2,v3)) { dis_y=(int)(my-dx*lng); dis_x=(int)(mx+dy*lng); }
  else                   { dis_y=(int)(my+dx*lng); dis_x=(int)(mx-dy*lng); }
 }

 void insert(int x,int y,int kind)
 {
  int i,dx,dy;

  for(i=0;i<no_nodes;i++)
  {
   dx=nodes_x[i]-x;
   dy=nodes_y[i]-y;
   if(Math.sqrt(dx*dx+dy*dy)<3)
   {
    nodes_x[i]=nodes_x[no_nodes-1];
    nodes_xd[i]=nodes_xd[no_nodes-1];
    nodes_y[i]=nodes_y[no_nodes-1];
    nodes_yd[i]=nodes_yd[no_nodes-1];
    nodes_kind[i]=nodes_kind[no_nodes-1];
    nodes_viable[i]=nodes_viable[no_nodes-1];
    no_nodes--;
    return;
   }
  }

  nodes_x[no_nodes]=x;
  nodes_y[no_nodes]=y;
  nodes_xd[no_nodes]=x+Math.random()/5.;
  nodes_yd[no_nodes]=y+Math.random()/5.;
  nodes_kind[no_nodes]=kind;
  nodes_viable[no_nodes++]=true;
 }

 double distance(double ox,double oy,double x,double y)
 {
  return((ox-x)*(ox-x)+(oy-y)*(oy-y));
 }

 void compute_voronoi()
 {
  int i,j,k,l,e1,e2,e3;
  int edges1[]=new int[no_nodes*no_nodes];
  int edges2[]=new int[no_nodes*no_nodes];

  for(i=0;i<no_nodes*no_nodes;i++) edges1[i]=edges2[i]=-1;

  for(i=0;i<no_nodes;i++)
  {
   for(j=i+1;j<no_nodes;j++)
   {
    for(k=j+1;k<no_nodes;k++)
    {
     Line a=new Line(nodes_xd[i],nodes_yd[i],nodes_xd[j],nodes_yd[j]);
     Line b=new Line(nodes_xd[j],nodes_yd[j],nodes_xd[k],nodes_yd[k]);
     if(a.intersection(b))
     {
      double rad=distance(a.intersection_x(),a.intersection_y(),
                          nodes_xd[i],nodes_yd[i]
                         );
      for(l=0;l<no_nodes;l++)
      {
       if((l!=i)&&(l!=j)&&(l!=k)&&(
          distance(a.intersection_x(),a.intersection_y(),
                   nodes_xd[l],nodes_yd[l])<rad)
         ) break;
      }
      if(l==no_nodes)
      {
       int t;

       v1[no_mid]=i; v2[no_mid]=j; v3[no_mid]=k;

       if(i<j) e1=i*no_nodes+j; else e1=j*no_nodes+i;
       if(j<k) e2=j*no_nodes+k; else e2=k*no_nodes+j;
       if(k<i) e3=k*no_nodes+i; else e3=i*no_nodes+k;

       if(edges1[e1]==-1) edges1[e1]=no_mid; else edges2[e1]=no_mid;
       if(edges1[e2]==-1) edges1[e2]=no_mid; else edges2[e2]=no_mid;
       if(edges1[e3]==-1) edges1[e3]=no_mid; else edges2[e3]=no_mid;

       mid_x[no_mid]=(int)a.intersection_x();
       mid_y[no_mid]=(int)a.intersection_y();
       no_mid++;
      }
     }
    }
   }
  }
  for(l=0;l<no_nodes;l++) nodes_viable[l]=false;
  for(l=0;l<no_mid;l++)
  {
   i=v1[l]; j=v2[l]; k=v3[l];

   if(i<j) e1=i*no_nodes+j; else e1=j*no_nodes+i;
   if(j<k) e2=j*no_nodes+k; else e2=k*no_nodes+j;
   if(k<i) e3=k*no_nodes+i; else e3=i*no_nodes+k;

   c1[l]=c2[l]=c3[l]=false;
   if(nodes_kind[i]!=nodes_kind[j])
   { nodes_viable[i]=nodes_viable[j]=true; c1[l]=true; }
   if(nodes_kind[j]!=nodes_kind[k])
   { nodes_viable[j]=nodes_viable[k]=true; c2[l]=true; }
   if(nodes_kind[k]!=nodes_kind[i])
   { nodes_viable[k]=nodes_viable[i]=true; c3[l]=true; }

   if(edges1[e1]!=l) t1[l]=edges1[e1]; else t1[l]=edges2[e1];
   if(edges1[e2]!=l) t2[l]=edges1[e2]; else t2[l]=edges2[e2];
   if(edges1[e3]!=l) t3[l]=edges1[e3]; else t3[l]=edges2[e3];
  }
 }

 void compute_gabriel()
 {
  int i,j,l;

  for(i=0;i<no_nodes;i++)
  {
   for(j=i+1;j<no_nodes;j++)
   {
    double mx=(nodes_xd[i]+nodes_xd[j])/2;
    double my=(nodes_yd[i]+nodes_yd[j])/2;
    double rad=distance(mx,my,nodes_xd[i],nodes_yd[i]);

    for(l=0;l<no_nodes;l++)
    {
     if((l!=i)&&(l!=j)&&(distance(mx,my,nodes_xd[l],nodes_yd[l])<rad)) break;
    }

    if(l==no_nodes)
    {
     g1[no_gab]=i; g2[no_gab++]=j;
    }
   }
  }
  for(l=0;l<no_nodes;l++) nodes_viable[l]=false;
  for(l=0;l<no_gab;l++)
  {
   i=g1[l]; j=g2[l];

   if(nodes_kind[i]!=nodes_kind[j])
   { nodes_viable[i]=nodes_viable[j]=true; }
  }
 }

 void compute_relative()
 {
  int i,j,l;

  for(i=0;i<no_nodes;i++)
  {
   for(j=i+1;j<no_nodes;j++)
   {
    double rad=distance(nodes_xd[i],nodes_yd[i],nodes_xd[j],nodes_yd[j]);

    for(l=0;l<no_nodes;l++)
    {
     if((l!=i)&&(l!=j)&&
        (distance(nodes_xd[i],nodes_yd[i],nodes_xd[l],nodes_yd[l])<rad)&&
        (distance(nodes_xd[j],nodes_yd[j],nodes_xd[l],nodes_yd[l])<rad)
       ) break;
    }

    if(l==no_nodes)
    {
     g1[no_gab]=i; g2[no_gab++]=j;
    }
   }
  }
  for(l=0;l<no_nodes;l++) nodes_viable[l]=false;
  for(l=0;l<no_gab;l++)
  {
   i=g1[l]; j=g2[l];

   if(nodes_kind[i]!=nodes_kind[j])
   { nodes_viable[i]=nodes_viable[j]=true; }
  }
 }

 void delete()
 {
  int i;

  for(i=0;i<no_nodes;i++)
  {
   if(!nodes_viable[i])
   {
    nodes_x[i]=nodes_x[no_nodes-1];
    nodes_xd[i]=nodes_xd[no_nodes-1];
    nodes_y[i]=nodes_y[no_nodes-1];
    nodes_yd[i]=nodes_yd[no_nodes-1];
    nodes_kind[i]=nodes_kind[no_nodes-1];
    nodes_viable[i]=nodes_viable[no_nodes-1];
    no_nodes--; i--;
   }
  }
 }
}

//////////////////////////////////////////////////////////
// The front end.                                        //
///////////////////////////////////////////////////////////

public class VorApplet extends java.applet.Applet
{
 private int node_kind;
 private Diagram vor;
 private Image offscreen;
 private Graphics offgraphics;
 private Dimension offscreensize;
 private int option;

 public void init()
 {
  CheckboxGroup group=new CheckboxGroup();
  vor=new Diagram(512);
  add(new Checkbox("add A node",group,true));
  add(new Checkbox("add B node",group,false));
  add(new Button("Find"));
  add(new Button("Delete"));
  add(new Button("Clear"));
  String str=getParameter("option");
  if(str==null) option=0;
  if("voronoi".equals(str)) option=0;
  if("gabriel".equals(str)) option=1;
  if("relative".equals(str)) option=2;
 }

 public void paint(Graphics g) { repaint(); }

 public void update(Graphics g)
 {
  Dimension d=size();
  if((offscreen==null)||(d.width!=offscreensize.width)||(d.height!=offscreensize.height))
  {
   offscreen=createImage(d.width,d.height);
   offscreensize=d;
   offgraphics=offscreen.getGraphics();
   offgraphics.setFont(getFont());
  }
  offgraphics.setColor(Color.white);
  offgraphics.fillRect(0,0,d.width,d.height);
  offgraphics.setColor(Color.black);
  if(option==0) vor.show_voronoi(offgraphics);
  else vor.show_graph(offgraphics);
  offgraphics.drawString(vor.status,5,35);
  g.drawImage(offscreen,0,0,null);
 }

 public boolean action(Event evt,Object arg)
 {
  if(arg instanceof Boolean)
  {
   if("add A node".equals(((Checkbox)evt.target).getLabel())) node_kind=0;
   else node_kind=1;
   repaint();
   return true;
  }
  if("Find".equals(arg))
  {
   vor.reset();
   vor.compute_voronoi();
   if(option==1) vor.compute_gabriel();
   if(option==2) vor.compute_relative();
   repaint();
   return true;
  }
  if("Delete".equals(arg))
  {
   vor.delete();
   vor.reset();
   vor.compute_voronoi();
   if(option==1) vor.compute_gabriel();
   if(option==2) vor.compute_relative();
   repaint();
   return true;
  }
  if("Clear".equals(arg))
  {
   vor.empty();
   repaint();
   return true;
  }
  return false;
 }

 public boolean mouseDown(Event evt,int x,int y)
 {
  vor.reset();
  vor.insert(x,y,node_kind);
  repaint();
  return(true);
 }
}

///////////////////////////////////////////////////////////