1

...感谢阅读...

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

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

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;

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

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

非常感谢！副总裁。

4

6 回答 6

6

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

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

对于保存要渲染的对象的东西，一个通用结构是二进制空间分区树，它允许有效剔除绝对不可见或被其他对象遮挡的对象。

编辑; 我错过了您正在按浮点进行索引。这通常是一个坏主意（因为大多数标准地图所要求的准确性会导致与浮点行为的不稳定性有关的问题）。除非你真的想要这种行为

在这种情况下，您需要有某种处理方式，例如：

  • 对您的域进行分块，以便您可以准确地指向其中的一小部分，并防止多个节点占用同一块空间。
  • 有一些方法来划分你的空间（可能需要对节点集中度较高的区域进行自适应细分），以便在请求点 p,r 时，你会得到该区域中存在的一组（可能是空的）节点。
于 2009-02-13T16:32:44.450 回答
1

你看过可用的几何库吗，我不是这个领域的专家，最近在 boost 邮件列表的预览中听说了GTL 。

于 2009-02-13T16:37:45.763 回答
1

与查找问题无关，而是与您Nodes使用new. 如果地图拥有节点，就像您的情况一样，您可以简单地说：

map <int, Node> mymap;     // map of Nodes, not pointers to Nodes
...
myMap[i] = Node( whatever );

这将大大简化您的内存管理。在 C++ 中，您应该尽可能避免显式动态内存分配new。

于 2009-02-13T16:44:29.507 回答
0

你到底想做什么？

如果您有 2 个坐标代表 3d 位置，那么我假设它们是某些参数化函数的输入，该函数会产生 3 个顶点分量……如果是这种情况，那么节点实际上是做什么用的？在大多数情况下，这种参数化可用于直接生成网格。

作为一个例子，考虑一个单位球体，它接受参数 u,v (0...2PI) 和 (0...PI) 并通过执行以下操作将它们转换为坐标：

x = sin(u)*cos(v);
y = sin(u)*sin(v);
z = cos(u);

这可用于通过在适当范围内改变 u 和 v 并合并任何重复的顶点来创建网格。例如，取 u = 0、u = 0.1、v = 0 和 v = 0.1，您可以创建四个顶点 V(u,v)，从而可以创建两个三角形。由于我假装这是一般情况而不是特殊情况，因此您必须执行诸如检查顶点是否重复并合并它们以及检查退化三角形并删除它们之类的操作。

于 2009-02-13T16:40:53.760 回答
0

地图<> 不起作用。C++ 关联容器在键相等的基础上工作，比较浮点数的相等性根本不起作用。

听起来你需要找到一个节点，给定 x 和 y。最好的方法将取决于您要完成的工作。您是要在给定坐标的情况下找到最近的节点，还是要计算非常接近节点的坐标，然后您需要找到该节点？

对于第二个，您可能会很好地在 x 或 y 坐标（我假设 x）上对节点进行排序，并进行二进制搜索以查找哪些节点的 x 坐标非常接近给定的 x。这通常会选择少量节点，这些节点可以搜索到近似正确的 y。

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

如果您需要找到最近的节点，那会有点复杂。我对此知之甚少，无法提供太大帮助，但有几何算法的资源。

于 2009-02-13T16:46:29.643 回答
0

杰里科一针见血。我正在使用两个参数来生成 3D 网格。这两个参数是柱坐标。一个是角度，第二个是沿轴的 z。半径是一个常数，就像他的球体示例一样。我可以创建一个网格，但我需要更新它，并且执行更新的函数不会将 id 作为输入参数。它通过使用这些参数 p 和 r 来获取“原始位置”。

于 2009-02-13T16:51:15.670 回答