Kata

Task

Given two overlapping polygons, return the polygon formed by their combined outer perimeter:

square = [(0, 0), (0, 20), (20, 20), (20, 0)]
triangle = [(5, 5), (15, 30), (30, 15)]
combined = [(0, 0), (0, 20), (11, 20), (15, 30), (30, 15), (20, 11), (20, 0)]

Polygons

For this kata, a polygon is represented as a list of pairs of rational numbers corresponding to the x and y coordinates of the vertices. The coordinates are ordered to form a path around the perimeter of the polygon. For both the input polygons and your resulting polygon, the following should be true:

• Each point on the polygon must be unique
• The polygons are non self-intersecting (no line segments cross)
• There are no holes in the polygon

Note that the last point means any holes formed by the combining of two polygons should be removed, and only the outer perimeter should be returned:

Finally, polygons do not have a set starting point nor direction. This means the following two polygons are the same:

[(0, 0), (0, 1), (1, 1), (1, 0)]
[(1, 1), (0, 1), (0, 0), (1, 0)]

However, they do need to traverse the perimeter in order (either clockwise or counterclockwise), meaning the following would not be the same (nor a valid polygon):

[(0, 0), (1, 1), (1, 0), (0, 1)]

Notes

To simplify this task, the following are guaranteed about all test cases:

• The two polygons will always overlap
• The two polygons will not share any points
• A point on one polygon will not be on the edge of the other polygon
• All input polygons will have fewer than 40 points