CODEWITHSUNDEEP
algorithmgraph
FreeFly
FreeFly

Reputation: 153

Find unique loops in undirected graphs

I am currently working on a node-based house-builder for Unity. The system is pretty simple in its workflow: users can create nodes, which are simply cubes, and connect them with each other to create walls. The mesh processing is already done and it works nice and smooth.

What I am trying to do now is to detect how many closed rooms have been created and what vertices are involved in each one of them. The possible inputs can be seen in the following images:

enter image description here enter image description here

In the first picture, the loops would be

(1,5,3,4), (1,2,6,8,7,5), (6,9,12,11,10,8), (8,10,14,13) and (10,11,17,16,15,14).

In the second one they'd be

(1,2,5,6,8,7), (2,3,4,14,13,6,5), (6,13,12,11,10) and (8,6,10,9).

Each node can be connected to up to four other nodes, one per cardinal side, and every link is stored on both sides. I do not need the nodes to come in any particular order.

I thought I could use a generic loop-detection algorithm and recursively search for sub-loops until the loop I find has has no internal connections, but this would be extremely resource-consuming. There must be some properties I can use to detect loops with no internal connections without iterating over the graph so many times, but I haven't been able to find it.

Do you have any suggestion?

Upvotes: 1

Views: 374

Answers (2)

Gabriel Furstenheim
Gabriel Furstenheim

Reputation: 3432

This is an answer only to the first question, but it might help you with the second one. The number of closed rooms actually has a closed formula: 1 - V + E where V is the number of vertices and E is the number of edges. In your second example, there are 14 vertices, 17 edges and 4 rooms. The mathematics are a bit complicated, but the key word is Euler characteristic.

Upvotes: 1

Nico Schertler
Nico Schertler

Reputation: 32597

For the following algorithm to work, you need the following:

  • A unique direction of the edge (which you probably already have)
  • Two flags for every edge that specify if the edge has been used in the forward and the backward direction
  • A list of vertices with unused edges

Then the idea is the following. Take any node with unused edges and go along any of the unused edges to the neighbor (keep the direction in mind). Doing so, immediately mark the edge in the according direction as used. At this neighbor, you know the direction from which you came. Look in counter-clockwise order until you find the first unused edge (again watch out for the edge direction). You can also search in clockwise order, this will define the order of all your output faces. E.g. if you came from the left edge, then check the bottom, right, top edges, respectively. Go across this edge (mark as used) and repeat until you arrive at the start vertex. All visited vertices form your room.

Doing so, you should update the list of vertices with unused edges accordingly.

Eventually, you will also create a face for the border. You can detect this e.g. by calculating its orientation:

v1 x v2 + v2 x v3 + v3 x v4 + ... + vn x v1

, where v are the positions of the vertices and x represents the z-component of the cross product (which represents the face orientation):

(x1, y1) x (x2, y2) = (x1 * y2) - (x2 * y1)

The boundary face will have a different sign for this orientation than all other faces. The actual sign depends on whether you used counter-clockwise or clockwise order during the edge traversal.

Upvotes: 1

Related Questions