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 http://freegis.org You can basically do this:

       
1 .........
2 .       .
3 .       ........
4 .       .      .
5 .       .      .
6 .       ........
7 .       .
8 .........
  1234567891111111
           0123456
[download]

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
[download]

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.

# 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.
[download]

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

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 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
[download]

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.