play with intersections of lines (unfinish)

AVLTree.pde

abstract class Node {
  Node left;
  Node right;
  Object element;

  int height;

  private Node() {
  }

  Node(Object element) {
    this.init(element, null, null);
  }

  Node(Object element, Node left, Node right) {
    this.init(element, left, right);
  }

  private void init(Object element, Node left, Node right) {
    this.element = element;
    this.left = left;
    this.right = right;
    this.height = 0;
  }

  abstract public int compare(Node n);
  abstract public void print();
}

class AVLTree {

  private Node root;

  AVLTree() {
    root = null;
  }

  public void insert(Node x) {
    root = insert(x, root);
  }

  public void remove(Node x) {
    remove(x, root);
  }

  public boolean isEmpty() {
    return root==null;
  }

  public Node findMin() {
    if (isEmpty()) {
      return null;
    }

    return findMin(root);
  }

  public void printTree() {
    printTree(root);
  }

  private Node insert(Node node, Node parent) {
    if (parent==null) {
      return node;
    }
    switch(node.compare(parent)) {
    case -1:
      parent.left = insert(node, parent.left);
      if (height(parent.left)-height(parent.right)==2)
        if (node.compare(parent.left)<0)
          parent = rotateWithLeftChild(parent);
        else
          parent = doubleWithLeftChild(parent);
      break;
    case 1:
      parent.right = insert(node, parent.right);
      if (height(parent.right)-height(parent.left)==2)
        if (node.compare(parent.right)>0)
          parent = rotateWithRightChild(parent);
        else
          parent = doubleWithRightChild(parent);
      break;
    default:
      // 0: do nothing
    }

    parent.height = max(height(parent.left), height(parent.right))+1;
    return parent;
  }

  private void remove(Node node, Node parent) {
    if (parent==null)
      return;
      
  }

  private int height(Node node) {
    return node==null?-1:node.height;
  }

  private Node rotateWithLeftChild(Node node) {
    Node left = node.left;
    node.left = left.right;
    left.right = node;
    node.height = max(height(node.left), height(node.right))+1;
    left.height = max(height(left.left), height(node))+1;
    return left;
  }

  private Node rotateWithRightChild(Node node) {
    Node right = node.right;
    node.right = right.left;
    right.left = node;
    node.height = max(height(node.left), height(node.right))+1;
    right.height = max(height(right.right), height(node))+1;
    return right;
  }

  private Node doubleWithLeftChild(Node node) {
    node.left = rotateWithRightChild(node.left);
    return rotateWithLeftChild(node);
  }

  private Node doubleWithRightChild(Node node) {
    node.right = rotateWithLeftChild(node.right);
    return rotateWithRightChild(node);
  }

  private Node findMin(Node node) {
    if (node==null)
      return node;

    while (node.left!=null)
      node = node.left;
    return node;
  }

  private void printTree(Node node) {
    if (node!=null) {
      node.print();
      printTree(node.left);
      printTree(node.right);
    }
  }
}

Entity2D.pde

class Point2D {
  public int x, y;
  Point2D(int x, int y) {
    this.x = x;
    this.y = y;
  }
}

class Line2D {
  public Point2D start, end;
  Line2D(Point2D s, Point2D e) {
    this.start = s;
    this.end = e;
  }

  public Point2D getUpPoint() {
    if (start.y<end.y) {
      return start;
    } else if (start.y==end.y) {
      if (start.x<=end.x) {
        return start;
      }
    }
    return end;
  }
  
   public Point2D getDownPoint() {
    if (start.y<end.y) {
      return end;
    } else if (start.y==end.y) {
      if (start.x<end.x) {
        return end;
      }
    }
    return start;
  }
}

EventNode.pde

static class PointType {
  static final int UKNOWN_TYPE = 0;
  static final int UP_POINT = 1;
  static final int INTERSECTION_POINT = 2;
  static final int DOWN_POINT = 3;
}

class EventNode extends Node {

  Point2D element;

  int type = PointType.UKNOWN_TYPE;
  ArrayList<Line2D> lines;

  EventNode(Point2D point) {
    this.init(point, PointType.UKNOWN_TYPE);
  }

  EventNode(Point2D point, int type) {
    this.init(point, type);
  }

  EventNode(Line2D line, int type) {
    switch(type) {
    case PointType.UP_POINT:
      this.init(line.getUpPoint(), type);
      lines.add(line);
      break;
    case PointType.DOWN_POINT:
      this.init(line.getDownPoint(), type);
      break;
    default:
      println("Wrong point type!");
    }
  }

  private void init(Point2D point, int type) {
    this.element = point;
    this.type = type;
    this.lines = new ArrayList<Line2D>();
  }

  public int compare(Node node) {
    return compare((EventNode)node);
  }

  // order by y,x
  public int compare(EventNode node) {
    //    node = node;
    if (element.y<node.element.y) {
      return -1;
    } else if (element.y==node.element.y) {
      if (element.x<node.element.x) {
        return -1;
      } else if (element.x==node.element.x) {
        if (type==node.type) {
          if (type==PointType.UP_POINT) {
            node.merge(this);
            return 0;
          }
        } else if (type==PointType.UP_POINT) {
          return -1;
        }
      }
    }
    return 1;
  }

  public void print() {
    fill(255, 0, 0);
    ellipse(element.x, element.y, 3, 3);
  }

  private void merge(EventNode node) {
    println(this.lines.size()+" "+node.lines.size());
    this.lines.addAll(node.lines);
    println(this.lines.size());
  }
}

Test.pde

AVLTree eventQueue, statusQueue;
ArrayList<Line2D> lines;
Point2D eventPoint;

void setup() {
  size(640, 480);
  lines = new ArrayList<Line2D>();
}

void draw() {
  background(200);

  for (Line2D line : lines) {
    Point2D start = line.getUpPoint();
    Point2D end = line.getDownPoint();
    line(start.x, start.y, end.x, end.y);
    noFill();
    ellipse(start.x, start.y, 7, 7);
    fill(0);
    ellipse(end.x, end.y, 7, 7);
  }
  
  // dragging line
  if (point_end!=null)
    line(point_start.x, point_start.y, point_end.x, point_end.y);

  // AVLTree
  if (eventQueue!=null) {
    eventQueue.printTree();
  }
  
  // eventPoint
  if (eventPoint!=null) {
    fill(0, 255, 0);
    ellipse(eventPoint.x, eventPoint.y, 5, 5);
  }
}

//enum LineStatus {
//  line_start, 
//  line_end
//}
//
//LineStatus line_start = line_end;
Point2D point_start, point_end;

void mouseMoved() {
}

// create a start point
void mousePressed() {
  point_start = new Point2D(mouseX, mouseY);
}

// remove last line by decreasing index
void mouseClicked() {
  if (eventQueue!=null && !eventQueue.isEmpty()) {
    EventNode e = (EventNode)eventQueue.findMin();
    eventPoint = e.element;
    handleEventPoint(e);
  }
}

// create a end point with mouse coordinate
void mouseDragged() {
  point_end = new Point2D(mouseX, mouseY);
}

// create a line with start point and end point
void mouseReleased() {
  // break if mouse click
  if (point_end==null)
    return;

  lines.add(new Line2D(point_start, point_end));

  // remove start point and end point
  point_start = point_end = null;

  buildAVLTree();
}

void keyReleased() {
  switch(key) {
  case 'd':
    println("breakpoint");
    break;
  case 'r':
    if (lines.size()>0)
      lines.remove(0);
    buildAVLTree();
    break;
  default:
  }
}

void buildAVLTree() {
  eventQueue = new AVLTree();
  for (Line2D line : lines) {
    eventQueue.insert(new EventNode(line, PointType.UP_POINT));
    eventQueue.insert(new EventNode(line, PointType.DOWN_POINT));
  }
}

void handleEventPoint(EventNode node){
  eventQueue.remove(node);
}