ALGORITHMS AND DATA STRUCTURES
Convex Hull Algorithms
Given a cloud of points on a 2D plane, a convex hull is the smallest set of points which encloses all of the points.
Another useful concept related to convex hulls is the minimum bounded rectangle. The minimum bounded rectangle is the smallest rectangle (measured by area) which encompasses the entire convex hull (by extension, it is also the smallest rectangle that encompasses all points).
The minimum bounded rectangle must have an edge which is co-linear to one of the edges in the convex hull.
The Jarvis March (Gift Wrapping Algorithm)
$$ o = (q_y - p_y)(r_x - q_x) - (q_x - p_x)(r_y - q_y) $$
\(o == 0\)they are co-linear
\(o > 0\)they are clockwise
\(o < 0\)they are counter-clockwise
This equation comes from the 3D definition of the cross-product (for a proof, see here).
- Pick one point that is guaranteed to lie in the convex hull. This can be done by picking the left-most point (i.e. has the lowest x value). If there is more than one point that meets this condition, you are free to choose any one. Add this to the start of list of the
- Pick any other point to be the potential
next_pointon the hull.
- Iterate over all the points, checking the orientation between the
last_pointfound on the hull, the potential
next_point, and the
loop_pointyou are currently iterating over. If the orientation is counter-clockwise, then
loop_pointis to the left the the line formed by between
next_point, and becomes the
- One you reach the end of the loop,
next_pointis guaranteed to be the correct next point on the convex hull. Append this to the
- Repeat steps 2 to 4, until you end up adding the same point to the
convex_hulllist as you started with (the left most point).
scipy provides a
ConvexHull object which can be used to calculate a convex hull from a set of points.
The Shapely library for Python has built-in support for finding the minimum bounded rectangle for a generic geometry type. Shapely can find the minimum bouded rectangle for polygons, point sequences, e.t.c.
https://www.geometrictools.com/Source/ComputationalGeometry.html contains some useful geometric algorithms for C/C++, including convex hull algorithms and code for finding the minimum bounding box/volume/circle/sphere e.t.c.
https://stackoverflow.com/questions/13542855/python-help-to-implement-an-algorithm-to-find-the-minimum-area-rectangle-for-gi contains useful information to fin the minimum bounded rectangle.
https://www.geometrictools.com/Documentation/MinimumAreaRectangle.pdf is a very detailed and precies explanation on how the minimum bounded rectangle algorithm works. See here for a cached copy.
This work is licensed under a Creative Commons Attribution 4.0 International License .
- How To Parse Mathematical Expressions
- Bresenham's Line Algorithm
- Consistent Overhead Byte Stuffing (COBS)
- How To Change The IO Scheduling Class And Priority In Linux