Search code examples
algorithmgeometrypolygoncomputational-geometryplanar-graph

How to find all the polygonal shapes of given the vertices?

I have a list of vertices and I know the connections between them. I am trying to find all the polygonal shapes of the vertices. These polygonal shapes should not overlap.

I did some research and I thought that I could detect the polygonal shapes, if I can traverse over the vertices on clockwise, (or counter-clockwise, doesn’t make a difference).
So, I search for solutions to traverse over the vertices on clockwise. And I found a similar topic and try the suggested solution.
But the problem is while traversing over vertices, I cannot decide which path to choose when there are multiple clockwise options.

Basically, I want to find the following polygonal shapes:

* A, E, G, C, D, A
* E, F, G, E 
* E, B, F, E

How can I decide to choose G path when I start from A then came to E vertex?

P.S: I am open for a different approach than mine if my approach is not appropriate for this problem or there are better/easier solutions for this

SampleImg

Solution

  • According to your example you are trying to find faces of planar graph, defined by its vertices and edges.

    Step 1. Replace each of your un-directed edges by a pair of directed edges (arcs), connecting vertices in both directions. For each arc (v1 -> v2) find a next arc (v2 -> v3), such that both these arcs have the same face to the left of them - this can be done by calculating angles between arcs and the axis (say) OX and ordering them in clockwise (or counter-clockwise) order. Mark all the arcs as "unused".

    Step 2. Pick up any "unused" arc and follow next arcs one after another until you reach the origin of the initial arc - you'll get a cycle, bounding a face. You've found a new face with all its arcs/vertices. Mark all the arcs in this cycle as "used". Repeat until there are no "unused" arcs.

    Returning to your example - you'll have following arcs:

    A -> E, E -> A
A -> D, D -> A
B -> E, E -> B
B -> F, F -> B
C -> D, D -> C
C -> G, G -> C
E -> F, F -> E
E -> G, G -> E
F -> G, G -> F

    Examples of next arcs:

    • (D -> C) is the next arc for (A -> D)
    • (C -> G) is the next arc for (D -> C)
    • (G -> E) is the next arc for (C -> G)
    • and so on...

    This algorithm will find all your internal faces plus one external face, bounded by the cycle (A -> E, E -> B, B -> F, F -> G, G -> C, C -> D, D -> A). You can ignore this external face, but in some cases it can be useful - for example, when you're a given a point and you need to find its position relative to your graph as a whole.