Compute union of two arbitrary shapes

Question

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++.

Toolmaker

Answer 1

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.

Ouabain

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

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? – Ouabain

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

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

Answer 2

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 :)

Stress

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

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. – Ouabain

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. – Stress

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. – Toolmaker

Answer 3

See also GPC.

Exonerate

Answer 4

Would this algorithm work for you?

Pelham

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. – Ouabain

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

This link is busted – Crewelwork

Answer 5

How about:

1. Pick the left-most point of the two shapes. Call that Shape A and make it the current shape.
2. 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.
3. 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.

Pelham

Answer 6

There seems to be also a javascript api:

https://github.com/bjornharrtell/jsts/

which seems to implement the jts standard and has several differnt implementations:

http://tsusiatsoftware.net/jts/jts-links.html#ports

all of them should be able to perform union etc:

http://tsusiatsoftware.net/jts/JTSUser/contents.html

But csg.js is the most impressive project IMO

https://github.com/evanw/csg.js

Godfather