1
$\begingroup$

I have a bunch of connected walls in a list and the data for them is like so:

Wall
{
   Node A;
   Node B;
}

Node 
{ 
   float x; 
   float y; 
}

I want to find the rooms from the connected walls as an array of connected points to represent each room's perimeter.

This is an example visually of what i am trying to find: enter image description here

The red dots are the nodes, and the lines are the walls, the numbers are the identified rooms that the walls created.

The walls can be at any angle, not sure if that matters though.

I am wondering what algorithms exist that can help me solve this problem, what is the best way to approach this?

$\endgroup$

1 Answer 1

2
$\begingroup$

One approach is to use a data structure for representing a planar graph. Each node corresponds to a vertex in the graph, and each walls corresponds to an edge in the graph. Then, you are looking for the set of faces in this graph. Standard data structures for representing planar graphs should make it easy to retrieve the set of faces.

For instance, one standard data structure is the DCEL data structure. It explicitly contains one record for each face, so once you have converted this to a DCEL data structure, then it is straightforward to iterate over all faces. There are standard algorithms for constructing a DCEL data structure from the set of vertices and edges. Or, instead of a DCEL, it looks like you could alternatively use a quad-edge data structure or a winged-edge data structure. The keyword is to look for data structures for polygon meshes. This has been studied in great detail in the computer graphics and computational geometry fields.

Alternatively, you could solve your problem directly. For each node, find all of the walls associated with it, sort them by their angle, and store that sorted list associated the node. After doing that for all nodes, then you can iterate through all rooms. Pick an wall, then you can find the room to the "right" of that wall by simulating the left-hand rule: stand to the right of that wall, put your left hand on the wall, and walk forward, going in a circle around the perimeter of the room. To simulate that rule, as you walk forward, you'll walk to the endpoint of the current wall; at that node $d$, to find the next wall you proceed to, look in the sorted list of walls incident on $d$, and find the next one in sorted order, then follow that wall. It might be a bit trickier to work out the details of this, than to use an existing implementation of a DCEL data structure.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.