# (Non-Convex) Polygon Union and Intersection Functions [duplicate]

Possible Duplicate:
Intersecting graphics

Back in 2009 I posted a question in comp.soft-sys.math.mathematica looking for a function which generates the union of two (not necessarily convex) polygons. The Imtek library has a function which generates the intersection of two such polygons, but it doesn't have a union function. There are apparently C libraries available to which one could link which include such a capability (e.g., http://www.cs.man.ac.uk/~toby/alan/software), but I'm still curious if anyone has developed (and is willing to share) a native Mathematica function to generate a polygon union.

Since I just learned from @ruebenko that the Imtek library which I mentioned above only finds intersections for convex polygons, I'd like to expand this question to functions which can find the union AND intersection of non-convex polygons.

-

## marked as duplicate by J. M.♦Oct 30 '12 at 2:51

The code I wrote at that time was based on Joseph O'Rourke book Computational Geometry in C The notation is based on the book and it would requite a bit of thinking on how to tweak it to make a polygon union in stead of an intersection but not impossible. It might be worth a try. – user21 Jun 21 '12 at 18:48
Forgot to mention the IMS version would intersect convex polygons only. So there is a need for some further algorithm to make it work for non convex polygons. – user21 Jun 21 '12 at 18:54
@ruebenko: I didn't realize it would only intersect convex polygons. Thanks for the heads up! – Cassini Jun 21 '12 at 19:40
Since a Java port of the GPC library you linked above was made, this could be another case for Leonid's excellent JavaLoader. – Ajasja Jun 21 '12 at 21:04
Please, how is this question substantially different from: mathematica.stackexchange.com/q/528/121 ? – Mr.Wizard Jun 22 '12 at 2:00

A poor man's alternative to polygon union (not fully tested, and obviously rough):

p0    = Polygon[{{0, 0}, {1, 1}, {0, 1}, {1, 0}}];
p     = Polygon[{{1, 0}, {0, Sqrt[3]}, {-1, 0}}];
g     = Graphics[{p0, p}];
lines = ImageLines[ed, "Segmented" -> True];
f1    = (Round /@ Flatten[lines, 2] //.
{r___, {a_, b_}, s___, {x_, y_}, t___} /; (0 < Abs@(x - a) < 3)
:> {r, {a, b}, s, {a, y}, t});
f2    = (f1 //. {r___, {a_, b_}, s___, {x_, y_}, t___} /; (0 < Abs@(y - b) < 3)
:> {r, {a, b}, s, {x, b}, t});
f3    = Partition[f2, 2];
fk    = f3 //.
Alternatives[
{r___List, {x__List, y__List}, s___List, {w__List, y__List}, t___List},
{r___List, {x__List, y__List}, s___List, {y__List, w__List}, t___List},
{r___List, {y__List, x__List}, s___List, {y__List, w__List}, t___List},
{r___List, {y__List, x__List}, s___List, {w__List, y__List}, t___List}]
-> {r, {x, y, w}, s, t};
GraphicsGrid[{{g, Graphics@Polygon[fk]}}]


-
Is the code you posted what you used to generate the figure? I ask because when I run the code, I get a different result for the fk polygon (the coordinates of the vertices are {{7, 7}, {353, 7}, {181, 306}, {8, 7}, {181, 306}, {254, 178}, {289, 118}, {353, 7}, {352, 178}, {289, 115}, {250, 181}, {352, 180}, {331, 47}, {352, 6}} ). – Cassini Jun 22 '12 at 1:09
@David Yep. It in running on my machine (Mma v 8.0.0.0) – Dr. belisarius Jun 22 '12 at 1:15
Can you post the vertices of the resulting polygon? I suspect there's an ordering difference, but I have no idea why. I'm running MMA v.8.0.4. – Cassini Jun 22 '12 at 1:16
@David and here the fk polygon is {{180, 305}, {8, 8}, {352, 8}, {289, 116}, {352, 179}, {253, 179}, {180, 305}} – Dr. belisarius Jun 22 '12 at 1:17
Can anyone confirm David's result? – Dr. belisarius Jun 22 '12 at 1:50