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

Fun fact: Math::Polygon::Calc will return 0 as the area of @poly1 and @poly2, while the merged polygon has an area of 1.