4

I'm searching for a way to find the outline of two adjacent polygons.

The polygons are defined by a list of points ordered by occurrence in the polygon. In my use case, there are no overlapping polygons, there are no gaps between the polygons, and there are no polygons with "holes".

I want to calculate the outline of the two polygons without any "holes". These pictures show the expected results.

enter image description here

I know that there are a lot of libraries for clipping polygons, but for most of them the performance is not very good because they work for any kind of polygon (with holes, overlapping polygons etc.). In my use case the algorithm has to work in real time for a lot of polygons (>20.000). How can I most efficiently calculate the outline?

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
heinzwilli
  • 247
  • 1
  • 3
  • 9
  • Try this ... http://stackoverflow.com/questions/83593/is-there-an-efficient-algorithm-to-generate-a-2d-concave-hull – Angus Johnson Sep 29 '14 at 16:05
  • Will be useful to 1) avoid duplicating the vertexes; 2) establish the inverse relation "this vertex belongs to this/these outline(s)". From there, you can find outlines that share a vertex and could be merged, and processing will reduce to logically combining two vertex lists. –  Sep 29 '14 at 17:27
  • To Yves Daoust: Following your advice I can identify which vertexes belong to both polygons. But how to go on? Case one in the picture is quite easy. I just have to insert the vertexes from polygon 2 between the two vertexes from polygon 1 which belong to both polygons, in the right order. Case 2 from the picture is more difficult I thing. If I remove the outlines between the polygons a "hole" is left over. How can I identify which outlines belong to the "hole"? – heinzwilli Sep 30 '14 at 07:13
  • Do you see any way of selecting a vertex which is guaranteed to be part of the outline? Like mentioned before case 2 of the picture will result in two possible outlines. The outline of the "hole" and the outline I'm looking for. If I could identify a point of the outline I would know which outline I should choose. – heinzwilli Sep 30 '14 at 14:01
  • The question text says that "there are no gaps between the polygons". In the second example, wouldn't that island between the two polygons, formed by red vertices 3, 4, 5, 6 and blue vertices 4, 5, 6, 7 be considered a gap? – Reto Koradi Oct 04 '14 at 05:57
  • The second example should visualize the possibility of one (or more) polygons being surrounded by the polygons that going to be combined. – heinzwilli Oct 06 '14 at 08:16

1 Answers1

0

Given

no overlapping polygons, there are no gaps between the polygons and there are no polygons with "holes"

the following algorithm should do the trick.

  1. Discard duplicate line segments.

  2. Compute the natural combinatorial embedding of what's left as a doubly connected edge list. Each segment gives rise to two nodes (half edges, reverses of each other, with one endpoint of the segment being the head (respectively, the tail) and the other being the tail (respectively, the head)), and each half edge links to the next half edge with the same head in counterclockwise order.

  3. Extract the faces. A face in the combinatorial embedding is a minimal, nonempty set of half edges such that, for each half edge e, the reverse of the next half edge from e is in the set. The set of faces is a partition of the half edges. See the ASCII art diagram below.

    U----V----W
|    |    |
|    |    |
Z----Y----X

    The infinite face is {U->Z, Z->Y, Y->X, X->W, W->V, V->U}. The next half edge from W->V is U->V. The reverse of the next half edge from W->V is V->U. The other faces are {U->V, V->Y, Y->Z, Z->U} and {V->W, W->X, X->Y, Y->V}.

  4. Retain only the infinite faces by summing signed counterclockwise angles and testing the sign. A finite face like {U->V, V->Y, Y->Z, Z->U} has negative sum

    /_UVY - 180 + /_VYZ - 180 + /_YZU - 180 + /_ZUV - 180
    = 4 * (90 - 180) = -360.

    The infinite face has positive sum

    /_UZY - 180 + /_ZYX - 180 + /_YXW - 180 + /_XWV - 180 + /_WVU - 180 + /_VUZ - 180
    = 4 * (270 - 180) + 2 * (180 - 180) = 360.
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120