• Computing Convex Hull for Simple Polygons in O(n)

  Here I implemented Melkman's algorithm from scratch. (description and proof can be found on that link)
  The applet provided on that page, however, has a bug.
  In particular, if first 3 inputed points are colinear from left to right, and the last inputed point is also colinear with the first 3 and to the left of them, the algorithm computes a wrong convex hull (try it).
  The problem is actually that first 4 points of the point-list are colinear from left to right, but this applet inserts points in such a way that the last inputed point will be first in the linked list.
  To fix this, I set the top-left point to be the second point in the list (which also takes O(n) time and does not change asymptotic running time of the algorithm)
  The applet does not allow you to input vertices which would make the polygon non-simple. Even after you close the polygon and compute the convex hull, you can move the points but cannot make the polygon non-simple.
  
  

• Animating Andrew's Algorithm

  This algorithm I also implemented from scratch using pseudo-code from the book.
  While stepping through the algorithm, right turns are represented by green triangles, and left turns by red triangles. The algorithm removes all left turns.
  The algorithm keeps computing the upper hull until all turns are righ turns, then procedes to computing the lower hull. When done, it removes first and last elements of the lower hull and concatenates the two hulls.
  The current state of the algorithm is displayed below the drawing area.
  Instructions for using the applet are next to the applet window.
  
  

• source

Using the applet:

• Tab -- switch between point and polygon input mode
• Delete -- clear the screen
• Mouse left -- insert/select a point
• Shift + Mouse left -- restrict movement of the selected point
  • move horizontaly if clicked inside a 45-degree cone left/right of the point
  • move vertically otherwise
• Mouse right -- delete a point
• Mouse drag -- move the selected point
  • if the dragged point aligns with some other point in x and/or y coordinate, you will see vertical and/or horizontal guide-lines
• Point mode:
  • Space -- switch between edit and run mode
  • Right arrow -- step through the algorithm
  • Left arrow -- restart the algorithm
  • Up arrow -- animate the algorithm step-by-step
  • Down arrow -- run the algorithm all the way (one step)
• Polygon mode:
  • (the applet does not allow you to create self-intersecting polygons)
  • Space:
    • if CH is computed, go back to edit mode
    • else if polygon is closed, compute CH -- O(n)
    • else close the polygon