Geometry Algorithms


This site is now a book, available from Amazon US as a
Kindle eBook ($8.95)
Paperback ($17.95)
NEW  Hardcover ($23.95)

Also available from Amazon in other countries, including


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. The Math 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 available 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 is only available here.


© Copyright 2001, 2021 Dan Sunday