Geometry Algorithms

Convex Hulls

An implementation of Graham's scan for simple 2-dimensional convex hulls.

C source files: chull.c chull.h
Demonstration program (X Windows): run_chull.c
Makefile

Voronoi Diagrams

An implementation of Shamos and Hoey's O(n log n) time divide and conquer algorithm.
Note: This implementation is not completely robust and can fail in some situations because of floating point errors.

X Windows code: xgraphics.c xgraphics.h
Demonstration programs (X Windows): voronoi.c voronoi2.c
Makefile