This problem looks so easy if you tackle it with a pencil and paper, and yet it is rather complex to do by a computer program. There's a lot of tedious geometry to do. On the other hand, geometry isn't Perl specific. There's an Article on stackoverflow which explains the steps.
While writing this, I saw that choroba recommends Math::Geometry::Planar which helps a lot.
There are some more issues to consider:
- Be aware of rounding errors, for example if vertices are "almost parallel".
- Be aware that the union of the two shapes can contain a hole unless both polygons are convex. A merge of two polygons isn't necessarily convex, as your examples show. Therefore, the library returns a structure which contain more than just a list of points.
- Be aware of self-intersecting polygons, like these:
my @poly1 = ([0,0], [1,0], [0,1], [1,1], [0,0]);
my @poly2 = ([0,0], [0,1], [1,0], [1,1], [0,0]);
# A possible result could be:
my @merge = ([0,0], [1,0], [1,1], [0,1], [0,0]);
Fun fact: Math::Polygon::Calc will return 0 as the area of @poly1 and @poly2, while the merged polygon has an area of 1.