More on Floating Point

In my last post I outlined one of the issues with floating point. My particular geometric problem is testing if two polygons are subsets of each other. In general I want to test if one polygon is a subset of another polygon. Also the polygons can be rotated, translated, or reflected in particular any rigid motion can be applied to the polygons.

To again illustrate the problem with floating point I’ll give an example:

Let polygon, T1 = \{(0, 0), (1, 0), (1, 1),\} (a triangle), and polygon T2 = \{ (0, 0), (0.1, 0.1), (0, 1)\} (another triangle). See the below illustration.
Two triangles
By rotating triangle T1 by exactly -\pi/4 radians, I can make triangle T1 a subset of triangle T2. But the problem with floating point is that -\pi/4 is not a floating point number so I can’t rotate by exactly -\pi/4. Which means that using the ordinary algorithms for subsetness there is no easy way to make T1 a subset of T2.

That why I wrote the previous post on using some sort of fuzzy \epsilon in my geometry algorithms. But I believe that there is another way to get the result I want. What I can do is rotate T1 by the closest floating point number to -\pi/4 and then do some boolean operations to T1 and T2. In particular take the boolean intersection of T1 and T2, call the resulting shape I (the intersection). And then take the boolean difference of T1 and I, call the resulting shape R (the remainder). If R is small enough (say the area is within \epsilon = 10^-5) then I can say that T1 is a subset of T2.

In this way I can avoid using \epsilon in the algorithm for testing if a point is contained in a polygon (which is what I was supposed to write about in this post).

Advertisements

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