here's a question that's been bothering me for the last couple of days - my colleague believes this is a well-researched problem, but I couldn't find any papers online (perhaps the key words I used were incorrect).
Given a graph where each vertex corresponds to a surface and an edge exists between two vertices if the corresponding surfaces meet at a line, how would I go about identifying the surfaces that combine to form closed volumes?
So for instance, the adjacency list for a cube (with surfaces numbered 1 to 6) might look something like this:
1 -> [4,2,5,6]
2 -> [1,3,5,6]
3 -> [2,4,5,6]
4 -> [3,1,5,6]
5 -> [1,2,3,4]
6 -> [1,2,3,4]
In addition to this information, I also know if some surfaces have free-edges (i.e those edges are not shared with any other surface) which means I can immediately exclude these surfaces since a surface with a free-edge cannot be part of a cavity boundary. Also, if two surfaces meet, they will meet cleanly at a boundary - no glancing blows etc.
What I hope to be able to do is not just identify that a cavity exists but also to output a mapping between surfaces and the cavities they contain. For instance, in the case of two cubes which meet at an edge (not enough reputation to post an image, so here's a side view):
-----------
| |
| |
| |
---------------------
| |
| |
| |
-----------
...this would be the desired output assuming surfaces 1-6 make up cube ONE and 7-12 make up cube TWO:
Volume 1 -> [1,2,3,4,5,6]
Volume 2 -> [7,8,9,10,11,12]
Note that, in this case, some surfaces have SIX neighbors in the graph while others have only FOUR neighbors.
Any help would be much appreciated!