THREE.js | FALL 2016

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

**IDEATION AND DEVELOPMENT PROCESS**

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.

#### PROCESS

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

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

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

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

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.