Geometry Algorithms


NEW   This site is now a book, available at Amazon as a
Paperback ($14.95)
Kindle eBook ($9.95)


This book presents practical geometry algorithms with computationally fast C++ code implementations. It covers algorithms for fundamental geometric objects, such as points, lines, rays, segments, triangles, polygons, and planes. These determine their basic 2D and 3D properties, such as area, distance, inclusion, and intersections. There are also algorithms compute bounding containers for these objects, including a fast bounding ball, various convex hull algorithms, as well as polygon extreme points and tangents. And there is a fast algorithm for polyline simplification using decimation that works in any dimension.

These algorithms have been used in practice for several decades, and are robust, easy to understand, code, and maintain. And they execute very rapidly in practice, not just in theory. For example, the winding number point in polygon inclusion test, first developed by the author in 2000, is the fastest inclusion algorithm known, and works correctly even for nonsimple polygons. There is also a fast implementation of the Melkman algorithm for the convex hull of a simple polyline. And much more.

If your programming involves geometry, this will be an invaluable reference.

Here is the complete Table of Contents.

Also, all code given in this book can be downloaded in a zip file available at

Further, the Math used by these algorithms is still available on this site. This is Chapter 1 in the book, and consists of the basic linear algebra for points and vectors used to describe geometric objects like lines and planes. Also on this site, there is a Summary Sheet for the basic linear algebra definitions and operations. This summary sheet is not in the book, and only available here.


© Copyright 2001, 2021 Dan Sunday