4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Easy:

  • 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]. $$

  • If you find that this order is, geometrically, not clockwise or counter-clockwise (whichever you want it to be), just revert the order in which segments appear and in the order of vertices in each line segment.

$\endgroup$
1
  • $\begingroup$ Thanks you very much this does it. $\endgroup$ – lucmobz Jan 20 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.