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

...并感谢阅读......

我还在学习绳索所以请原谅... ;-)

我正在编写一个在空间中嵌入实体的函数.网格是通过使用"Node"类的对象完成的,每个节点由以下表示:

int id
double p
double r

最初我认为地图将是要走的路:使用地图我可以在"id"键和第二个键(指向节点对象的指针)之间建立关联.

像这样的东西:

int nodeId;
Node *node;
std::map NodeMap;

然后,当我创建节点时,我只需要调用"new"运算符.例如在for循环中我做这样的事情:

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

我将新节点添加到地图:

NodeMap[i] = node;

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

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

非常感谢!ASVP.

与任何"我应该用什么来表示这个结构"的问题一样,它确实取决于你想如何与它进行交互

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

对于要保持要渲染的对象的东西,常见的结构是二元空间分区树,它允许有效地剔除其他人肯定不可见或遮挡的对象.

编辑; 我错过了你通过浮点索引.这通常是一个坏主意(因为大多数标准映射中所需的准确性将导致与浮点行为的不稳定性相关的问题).除非你真的想要这种行为

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

对您的域进行分块,以便您可以准确地指向它的一小部分,并防止多个节点占用相同的空间块.

有一些方法来摧毁你的空间(可能需要对具有更高浓度节点的区域进行自适应细分),这样当你要求点p时,你会得到一个(可能是空的)该区域中存在的节点集.