Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris

Merging Polygons

by Anonymous Monk
on Mar 30, 2005 at 00:11 UTC ( #443311=perlquestion: print w/replies, xml ) Need Help??
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 error-checking 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!

Replies are listed 'Best First'.
Re: Merging Polygons
by thekestrel (Friar) on Mar 30, 2005 at 00:30 UTC
    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.
      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, lat-long pairs, etc? Even if you are not doing GIS work do a google search on 'gis perl' or start at 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
      Yes...they would be touching.
      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.
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 pseudo-code on my thoughts...

    # assuming polygon is 1-2-3-(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
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.)

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.
      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 A-B-C-D and E-F-G-H. in this case B-C is on the same line as H-E and H-E is shorter. Thus on the co-linear line looking down it you would have B-H-E-C. From my routine you would insert the H-E shape between points B-C. Thus going from
      A-B-C-D and E-F-G-H to A-(B-C)-D and E)-F-G-(H which gives A-B-E-F-G-H-C-D or A----B | | | | E-----F | | | | | | H-----G D----C A----B | | | E-----F | | | H-----G D----C
      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.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://443311]
Approved by kvale
Front-paged by DrHyde
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (3)
As of 2018-03-24 05:15 GMT
Find Nodes?
    Voting Booth?
    When I think of a mole I think of:

    Results (297 votes). Check out past polls.