Compute union of two arbitrary shapes

views:

448

answers:

+3 Q:

Compute union of two arbitrary shapes

I'm working on an application, I need to be able to combine two overlapping arbitrary shapes as drawn by the user. This would be a Union operation on the two shapes. The resultant shape would be the silhouette of the two overlapping shapes.

The shapes are stored as a sequence of points in a clockwise manner.

Ideally I'd like an algorithm which will take two arrays of Points (x,y) and return a single array of the resultant shape.

I've been reading Wikipedia on Boolean operations on polygons which mentions the Sweep line algorithm but I can't make the link between this and my goal, alas I'm not a Mathematician.

I'm developing the application in ActionScript 3 but I'm familiar with C#, Java and I can pick my way through C and C++.

+2 A:

Implementing boolean operations correctly is not trivial; fortunately, there are libraries that already implement this functionality.

What language are you using? If it's C++, take a look at CGAL, the Computational Geometry Algorithms Library.

Martin B 2010-01-26 14:48:47

Thanks, I'm implementing in AS3 but familiar with C#,Java

Greg B 2010-01-26 14:53:29

Ah... well, I'm not sure if the CGAL source code is that much fun to pick apart and port, since it expresses its algorithms in a pretty generic fashion, modelled after the STL (IIRC, it's been a while). You might be better off porting one of the more specific libraries linked to at the bottom of the Wikipedia page. Alternatively, can you get away with simply rendering both polygons to a bitmap and then performing the boolean operations on that?

Martin B 2010-01-26 15:03:21

I found this (partial) AS3 port of the Java port of GPC http://code.google.com/p/gpcas/ which supports UNION operations. Thanks for your input.

Greg B 2010-01-26 16:47:28

Good find -- looks like that's exactly what you need!

Martin B 2010-01-26 16:53:37

GPCAS works a treat and is super simple. Thanks Martin

Greg B 2010-01-27 11:02:07

+2 A:

Given two lists of points (A and B)
- [ 1 ] for each line in A does it intersect a line in B
-.- [2] if no (more) lines intersect, there is no overlap
-.- [3] if a line in (A) intersects a line in B then
-.-.- [4] add the point of intersection into output
-.-.- [5] does the next line from A intersect B
-.-.-.- [6] if not, add this to output (it's inside B) goto 5
-.-.-.- [7] if so, add the intersect to output and switch lists A & B goto 2

Also see Intersection Point Of Two Lines. I'm not gonna write the code sorry :)

Dead account 2010-01-26 15:07:04

+1: Sounds like a decent approach to me

Jon Cage 2010-01-26 15:19:30

thanks Jon... should also say "add logic to avoid infinite loop"

Dead account 2010-01-26 15:21:08

Beware -- this problem isn't as easy as you think. Some food for thought: One line (or "edge") in A may intersect more than one edge in B. The two original polygons may be disjoint; or A may lie entirely within B; or B may lie entirely within A (though these three cases look the same if you're merely looking at intersections between lines). The polygons need not be convex, and the union of two non-convex polygons can have holes. And so on… computational geometry is notorious for having all sorts of special cases you don't think of at first.

Martin B 2010-01-26 15:42:28

Yes Martin - a line in group A may cross more than one line in group B. So you'd need to take the closest intersection from the starting point.I was trying for a "fill winding" algorithm approach.

Dead account 2010-01-26 15:47:21

Thanks for your thoughts Ian. I'm looking at a very similar algorithm on my pad in front of me. It was starting to think about some of Martin B's points that made me start my search for a Library to do it for me.

Greg B 2010-01-26 16:46:51

+1 A:

Would this algorithm work for you?

Jon Cage 2010-01-26 15:10:04

+1 I'd give this a go first tbh!

Dead account 2010-01-26 15:21:34

This algorithm computes the intersection; Greg B is looking for the union. Also, this algorithm works only when both polygons as well as their intersection are convex; Greg B talks about "arbitrary shapes", so I assume he wants to be able to handle non-convex polygons, too.

Martin B 2010-01-26 15:44:32

Fair point Martin. I had assumed they were convex shapes and was suggesting that algorithm as a starting point to find the two intersections.

Jon Cage 2010-01-26 15:54:57

How about:

Pick the left-most point of the two shapes. Call that Shape A and make it the current shape.
Wind clockwise along the current shape to the next point and check to see if one or more lines intersect.
- If any lines DO intersect, find the first intersection point and add that to your new shape. Switch to winding along the other shape.
- If no lines intersect move onto the next point in shape A and add that as the point in your new shape. Continue winding along the current shape.
Repeat Step 2.

I think if you keep winding along whichever shape is current, looking for intersections, that should do what you want. I think that should cope with concave shapes as well...

I'm sure there are a lot of optimisations you can add once you've got the basics working.

Jon Cage 2010-01-26 17:22:13

+1 A:

ansaurus

tags:

views:

answers:

Compute union of two arbitrary shapes

related questions