data-structures - 如何最好地表示 3D 欧几里得空间中的网格图？

Question

我正在寻找一种表示连通图的有效方法，其中节点在空间上位于 3D 欧几里得空间中，每个节点可能有 6 条边(在其各自的 2D 平面上有 4 个方向以及上下方向)，但是还没有找到任何示例，可能是因为我没有使用正确的关键字。

任何指导将不胜感激。

有这样结构的库吗？

Answer 1

也许您正在寻找“空间”数据结构。 一个简单的例子是八叉树(三维)，它很容易实现，网上也有很多实现。

网格是否一次扩展一个节点？还是一次飞机？还是要添加节点的立方体(例如 10x10x10)？

我前段时间写了自己的多维结构，叫PH-Tree .如果您添加单个节点，则可以一个接一个地添加它们。如果添加节点立方体，也许最好将这些立方体存储在 3D 数组中，然后将这些数组添加到 ph 树中，并将它们在空间中的位置作为键。

PH-Tree 的实现有些复杂，但它比八叉树更快且空间效率更高，至少对于大型数据集而言是这样。 PH-Tree 源代码使用 Java。

要查找的其他关键字:R-树(R*-树、R+树、X-树)和 kd-树。