THREE.js | FALL 2016

Interactive Implementation of Graham Scan Algorithm for Convex Hulling and using this to understand the interaction of virtual ant clusters.


Screen Shot 2017-01-23 at 11.19.29 AM.png

So lay down a table. Collect ants from different localities, probably color tag them. Now leave all of them on a table. Figure out how much do they interact and mix?

This simulation was made to virtually visualize this phenomenon.


STEP 1: Select a set of N random points, points_array in a rectangle bound area.

Screen Shot 2017-01-23 at 11.36.54 AM.png

STEP 2: Find the point with y_coord_min_index as the index which has the minimum y coordinate in the array points_array.

Screen Shot 2017-01-23 at 11.37.16 AM.png

STEP 3 : Exchange the 1st element in points_array, points_array[0] with the minimum y coordinate point,  points_array[y_coord_min_index].

Screen Shot 2017-01-23 at 11.37.28 AM.png

STEP4: Sort points_array with the angle/slope points_array[0] (lowest y coordinate) makes with other points.

Screen Shot 2017-01-23 at 11.37.39 AM.png

In the sort, if any point A has 0 slope/ or has the same y as the points_array[0], either make A, points_array[1] or points_array[points_array.length-1].

STEP5: Finding the convex_points_array, which hold the convex hull points from points_array.

Push points_array[0], points_array[1] and points_array[2] in a stack .

Now find if to go from point 1 to point 2 we need to take a left turn or a right turn.

If a right turn, the point stays in the stack else is popped out. Further on, the current point is checked with the previous point in the stack for the same till a right turn is needed.

This iteration is done for all the points in the points_array to make the convex_points_array holding convex hull points.