# Algorithm to merge two polygons (using connectivities)?

I am struggling with implementing an algorithm that does one simple thing:

Consider two polygons (one can just draw any two polygons and number their vertices), whose connectivities in a node list are:

A = [1, 2, 3, 4, 5] B = [1, 6, 7, 8, 3, 2]

These two polygons share 2 faces (1, 2) and (2, 3).

What I want to do is to merge them into the union polygon and get the connectivity back:

C = [1, 6, 7, 8, 3, 4, 5]

The rules are:

1. All polygons have their connectivities ordered anti-clockwise (so if A has face [1, 2], B has face [2, 1] etc...)
2. It doesn't matter what is the first node index in C, but it must be ordered anti-clockwise as well.
3. Polygons can share any number of faces (the resulting element can also have a hole, but this is an edge case)

My idea is:

• Get the list of shared nodes (in this case [1, 2, 3])
• Find the first node in any polygon that is not in the list and mark it,
• Add nodes from that element moving anti-clockwise
• Once a node in the list is found, go to the other element and add nodes from there,
• Switch back and forth untill the first node is found again

Problem: It doesn't work if the union forms a hole...

I don't know if there is a standard way to do this. If I am overcomplicating things. I'd like some feedback to know if it's a reasonable way to do it. More in general, if there are, and where can I read about them, algorithms to merge a group of polygons and get the union connectivity.

Thanks for reading trough and for any tip.

• Decompose the polygons into (unoriented) line segments each of which is sorted by vertex index: $$A = \{[1,2], [2,3], [3,4], [4,5], [1,5]\}, \\ B = \{ [1,6], [6,7],[7,8],[3,8], [2,3], [1,2] \}.$$
• Then you want to want to consider the union of all of these edges, but removing the duplicated ones. So you need to form $$(A \cup B) \setminus (A \cap B) = \{ [3,4], [4,5], [1,5], [1,6], [6,7],[7,8],[3,8] \}.$$
• Now you just need to re-constitute the order of vertices. Because you know that it's a closed polygon, you start with the first line segment, and then you find that line segment that starts with the second vertex of the last segment, etc. So you get $$\left[[3,4], [4,5], [5,1], [1,6], [6,7],[7,8],[8,3]\right].$$