c++ - 在 3D 空间中表示节点的最佳数据结构是什么？

Question

...感谢阅读...

我还在摸索中所以请原谅... ;-)

我正在编写一个在空间中对实体进行网格划分的函数。网格是通过使用“节点”类的对象完成的，每个节点表示为:

int id
double p
double r

最初我认为 map 是可行的方法:使用 map 我可以在“id”键和第二个键(指向节点对象的指针)之间建立关联。

像这样:

int nodeId;
Node *node;
std::map<int, Node *> NodeMap;

然后，当我创建节点时，我只调用“new”运算符。例如，在 for 循环中我会做这样的事情:

node = new Node(i); // the node constructor sets the id to the value of i.

然后我将新节点添加到 map 中:

NodeMap[i] = node;

但是......我意识到我需要在 map 中进行查找，而不是通过第一个键(id)，而是通过 p 和 r 参数(节点的坐标)。

换句话说，我需要一些东西来返回给定 p 和 r 值的节点 ID。 如果查找是使用整数第一个键 (id) 完成的，则映射是一个完美的容器。 有人对如何解决这个特定问题有建议吗？

非常感谢! AsvP.

Answer 1

与任何“我应该用什么来表示这个结构”的问题一样，它确实取决于您想如何与之交互

场景图在 3D 库中很常见，它们提供基于树的节点遍历，通常允许变换、交互和其他属性沿着树向下级联。

对于保存要渲染的对象的东西，一个常见的结构是 Binary space Partitioning Tree这允许有效剔除绝对不可见或被其他人遮挡的对象。

编辑； 我想念你是按 float 索引的。这通常是个坏主意(因为大多数标准映射中要求的准确性会导致与浮点行为的不稳定性相关的问题)。除非你真的想要这种行为

在这种情况下，您需要有一些处理方法，例如:

• 分块您的域，以便您可以准确地指向它的一小部分，并防止多个节点占用同一 block 空间。
• 采用某种方式对您的空间进行分桶(可能需要对节点浓度较高的区域进行自适应 segmentation )，以便在询问点 p,r 时，您会得到该区域中存在的一组(可能为空的)节点。