algorithmpolygongl-triangle-stripspherical-coordinate

Converting from triangle strip to polygon

I've some areas which contains 1 or more polygons. Each polygon is represented in GL_TRIANGLE_STRIP format, where each vertex is a pair of (lat, long). Is there any way to get the contours of the area?

Some specs:

I'm looking for an algorithm which complexity is around O(N*logN), where N = number of vertices.

EDIT: I tried solutions like going 2 by 2 until I reach the end of the dataset and then going backwards, but this algorithm works bad on polygons with gaps, for example this polygon where input is: A B C D E F G H I J, where I = A and J = B, doing that, the output will be A C E G I J H F D B and that should be A C E G and B H F G (order is inverted because it was easier to draw like that).

Another solution was considering points an undirected graph and edges between them (according to GL_TRIANGLE_STRIP format) where I applied a DFS in order to take out connected components. After that I computed the area of each component, and I considered the maximum area polygon as the counter clockwise contour, and the rest as the clockwise contour. That doesn't work because adjacency list requires some sorting which will make the algorithm inefficient.

Another solution I tried was some tweaked convex hull, but a convex hull is still a convex hull and did not work on concave polygons.

I also read about concave hull, but that seems to not give always precise results.

Thank you for your answers!

Solution

  • Let's start by converting a triangle strip to a polygon. We take the following strip as an example:

    Triangle Strip (Courtesy of Wikimedia Commons)

    Your strip definition would be:

    A B C D E F

    Converting that into a polygon is very simple. Just go through the list and use every second vertex. When you are at the end, return backwards and use the other vertices. In this case:

    A C E (reached the end, now return) F D B

    This can be done in O(N), where N is the number of vertices of the strip. Whether this is clockwise or counter-clockwise depends on the orientation of the strip.

    So, we can turn every strip into a polygon. All that remains is to remove shared edges. Let's say we have two polygons

    A C E F D B
W X E C Y Z

    Note that any edge that is shared (in this case C E) will appear in opposite directions (C E in the first polygon, E C in the second one). To find the area contour, we simply need to find matching edges and merge the two polygons.

    To find matching edges, it is enough to write all the polygon edges into a hash map (store what polygon they belong to and where they are in the polygon). This can be done in O(E), where E is the total number of polygon edges.

    To finally merge polygons, it is actually simpler to create new ones. Modification is definitely possible, but a bit more delicate. To do that we just need to walk along our polygon edges. As long as we are on an edge whose inverse is not in the hash map, then write this edge to the output polygon. If it is, ignore it and continue on the other polygon. Mark the edges that you visited and stop as soon as you are back to an edge that you visited before. Do this until all edges are visited (or both directions are in the hash map). This whole process can be done in O(E), where E is the total number of polygon edges.

    Here is how that would look like in our example:

    Start at polygon 1
Start at edge (A, C)
(A, C) is neither visited nor is its inverse in the hash map
Create new output area = [A, C]
the inverse of (C, E) is in the hash map, continue to polygon 2
(C, Y) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y]
(Y, Z) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z]
(Z, W) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W]
(W, X) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X]
(X, E) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E]
the inverse of (E, C) is in the hash map, continue to polygon 1
(E, F) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E, F]
(F, D) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E, F, D]
(D, B) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E, F, D, B]
(B, A) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E, F, D, B, A]
(A, C) is already visited
Close the area contour, continue to check other unvisited edges

    If you want, you can then also group the generated contours by the polygons they were created from to find connected areas that are bounded by multiple contours. A disjoint set over the polygons would be helpful for that task. If you need, you could also try to classify the contours into holes and outer contours. But be aware that this notion is highly ambiguous on the sphere (imagine a sphere and an area that is a band along the equator - which of the two contours is the hole and which is outside?) For comparatively small areas, you could use the area for this classification.