Robust Geometric Computation in Python

In this series we look in detail at the behaviour of one of the simplest geometric functions, demonstrate its flawed behaviour when implemented with floating point numbers, and fix it using an exact number type provided in the Python Standard Library.


The Folly of Floating-Point for Robust Geometric Computation

Posted on Fri 20 June 2014 by Rob Smallshire

Computational geometry - a world where lines have zero thickness, circles are perfectly round and points are dimensionless. Creating robust geometric algorithms using finite precision number types such as float is fiendishly difficult because it's not possible to exactly represent numbers such as one-third, which rather gets in the way of …

Rational Computational Geometry in Python

Posted on Thu 03 July 2014 by Rob Smallshire

In the previous article, we looked at how a standard technique for determining the collinearity of points, based on computing the sign of the area of the triangle formed by two points on the line and a third query point. We discovered, that when used with Python's float type [1 …