在3D空间中表示节点的最佳数据结构是什么？(What is the best data structure for representing nodes in 3D space?)

在3D空间中表示节点的最佳数据结构是什么？(What is the best data structure for representing nodes in 3D space?)

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

我仍然在学习绳索，所以请原谅... ;-)

我正在编写一个在空间中实现一个固体的函数。 网格通过使用“节点”类的对象来完成，并且每个节点由以下表示：

int id double p double r

起初，我认为地图应该是一条路：通过地图，我可以在“id”键和第二个键（指向节点对象的指针）之间建立关联。

像这样的东西：

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

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

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

并将新节点添加到地图中：

NodeMap[i] = node;

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

换句话说，我将需要返回给定p和r值的节点ID。 如果查找是使用整数第一个键（id）完成的，那么map是一个完美的容器。 有没有人有关于如何解决这个特殊问题的建议？

非常感谢！ ASVP。

... and thanks for reading...

I'm still learning the ropes so please be forgiving... ;-)

I am writing a function that meshes a solid in space. The mesh is done by using objects of a "Node" class and each node is represented by:

int id double p double r

Initially I thought that a map would be the way to go: with a map I can make the association between the "id" key and the second key (a pointer to the node object).

Something like this:

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

Then, when I create the nodes I just call the "new" operator. E.g in a for loop I do something like this:

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

and I add the new node to the map:

NodeMap[i] = node;

But.... I realized that I will need to do a lookup in the map not by first key (the id) but by the p and r parameters (the coordinates of the node).

In other words I will need something that returns the node id given the values of p and r. A map is a perfect container if the lookup is done using the integer first key (id). Does anyone have a suggestion on how to solve this particular problem?

Thanks much! AsvP.

最满意答案

地图<>不起作用。 C ++关联容器基于关键的相等性工作，并且为平等而比较浮点数并不能很好地工作。

这听起来像你需要找到一个节点，给定x和y。 最好的方法将取决于你想要完成的。 您是否试图根据坐标找到最近的节点，或者您是否要计算非常接近节点的坐标，然后您需要找到该节点？

对于第二种情况，您可能会在x或y坐标上排序节点（我将假设x），然后执行二进制搜索以查找哪些节点的x坐标非常接近给定的x。 这通常会选择少量的节点，可以搜索大致正确的y。

（当然，如果节点处于某种可预测的网格中，则应该能够提供一些直接计算的方法，例如，如果有整数格点，则将x和y四舍五入为最接近的整数。）

如果你需要找到最近的节点，那么这会变得有点复杂。 我对此不够了解，但有几何算法的资源。

A map<> won't work. C++ associative containers work on the basis of key equality, and comparing floating-point numbers for equality doesn't work at all well.

It sounds like you need to find a node, given x and y. The best way will depend on what you're trying to accomplish. Are you trying to find the nearest node, given the coordinates, or are you going to calculate coordinates that are very close to a node, and then you need to find the node?

For the second, you'll probably be well off sorting the nodes on either the x or y coordinate (I'll assume the x), and doing a binary search to find which nodes have x coordinates very close to your given x. That will generally select a small number of nodes, which can be searched for the approximately correct y.

(Of course, if the nodes are in some sort of predictable grid, you should be able to provide some means to calculate directly, like round x and y to nearest integer if you've got integral lattice points.)

If you need to find the closest node, well, that gets a bit complicated. I don't know enough about this to help much, but there are resources for geometric algorithms.