?

Log in

No account? Create an account

Previous Entry | Next Entry

I've been working on getting my CAD/CAM program up to snuff with basic stuff like, oh, Grouping/Ungrouping objects, and getting SVG import/export working. Part of this has gotten me to revisit some code that I had stopped working on out of frustration.

My Boolean Geometry code.

This is code that is supposed to let you take two or more polygons and join them into one object, or subtract one from the other, or get just the regions that are common to both polygons. This is incredibly useful code when you are trying to make milling paths in CNC work. But until now, my code was just plain broken.

As with many complicated tasks, a few months working on other code has let the design simmer in the back of my brain, and as I finally come back to it, now the design is both obvious and simple to me, so I coded it up, and it now works for simple closed polygons. (Compound polygons are slightly more complex, but with the basics in place, won't be a big deal to finish.)


For all boolean operations between two simple closed polygons, you need to first do a few steps to classify edges on both polygons:
Step 1: Find all places where the two polygons intersect, and insert a point into both polygons at the intersections.
Step 2: Remove any repeated points from both polygons so that there will be no zero-length segments.
Step 3: For the first polygon, check the midpoint of every segment, and find out if it is inside, outside or exactly on the edge of the second polygon. For those midpoints exactly on the other polygon's edge, check a point very slightly to the side of the midpoint to see if it is inside (or outside) both polygons (Shared), or only one (Unshared). We will now label each segment of polygon1 as being either Inside, Outside, Shared or Unshared.
Step 4: Do the same for the segments of polygon2 with respect to being inside/outside/shared/unshared of polygon1.

Now, to construct your output, for Union, you want to take all the segments in polygon1 that were Outside or Shared, and all the segments of polygon2 that were Outside, and connect them up into contiguous paths.

To construct your output for Diff, you want to take all the segments in polygon1 that were Outside or Unshared, and all the segments of polygon2 that were Inside, and connect them up into contiguous paths.

To construct your output for Intersection, you want to take all the segments in polygon1 that were Inside or Shared, and all the segments of polygon2 that were Inside, and connect them up into contiguous paths.



[edit:] This all is also known as constructive areal geometry or constructive 2D geometry.[/edit]

Comments

( 7 comments )
cjthomas
Apr. 10th, 2009 05:14 am (UTC)
This is certainly more elegant, and faster, than what my first approach would have been };>.

Case you didn't mention: A test point reading as outside both polygons (which would be for a shared edge). Your logic may well already catch this, but it wasn't mentioned in the description.

-Deuce
revar
Apr. 10th, 2009 05:32 am (UTC)
Shared = Segment is on the edge of the other polygon, and the inside of both polygons is on the same side of the segment.
Unshared = Segment is on the edge of the other polygon, and the insides od the pollygons are on opposite sides of the segment.

So your proposed test point indicates a Shared edge segment.
cjthomas
Apr. 10th, 2009 07:09 am (UTC)
I understand that (in fact, I said exactly that in my original reply).

I'd thought you'd overlooked this case in your original post, but rereading, it seems I was mistaken.

-Deuce
revar
Apr. 10th, 2009 07:51 am (UTC)
No, I edited it to add the words "(or outside)" to fix the oversight.
(Deleted comment)
revar
Apr. 10th, 2009 06:44 am (UTC)
A less hokey way to do the test is to test a horizontal (or vertical) line from the midpoint itself to infinity on one side, and discard the possible (due to rounding issues) intersection with the originating segment. If you get an even number of intersections (discarding the originating segment) with the polygon, then that side is outside the polygon.
cjthomas
Apr. 10th, 2009 07:11 am (UTC)
You could also maybe force a consistent winding direction for polygons (clockwise or counterclockwise), and test to see if the two edges were pointing in the same or opposite directions.

Moot point if it works as-is, of course =^.^=.

-Deuce
( 7 comments )