Title : Convex Hull algorithm Animation

Authors : Ji-Mo Jung (Á¤Áö¸ð)

Date : Jun 9, 2004

Aim : Showing how to find convex hull from some random points (using Graham's scan)

Background : Java & ciips

'ciips' is framework of Java platform. It has framework of data handling, thread, user interface objects.

Experimental Method :

class ConvexHullAlgThread :

implementation of graphic method & finding hull algorithm

run() :

main job thread

    1. init_points() : 

make some random points and draw it (blue points)

    2. set_pivot() :

find pivot point (represent red line)

    3. sort_points() :

sorting points by quicksort (represent sorting of angles & spokes)

    4. make_hull() :

make the hull (represent drawing the red edge)

init():

initialize framework

show_all(Graphics g) :

repaint the panel (drawing objects)

ConvexHullAlgThread(AlgAnimFrame frame) :

starting point

Conclusion :

The algorithm works in three phases:

1. Find an pivot point. This point will be the pivot and guaranteed to be on the hull. It is chosen to be the point with smallest y coordinate.
2. Sort the points in order of increasing angle to the pivot. Draw star-shaped polygon (one to pivot)
3. Build the hull, by scanning around the star-shaped polygon, adding edges when we make a left turn, and back-tracking when we make a right turn.