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

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.

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

Answer 3

See also GPC.

Answer 4

Would this algorithm work for you?

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.

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