All examples By author By category About

NPashaP

Convex Hull

This program demonstrates an algorithm for finding the smallest convex polygon containing a given set of points (Convex hull).

The algorithm works as follows

  1. Find the highest point A.
  2. Find the second point by searching for a point B such that AB makes the smallest angle with the positive x direction.
  3. Find the remaining points recursively by searcing for a point Z such that YZ makes the smallest angle with XY where X and Y are the last two points found (Y after X). Include the initial point A in the search. When the search ends in A, then the path is complete.

The dot product is used to find the angle between two vectors.