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:
- All polygons have their connectivities ordered anti-clockwise (so if A has face [1, 2], B has face [2, 1] etc...)
- It doesn't matter what is the first node index in C, but it must be ordered anti-clockwise as well.
- 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.