Rigorous Geometry

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 p = (0.5, 0) and let the square, s, have vertices at (0, 0), (1, 0), (1, 1), (0, 1) . Obviously p is contained in s and any reasonable algorithm for testing so would yield true. I now want to try rotating s by \pi/4 radians. This is the point where the pesky problems with floating point come in. The number \pi/4 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 \pi/4. That is the square was rotated by a little bit more than \pi/4 radians. Thus the point (0.5, 0.5) is not contained in the rotated square.

This is a bad thing because intuitively the point (0.5, 0.5) should be contained in the rotated square. After all we meant to rotate the square by \pi/4 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 \epsilon of the boundary of the polygon or is actually contained in the polygon. The \epsilon 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 \epsilon modification.

Advertisements

2 thoughts on “Rigorous Geometry

  1. Pingback: Rigorous Geometry - Mathematics Lectures

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s