Anonymous Monk has asked for the
wisdom of the Perl Monks concerning the following question:
I'm looking to merge polygons. In other words, I have 2 or more adjacent polygons (defined as a series of points whose first and last points are equivalent and, therefore, form a polygon) that I would like to merge into 1 polygon (so that I have 1 series of points that has the same first and last point).
Are there any modules anyone is aware of and, if so, does it do any sort of errorchecking to verify the 2 polygons are, in fact, adjacent?
If there aren't any modules, anyone have any ideas on how to get started on this?
Thanks in advance!
Re: Merging Polygons
by thekestrel (Friar) on Mar 30, 2005 at 00:30 UTC

Hi,
I'm not quite sure exactly how you're thinking of merging adjacent polygons (i.e. are they touching?) but this module seems to have the sort of polygon manipulation routines you would require to do this.
Regards Paul.  [reply] 

I have had to do this exact same thing previously. Are you doing GIS work? What type of data are these 'points'? Are they simple graph plots, latlong pairs, etc? Even if you are not doing GIS work do a google search on 'gis perl' or start at http://freegis.org
You can basically do this:
1 .........
2 . .
3 . ........
4 . . .
5 . . .
6 . ........
7 . .
8 .........
1234567891111111
0123456
Given the two adjacent polygons above, you essentially want to remove the points between 9,6 and 9,3. All you need to do is sort each list of points and remove the matching set. Be sure to leave the 'leftmost' and 'rightmost' matching set though. I would do as suggested and order each polygon either clockwise or counter clockwise. This should work out just fine for you. If you need more clarification or help, just ask.
If done carefully, you will end up with the following. Please correct me if I'm wrong in my assumptions.
1 .........
2 . .
3 . ........
4 . .
5 . .
6 . ........
7 . .
8 .........
1234567891111111
0123456
 [reply] [d/l] [select] 

Yes...they would be touching.
 [reply] 

I second the recommendation for the module Math::Geometetry::Planar, especially the GpcClip UNION operation. It is capable of dealing with concave polygons and polygons with holes.
 [reply] 
Re: Merging Polygons
by thekestrel (Friar) on Mar 30, 2005 at 02:06 UTC

Assuming you're wanting to join two polygons that both share a common line i.e. two subsequent vertices of exactly the same points and not worry about intersecting polygons it would not be that hard to do.
A bit or pseudocode on my thoughts...
# assuming polygon is 123(4=1 implied) for a square
#Get both shapes going in the same direction
# to make things simpler later
Order array of shape 1 so that its a clockwise closed shape
Order array of shape 2 so that its a clockwise closed shape
foreach line in shape 1 {
foreach line in shape 2 {
are line1 and line two the same {
store which line this is.
}
}
}
splice into array of shape1 at point of common line all of shape 2 rem
+oving the common line.
Regards Paul  [reply] [d/l] 
Re: Merging Polygons
by Fletch (Chancellor) on Mar 30, 2005 at 01:42 UTC

You'd better be careful how you pass perimeters to your subs or you'll wind up convexed and get the answers oblong.
(Aside from the bad puns, I've got nothing to add other than that PDL might have some support for this. If you're looking for algorithmic help see if you can't lay a hand on Computer Graphics, C Version (ISBN 0135309247); just be forewarned that the algorithm's probably going to be more geared towards rendering the merged result which may not be what you need.)
 [reply] 
Re: Merging Polygons
by TedPride (Priest) on Mar 30, 2005 at 11:37 UTC

Yes, but it's not that simple. What if two lines are equivalent, but one is shorter than the other? What if merging two polygons creates an internal "hole"? This could be quite an interesting thing to program.  [reply] 

TedPride
The example I gave would work if the equivalent lines were different lengths with slight modification. Identifiy the points that are on the same line, only add points from second line if they are not the same as the first. If you look at the post gnu@perl did for an example we have two shapes ABCD and EFGH. in this case BC is on the same line as HE and HE is shorter. Thus on the colinear line looking down it you would have BHEC.
From my routine you would insert the HE shape between points BC. Thus going from
ABCD and EFGH
to
A(BC)D and E)FG(H
which gives
ABEFGHCD
or
AB
 
  EF
   
  HG
DC
AB
 
 EF
 
 HG
DC
You are right though this does not take care of holes, or overlaps and intersections, this would be more a pure math problem of intersections etc and these can be found on the web. I was just postulating that the problem may have been more one of tiling and hence if this was the case the solution is not all that complicated.
Regards Paul.
Update: There is a good link here which can be simplified as some of the calculations are already available in the module Math::Geometry::Planar from my first post.  [reply] [d/l] 

