CODEWITHSUNDEEP
algorithmgeometrypolygoncomputational-geometryplanar-graph
onler
onler

Reputation: 83

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

Upvotes: 3

Views: 773

Answers (1)

HEKTO
HEKTO

Reputation: 4191

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.

Upvotes: 1

Related Questions