Tell me more ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.
up vote 9 down vote favorite
4

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.

share|improve this question
5  
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. – ruebenko Jun 21 '12 at 18:48
1  
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. – ruebenko Jun 21 '12 at 18:54
@ruebenko: I didn't realize it would only intersect convex polygons. Thanks for the heads up! – David Skulsky Jun 21 '12 at 19:40
1  
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
show 1 more comment

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

up vote 2 down vote

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}];
ed    = Binarize[GradientFilter[g, 2] // ImageAdjust];
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]}}]

enter image description here

share|improve this answer
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}} ). – David Skulsky Jun 22 '12 at 1:09
@David Yep. It in running on my machine (Mma v 8.0.0.0) – 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. – David Skulsky 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}} – belisarius Jun 22 '12 at 1:17
Can anyone confirm David's result? – belisarius Jun 22 '12 at 1:50
show 2 more comments

Not the answer you're looking for? Browse other questions tagged or ask your own question.