hull

Concave or convex hull around a list of points.

How to use

import hull

points = [
    (207, 184), (393, 60), (197, 158), (197, 114), (128, 261), (442, 40),
    (237, 159), (338, 75), (194, 93), (33, 159), (393, 152), (433, 267),
    (324, 141), (384, 183), (273, 165), (250, 257), (423, 198), (227, 68),
    (120, 184), (214, 49), (256, 75), (379, 93), (312, 49), (471, 187),
    (366, 122)
]

concave = hull.concave(points)
convex = hull.convex(points)

The code above creates the following results:

Requirements

• pyprocessing if you want to run the visual examples

References

• The concave hull algorithm is based on a paper by Adriano Moreira and Maribel Yasmina Santos.
• The convex hull algorithm is an implementation of Andrew's monotone chain algorithm.

Disclaimer

• Some parts of the concave hull algorithm were copied from Mapotempo's Ruby approach.
• The entire convex hull algorithm is copy-pasted from a wikibook about algorithm implementations.