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, (a triangle), and polygon (another triangle). See the below illustration.

By rotating triangle T1 by exactly radians, I can make triangle T1 a subset of triangle T2. But the problem with floating point is that is not a floating point number so I can’t rotate by exactly . 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 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 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 ) then I can say that T1 is a subset of T2.

In this way I can avoid using 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).

### Like this:

Like Loading...