Geometry Algorithms

 

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

Book_Cover


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
GeometryAlgorithms.com/code.html.

 

© Copyright 2001, 2021 Dan Sunday