Convex Hull Algorithm, build from scratch ,using the Monotone-Chain method.

Convex Hull is the minimum boundary of given set of data points. After it calculated, every point in the given set should be inside the hull, or part of its border. To find this hull, we should use proper convex-hull algorithm. The code ch.py is version of such convex hull 2D algorithm that build from scratch.

The algorithm process build from Four steps:

• In order to get the boundary around our 2D points, we must first sorting the points, using to their X values.

• Now, we will divide the calculation, so that it focuses on a different hull each time, once on the top and once on the bottom, as follows:

• We perform the calculation for each such sub-boundary (hull). In order to verify that we choose the desired path, we use invalid function (lambda function). This function identifies for each point if there is a better route to it. When a "better path" means relativity lower slope than the slope to the previous point. You can see such example in the following figure:

  As you can see, the slope between point 7 to 9 is lower then the slope between 7 to 8. So we choose to remove point 8 from the hull.

  These properties converted into an equations, which can be developed into our invalid function:

   Which equal to:

   When in our example, point 7 = (x0,y0), point 8 = (x1,y1) & point 9 = (x2,y2)

• After the calculation of the top & bottom hulls, all we need is merge them to one final hull.

It should be noted that the given example describe calculation of the lower hull. The function also works in the upper case, because we using reverse points list. The order of the coordinates ensures a negative denominator in the slope equation. So the denominator makes the left slope negative and the right positive if there is a better path.

You can also see a simple example of how the calculation is done, in each step of building the hull:

Now, it is also possible to calculate the area of the results hull polygon. The calculation is performed using the following equations, which are used to calculate an irregular polygon area:

When m = number of points in the hull and X&Y coordinates of the hull.

You can see example to area calculation in the following figure. It describe Convex-Hull boundary that created around point that sampled inside Unit-Circle. The actual area of the polygon should be close to pi (3.14) and we can see that the calculate area we get is 3.12:

The object also calculate the perimeter of the hull (length), by sum all the length of each line in the hull, as you can see in the equation:

The Convex-Hull object also can also generated as an output plot of the results, in a simple using of the built-in function:

# load libraries:
import numpy as np
from ch import ConvexH

# create xy coordinates:
points = np.random.normal(0,1,(100,2))

# calculate convex-hull & plot results:
ConvexH(points).plot()

The code uses the following library in Python:

matplotlib

An application of the code is attached to this page under the name:

implementation.py

The examples and the outputs are also attached here: examples & outputs.

To use this code, you just need to import it as follows:

# load libraries:
import numpy as np
from ch import ConvexH

# create xy coordinates:
points = np.random.normal(0,1,(100,2))

# calculate convex-hull get the hull boundary:
hull = ConvexH(points).vertex

When the variables displayed are:

points: list or array of 2D x,y coordinates

MIT © Etzion Harari