Monotone Chain Convex Hull

From Algorithmist
Jump to navigation Jump to search
Error creating thumbnail: Unable to save thumbnail to destination
Upper and lowers hulls of a set of points

Andrew's monotone chain convex hull algorithm constructs the convex hull of a set of 2-dimensional points in time.

It does so by first sorting the points lexicographically (first by x-coordinate, and in case of a tie, by y-coordinate), and then constructing upper and lower hulls of the points in time.

An upper hull is the part of the convex hull, which is visible from the above. It runs from its rightmost point to the leftmost point in counterclockwise order. Lower hull is the remaining part of the convex hull.

Pseudo-code[edit]

Input: a list P of points in the plane.

Sort the points of P by x-coordinate (in case of a tie, sort by y-coordinate).

Initialize U and L as empty lists.
The lists will hold the vertices of upper and lower hulls respectively.

for i = 1, 2, ..., n:
    while L contains at least two points and the sequence of last two points
            of L and the point P[i] does not make a counter-clockwise turn:
        remove the last point from L
    append P[i] to L

for i = n, n-1, ..., 1:
    while U contains at least two points and the sequence of last two points
            of U and the point P[i] does not make a counter-clockwise turn:
        remove the last point from U
    append P[i] to U

Remove the last point of each list (it's the same as the first point of the other list).
Concatenate L and U to obtain the convex hull of P.
Points in the result will be listed in counter-clockwise order.

Implementations[edit]

References[edit]

  • De Berg, van Kreveld, Overmars, Schwarzkopf. Computational Geometry: Algorithms and Applications. 2nd edition, Springer-Verlag. ISBN 3540656200.
  • Dan Sunday. The Convex Hull of a 2D Point Set or Polygon. (archived copy by webcite)
  • A. M. Andrew, "Another Efficient Algorithm for Convex Hulls in Two Dimensions", Info. Proc. Letters 9, 216-219 (1979).