I’ve mentioned before that floating numbers are not real numbers. In particular they are not associative or distributive link

and also most real numbers cannot be exactly represented. Thus a naive implementation for common geometry operations such as line intersection or testing if a point is contained (by contained I mean the point is either on the boundary or in the interior of the polygon) inside a polygon can have problems. I’ll give a short example of testing if a point is inside a square.

Let and let the square, , have vertices at . Obviously is contained in and any reasonable algorithm for testing so would yield true. I now want to try rotating by radians. This is the point where the pesky problems with floating point come in. The number is not a floating point number so it is approximated by 0.785398164 (I haven’t written all the digits of the floating point number but that doesn’t change the issue). It turns out that 0.785398164 is greater than That is the square was rotated by a little bit more than radians. Thus the point is not contained in the rotated square.

This is a bad thing because intuitively the point should be contained in the rotated square. After all we meant to rotate the square by radians. I don’t know of any way to fix the problem where we can’t rotate by the number of desired radians. What is possible is to modify the algorithms for testing if a point is contained inside a polygon so that they return true if the point is within of the boundary of the polygon or is actually contained in the polygon. The is a fixed number that is large enough to mask the floating point rounding problems.

My next post will give one of the algorithms for testing point containedness with the modification.

Pingback: Rigorous Geometry - Mathematics Lectures

Pingback: More Computational Geometry :) « A blog on math