How to best represent a grid graph in 3D Euclidean Space?

Question

I am looking for an efficient way to represent a connected graph, where the nodes are spatially located in a 3D Euclidian space and each node may have 6 edges (4 directions on its respective 2D plance and up and down), but have not yet found any examples, perhaps because I am not using the correct keywords.

Any guidance would be much appreciated.

Is there any library for such a structure?

Answer 1

Maybe you are looking for a 'spatial' data structure. A simple example is an oct-tree (three dimensions), which is easy to implement, there are also plenty of implementation on the web.

Is the grid extended one node at a time? Or planes at a time? Or are you adding cubes (for example 10x10x10) of nodes?

I wrote my own multi-dimensional structure a while ago, called PH-Tree. If you add individual nodes, you could add them one by one. If you add cubes of nodes, maybe it's best to store these cubes in 3D arrays, then you add these arrays to the ph-tree, with their position in space as key.

The PH-Tree is somewhat complex to implement, but it's faster and more space efficient than octtrees, at least for large datasets. The PH-Tree sources are in Java.

Other key-words to look up: R-Trees (R*-Tree, R+Tree, X-Tree) and kd-Trees.