fortune.pde

import java.util.*;
ArrayList<Point> pts = new ArrayList<Point>();

public class EventComp implements Comparator 
{
  public int compare(Object e1, Object e2) 
  {
      if (((fEvent)e1).loc.y < ((fEvent)e2).loc.y)
        return 1;
      else if (((fEvent)e1).loc.y == ((fEvent)e2).loc.y)
        return 0;
      return -1;
  }
}

public class fEvent
{
  boolean SITE;//event type: is it a site event?
  Point loc,cc;
  Point a,b,c;
  public fEvent(Point _loc)
  {
    SITE = true;
    loc = _loc;
  }
  public fEvent(Point _a, Point _b, Point _c)
  {
    SITE = false;
    loc = eventPoint(_a,_b,_c);
    cc = circumCenter2(_a,_b,_c);
    a=_a;  b=_b;  c=_c;
  }
  Point eventPoint(Point a, Point b, Point c)
  {
    float mr = (b.y-a.y) / (b.x-a.x);
    float mt = (c.y-b.y) / (c.x-b.x);
    float x = (mr*mt*(c.y-a.y) + mr*(b.x+c.x) - mt*(a.x+b.x)) / (2*(mr-mt));
    float y = (a.y+b.y)/2 - (x - (a.x+b.x)/2) / mr;
    float r = sqrt(((b.x-x)*(b.x-x) +  (b.y-y)*(b.y-y)));
    //noFill();
    //ellipse(x,y,2*r,2*r);
    
    return new Point(x, y-r);//returns event point
  }
  Point circumCenter2(Point a, Point b, Point c)
  {
    float mr = (b.y-a.y) / (b.x-a.x);
    float mt = (c.y-b.y) / (c.x-b.x);
    float x = (mr*mt*(c.y-a.y) + mr*(b.x+c.x) - mt*(a.x+b.x)) / (2*(mr-mt));
    float y = (a.y+b.y)/2 - (x - (a.x+b.x)/2) / mr;
    float r = sqrt(((b.x-x)*(b.x-x) +  (b.y-y)*(b.y-y)));
    return new Point(x, y);//return circumcenter
  }
}

class Point
{
  float x, y;
  public Point(float _x, float _y)
  {
    x = _x; y = _y;
  }
  boolean equals(Point b)
  {
    return abs(b.x - x) < EPSILON && abs(b.y - y) < EPSILON; 
  }
}

class BeachLine
{
  ArrayList<Point> shore = new ArrayList<Point>();
  
  Point insert(Point p)
  {
    if(shore.size()==0)
    {
      shore.add(p);
      return null;
    }
    float minY = (float)10E9;
    Point parent = shore.get(0);
    //find the intersecting parabola on the shore.
    for(int i= 0; i < shore.size(); i++)
    {
      Point q = shore.get(i);
      float iy = ((p.x-q.x)*(p.x-q.x) + q.y*q.y - sl*sl)/(2*(q.y-sl));

      if(iy < minY)
      {
        minY = iy;
        parent = q;
      }
      //this.draw();
    }
    //pushStyle();
    //fill(0,200,0);
    //ellipse(p.x, minY, 15,15);
    //popStyle();
    //update the shore
    for(int i =0; i < shore.size(); i++)
    {
      if(shore.get(i).equals(parent))
      {
        shore.add(i+1, p);
        shore.add(i+2, parent);
        break;
      }
    }
    return parent;
  }
  void draw()
  {
    for(Point q : shore)
    {
      pushStyle();
      fill(200,0,0);
      noStroke();
      for(float j = 0; j < width; j+=5)
      {
        float iy = ((j-q.x)*(j-q.x) + q.y*q.y - sl*sl)/(2*(q.y-sl));
        ellipse(j, iy, 5, 5);
      }
      popStyle();
    }
  }
  ArrayList<fEvent> getNewEvents(Point p)
  {
    ArrayList<fEvent> res = new ArrayList<fEvent>();
    for(int i = 0; i < shore.size(); i++)
    {
      if(shore.get(i).equals(p))
      {
        if(i >= 2)
          res.add(new fEvent(shore.get(i-2), shore.get(i-1), p));
        //if(i >= 1 && shore.size() > i+1)
        //  res.add(new fEvent(shore.get(i-1), p, shore.get(i+1)));
        if(shore.size() > i+2)
          res.add(new fEvent(p, shore.get(i+1), shore.get(i+2)));
        break;
      }
    }
    for(int i= 0; i < res.size(); i++)
    {
      if(res.get(i).loc.y > sl)
      {
        res.remove(i);
        i--;
      }
    }
    return res;
  }
  
  void remove(Point a, Point b, Point c)
  {
    for(int i= 0; i < shore.size()-3; i++)
    {
      if(shore.get(i).equals(a) && shore.get(i+1).equals(b) && shore.get(i+2).equals(c))
      {
        shore.remove(i+1);
        return;
      }
    }
  }
  
  void print()
  {
    println(shore.size());
    for(int i= 0; i < shore.size(); i++)
    {
      System.out.print("(" + shore.get(i).x + "," + shore.get(i).y + ")");
    }
    println();
  }
}

float sl = 0; //sweep line y

class EventQueue
{
  ArrayList<fEvent> pq = new ArrayList<fEvent>();
  void add(fEvent e)
  {
    pq.add(0, e);
    Collections.sort(pq, new EventComp());
  }
  fEvent poll()
  {
    return pq.remove(0);
  }
  
  void rmCircEvents(Point p)
  {
    //remove any circle event point involving p from eventqueue
    for(int i =0; i < pq.size(); i++)
    {
      fEvent fe = pq.get(i);
      if(!fe.SITE && (fe.a.equals(p) || fe.b.equals(p) || fe.c.equals(p)))
      {
        pq.remove(i);
      }
    }
  }
  
  int size()
  {
    return pq.size();
  }
}

void work()
{
  EventQueue eq = new EventQueue();
  sl = 0;

  for(Point p : pts)
    eq.add(new fEvent(p));
  
  BeachLine bl = new BeachLine();
  int x = 0;
  while(eq.size()>0)
  {
    fEvent next = eq.poll();
    sl = next.loc.y;
    x++;
    //strokeWeight(x);
    
    //line(0,sl,800,sl);
    if(next.SITE)
    {
      Point check = bl.insert(next.loc);     
      //remove circle events the involve the parab we added to
      eq.rmCircEvents(check);
      //add new circle events involving next
      ArrayList<fEvent> newCircEvents = bl.getNewEvents(next.loc);
      println("N:"  + newCircEvents.size());
      for(fEvent e : newCircEvents)
        eq.add(e);
    }
    else
    {
      //add new vertex
      Point v = next.cc;
      pushStyle();
      fill(100);
      ellipse(v.x, v.y, 20,20);
      popStyle();
      bl.remove(next.a, next.b, next.c);//remove parabola that was here
      //ellipse(next.b.x, next.b.y, 30, 30);
      //bl.draw();
    }
    bl.print();
  }
}

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

void setup(){size(800,800);}
void draw(){}
void mouseReleased()
{
  pts.add(new Point(mouseX, mouseY));
  ellipse(mouseX, mouseY, 10, 10);
}
void keyReleased()
{
  if(key=='f')
    work();
}