Finding polygons within an undirected Graph

8
votes

Please see Image: http://i.stack.imgur.com/NPUmR.jpg

I have an undirected graph which contains one or more connected sub graphs. The graph is defined by a set of ordered pairs of connected vertices. There may be upto 300 vertices. The graph is planar.

I need to identify polygons as shown in the Image. Each of the coloured areas in a separate polygon. A rough heuristic could be that polygons are "enclosed regions" between closed edge loops (cycles) in the graph. It's been suggested in similar posts that cycles may be identified using a Depth First traversal and marking visited vertices.

However I'm not sure how to proceed after this to get the desired output as seen in the image.

Requirements :

i) The polygons must not overlap or intersect. i.e : Cycle ABFHDCA is not a valid polygon since this would overlap with Polygon FHGE . Cycle ABFEGHDCA is a valid polygon.

ii) The polygon may have 3 or more edges and polygons must be bounded by edges of the graph. XYZ is a valid polygon although disconnected from the rest of the vertices of the Graph.

iii) Vertices like K and L (i.e. leaves) do not form parts of the polygons. We don't care about edge JK.

Update: iv) In the graph edges do not cross each other. The only place two edges can meet is at a vertex. This is guaranteed to be the case by a preceding stage/algorithm.

Questions:

  1. Am I on the right track with the DF travesal to find cycles approach? Would DF traversal give me all the (simple) cycles I need to consider in such cases, esp with XYZ being disconnected from the rest of the graph?

  2. Is there an existing alternative algorithm for solving this problem?

Additional notes:

a) I am having trouble in defining this problem in more specific computation geometric terms so am sticking with finding polygons within an undirected graph. I must admit it's been years since I studied graph theory. I'm am brushing it up presently.

b)A solution to this does not seem like a concave/convex hull algorithm. We are talking about a set of connected edges - true polygons, not just a point cloud that needs to be encompassed.

c) The example above is what I could come up with at short notice. I think it covers most of the "edge" cases (pun) :)

Similar Solutions

  1. I found a similar post but the accepted solution doesn't seem to generate the correct cycles for this example.

Thanks in advance!

2
graph-theorycomputational-geometrypolygons
I think DFS is a good way to find all the cycles in the graph. Then you want to start with the cycles of length 3 and define those as polygons. Next you need to look at the next size of cycle and check that there isn't a set of it's vertices that make up an entire defined polygon already - if there isn't then this cycle is a new polygon. Continue until you run out of cycles. – Helen
Thanks for your answer Helen. This might give us some results. But there are some failure cases here. Consider that the polygon XYZ is moved such that it is completely contained within EFGH. Your strategy would yield first XYZ and then EFGH as acceptable polygons disregarding the obvious overlap. I guess we could solve this problem by testing each vertex for every polygon so that it is not contained in another polygon. That is we are performing area check in addition to Edge chechs. But this is not very elegant and probably expensive. Thoughts? – Dev.D
I was thinking about this last night, and I don't think the problem is well defined enough to be solvable. As there are so many ways that the example graph can be drawn as a planar graph I don't think you can just input a set of vertices and edges and have a solution output. What if I,J were inside the A,B,C,D rectangle and E,G on the outside? In order to check if polygons overlap you need to know how they are drawn in relation to each other. You could really do with a coordinate set rather than a set of vertices. – Helen
Hi Helen, for my problem set I can guarantee that the edges will never intersect. If edges do meet , they will always meet at vertices. Thus polygons are either a) completely enclosed by or b) share a common set of edges with or c) are completely disassociated from a given polygon.This is ensured by a prior integrity stage in the pipeline. I'll update the question to reflect this. – Dev.D
Ok in which case use DFS to find all the cycles. Then iterate through all of the cycles to find the ones with no other cyles inside them. Define those as polygons. Iterate through the cycles again to find those with only the defined polygons and no other cycles inside them and define those new cyles (minus the existing polygons inside them) as polygons. Repeat until you run out of cycles. – Helen

2 Answers

0
votes

An optimal algorithm for extracting the regions of a plane graph: http://www.sciencedirect.com/science/article/pii/016786559390104L

What you want to do is extract polygons/regions from an embedded planar graph. The algorithm is given in the paper above. The time complexity is \Omega (m \log{m}) and space complexity is \Omega (m) where m is the number of edges in the graph.

0
votes

For starters lets get rid of the degenerate edges (JK and JL in your example): Find the vertices with a single edge and remove them from the graph. Note that this removal could also create another degenerate edge, so every time you remove a vertex A and the edge AB, take another look at vertex B to see if it is now also degenerate.

Now notice that while each vertex can be involved in any number of polygons, each edge is involved in exactly two. I'd thus suggest that we can make life simpler for ourselves by walking over the edges rather than the vertices.

  1. Associate two boolean fields with each edge to record if the left and right polygons have been found. These fields should initially all be false.
  2. Choose an arbitrary edge, let's call it AB
    1. if AB.right is false:
      1. Create an empty list L in which to store the polygon edges
      2. Set AB.right to true and add AB to L
      3. Iterate the edges of vertex B to find the next edge of the polygon. Imagine you're driving from A to B, the next edge is the one that forces you to make the sharpest-possible right-hand turn at B. I feel sure that the dot-product of the edge vectors will make this search trivial, but it's been too long for me to recall the details.
      4. Recurse steps 2 and 3 for this next edge (setting the right variable to true and adding the edges to L) until you hit an edge where right is already true. This will be the edge that you started on - You've found a complete polygon and you've eliminated a bunch of edges from your search space!
    2. if AB.left is false, do the same procedure as above, only this time you're driving in the opposite direction (from B towards A) and you're setting the left fields to true as you go. Note that you're still trying to make the sharpest-possible right-hand turn at each vertex. This will produce another polygon and eliminate another bunch of edges from your search.
  3. Repeat until the left and right fields of every edge are true.

We'll have produced a list of polygons, but this list will contain some polygons that we don't want - the ones that contain the exterior spaces of your plane (in your example image, these would be XZY and ACDHJIB). These can be detected by checking the winding order of the vertices. We were making right-hand turns at every vertex, so the polygons we want will show a clockwise winding order.