3

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

HEKTO
  • 3,876
  • 2
  • 24
  • 45
onler
  • 63
  • 8
  • `How can I decide to choose G path` I would guess you shouldn't, you can find a polygon with smallest amount of vertices, then cut it (remove non-shared edges, or mark polygon as deleted somehow). Then find next polygon with smallest amount of vertices, etc... – Renat Jun 07 '19 at 20:03
  • Yes, finding polygon with the smallest amount of vertices would be another approach. But, then two question needs to be answered: 1. How to find polygon with the smallest amount of vertices? 2. How to solve the overlapping problem? See the [example image](https://imgur.com/8K0bImF). In this case, ABC, ABD, ACD, BCD. all have the smallest number of vertices. How can I decide to discard ABC and keep the rest? – onler Jun 07 '19 at 20:34
  • Ok, while googling 'shortest cycle' I think I've found an answer to your question: https://math.stackexchange.com/questions/8140/find-all-cycles-faces-in-a-graph – Renat Jun 07 '19 at 20:43
  • You'll need a clearer explanation of "all the polygonal shapes of the vertices". Why would you not select AECD for example? Or the triangle ACD? Why will not something like a Delaunay triangulation algorithm suit your purposes? – Gene Jun 08 '19 at 03:39
  • @Renat Thanks, the question has a connected question(https://stackoverflow.com/questions/4023310/find-all-cycle-bases-in-a-graph-with-the-vertex-coordinates-given) and I think it is the same with mine. The accepted answer is pretty much same what you suggested. Pseudo code and a working version of the code also provided: https://gist.github.com/mastoj/750015 But, it does not solve the overlapping problem that I mention in my previous comment. – onler Jun 08 '19 at 18:02
  • @Gene Basically, I have a rectangular shape(four vertices and four edges) at the start. New vertices will be added dynamically and the new vertices will/may divide the rectangular area into smaller pieces. My main purpose is to follow this and calculate each individual area size. I run into ‘Delaunay triangulation algorithm’ while I was searching for a way to do this. I thought maybe it would be a solution for this but I couldn’t figure out a way to solve this with it. – onler Jun 08 '19 at 18:22

1 Answers1

1

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.

HEKTO
  • 3,876
  • 2
  • 24
  • 45
  • Any idea on how to detect and ignore the external face? – Magnuti May 20 '22 at 05:56
  • @Ramriez - consider angles between each arc and its *next* arc. The sum of these angles along the external cycle will be `PI*(n+2)`, and along any internal cycle - `PI*(n-2)`. Here the `n` is length of the cycle. – HEKTO May 20 '22 at 22:23