convex hull with AVLTree, demo: http://studio.sketchpad.cc/sp/pad/view/ro.9Da4TMdejnS2I/latest
import java.util.Iterator;
AVLTree pointSet;
AVLIterator iterator;
ArrayList<Point2D> convex_hull, convex_hull_up, convex_hull_down;
void setup() {
size(640, 480);
// initial AVLTree
pointSet = new AVLTree();
convex_hull = new ArrayList<Point2D>();
convex_hull_up = new ArrayList<Point2D>();
convex_hull_down = new ArrayList<Point2D>();
}
void draw() {
}
void mouseClicked() {
background(200);
}
void mousePressed() {
pointSet.makeEmpty();
}
void mouseDragged() {
Point2D p = new Point2D(mouseX, mouseY);
pointSet.insert(p);
point(mouseX, mouseY);
}
void mouseReleased() {
if (pointSet.isEmpty())
return;
// strokeWeight(1);
pointSet.printTree();
convex_hull.clear();
convex_hull_up.clear();
convex_hull_down.clear();
iterator = new AVLIterator(pointSet);
Node i = iterator.getBegin();
Point2D p = (Point2D)i.element;
convex_hull_up.add(p);
while (iterator.hasNext ()) {
i = iterator.next();
p = (Point2D)i.element;
convex_hull_up.add(p);
int total;
while ( (total = convex_hull_up.size ())>2) {
if (isOnTheRight(convex_hull_up.get(total-1), convex_hull_up.get(total-2), convex_hull_up.get(total-3))) {
break;
}
convex_hull_up.remove(total-2);
}
}
p = (Point2D)i.element;
ellipse(p.x, p.y, 10, 10);
convex_hull_down.add(p);
while (iterator.hasPrevious ()) {
i = iterator.previous();
p = (Point2D)i.element;
convex_hull_down.add(p);
int total;
while ( (total = convex_hull_down.size ())>2) {
if (isOnTheRight(convex_hull_down.get(total-1), convex_hull_down.get(total-2), convex_hull_down.get(total-3))) {
break;
}
convex_hull_down.remove(total-2);
}
}
convex_hull.addAll(convex_hull_up);
convex_hull.addAll(convex_hull_down);
fill(255);
// strokeWeight(2);
stroke(0);
Iterator<Point2D> iter = convex_hull.iterator();
Point2D lastPoint = null;
while (iter.hasNext ()) {
Point2D point = iter.next();
if (lastPoint!=null)
line(lastPoint.x, lastPoint.y, point.x, point.y);
lastPoint = point;
}
}
boolean isOnTheRight(Point2D p, Point2D q, Point2D r)
{
return q.x*r.y+p.x*q.y+p.y*r.x-q.y*r.x-p.x*r.y-p.y*q.x>0;
}
void keyReleased() {
switch(key) {
case 'r':
mousePressed();
mouseClicked();
break;
case'a':
mouseClicked();
mouseDragged();
mouseReleased();
break;
case 's':
mouseReleased();
break;
case 'c':
mouseClicked();
break;
case 'b':
println("for breakpoint");
break;
}
}
class Point2D implements Comparable {
float x;
float y;
Point2D(float x, float y) {
this.x = x;
this.y = y;
}
int compareTo(Object o) {
return compareToPoint2D((Point2D)o);
}
private int compareToPoint2D(Point2D p) {
if (abs(this.x-p.x)<0.001) {
if (abs(this.y-p.y)<0.001)
return 0; else
return this.y<p.y?-1:1;
}
return this.x<p.x?-1:1;
}
String toString() {
return "("+x+", "+y+")";
}
}
class Node {
// content element
Comparable element;
// tree construction
int height;
Node left;
Node right;
Node parent;
Node() {
init(null, null, null, null);
}
Node(Comparable e) {
init(e, null, null, null);
}
Node(Comparable e, Node parent) {
init(e, parent, null, null);
}
Node(Comparable e, Node parent, Node left, Node right) {
init(e, parent, left, right);
}
void init(Comparable e, Node parent, Node left, Node right) {
this.element = e;
this.parent = parent;
this.left = left;
this.right = right;
this.height = 0;
}
}
class AVLTree {
Node root;
int size;
AVLTree() {
init(null);
}
AVLTree(Node r) {
init(r);
}
private void init(Node r) {
this.root =r;
size = 0;
}
int height(Node node) {
return node==null?0:node.height;
}
boolean isEmpty() {
return root == null;
}
void makeEmpty() {
root = null;
size = 0;
}
Node findMin(Node node) {
if (node==null) return null;
else if (node.left==null) return node;
else return findMin(node.left);
}
Node findMax(Node node) {
if (node==null) return null;
else if (node.right==null) return node;
else return findMax(node.right);
}
void printTree() {
if (isEmpty()) {
println("Empty tree");
return;
}
else {
fill(0);
printTree(root, null);
}
}
void printTree(Node node, Node parent) {
if (node != null) {
Point2D p = (Point2D)node.element;
noStroke();
ellipse(p.x, p.y, 7, 7);
if (parent != null) {
Point2D q = (Point2D)parent.element;
stroke(map(parent.height,10,0,128,200));
line(q.x, q.y, p.x, p.y);
stroke(32);
noFill();
ellipse(q.x,q.y,9,9);
}
fill(255, 0, 0);
printTree(node.left, node);
fill(0, 255, 0);
printTree(node.right, node);
fill(255);
}
}
void insert(Comparable element) {
root = insert(element, root, null);
}
Node insert(Comparable element, Node node, Node parent) {
if (node == null) {
size++;
node = new Node(element, parent);
}
else if (element.compareTo(node.element) < 0) {
node.left = insert(element, node.left, node);
if (height(node.left) - height(node.right) == 2) {
if (element.compareTo(node.left.element) < 0) {
// LL
node = rotateWithLeftChild(node);
}
else {
// LR
node = doubleRotateWithLeftChild(node);
}
}
}
else if (element.compareTo(node.element) > 0) {
node.right = insert(element, node.right, node);
if (height(node.right) - height(node.left) == 2) {
if (element.compareTo(node.right.element) < 0) {
// RL
node = doubleRotateWithRightChild(node);
}
else {
// RR
node =rotateWithRightChild(node);
}
}
}
else {
// duplicate;
}
node.height = max(height(node.left), height(node.right)) + 1;
return node;
}
Node rotateWithLeftChild(Node k2) {
Node k1 = k2.left;
if(k1.right!=null)
k1.right.parent = k2;
k2.left = k1.right;
k1.parent = k2.parent;
k2.parent = k1;
k1.right = k2;
k2.height = max(height(k2.left), height(k2.right)) + 1;
k1.height = max(height(k1.left), k2.height) + 1;
return k1;
}
Node rotateWithRightChild(Node k1) {
Node k2 = k1.right;
if(k2.left!=null)
k2.left.parent = k1;
k1.right = k2.left;
k2.parent = k1.parent;
k1.parent = k2;
k2.left = k1;
k1.height = max(height(k1.left), height(k1.right)) + 1;
k2.height = max(k1.height, height(k2.right)) + 1;
return k2;
}
Node doubleRotateWithLeftChild(Node k3) {
k3.left = rotateWithRightChild(k3.left);
return rotateWithLeftChild(k3);
}
Node doubleRotateWithRightChild(Node k3) {
k3.right = rotateWithLeftChild(k3.right);
return rotateWithRightChild(k3);
}
}
class AVLIterator {
AVLTree tree;
Node begin;
Node end;
Node current;
AVLIterator(AVLTree t) {
this.tree = t;
current = begin = t.findMin(t.root);
end = t.findMax(t.root);
}
Node getBegin() {
current = begin;
return current;
}
Node getEnd() {
current = end;
return current;
}
boolean hasNext() {
return current!=end;
}
Node next() {
if (hasNext()) {
if (current.right!=null) {
current = tree.findMin(current.right);
}
else if (current.parent!=null) {
while (current==current.parent.right) {
current=current.parent;
}
current=current.parent;
}
else {
// error;
}
}
else {
return null;
}
return current;
}
boolean hasPrevious() {
return current!=begin;
}
Node previous() {
if (hasPrevious()) {
if (current.left!=null) {
current = tree.findMax(current.left);
}
else if (current.parent!=null) {
while (current==current.parent.left) {
current=current.parent;
}
current=current.parent;
}
else {
// error;
}
}
else {
return null;
}
return current;
}
}