2

我正在研究我希望是一个非常简单易用但功能强大的 2D 跨平台 CAD 软件包。我知道周围已经有一些这样的，但我这样做更多是为了学习经验而不是其他任何事情。

我正在使用 OpenGL 进行渲染，并且我希望能够在鼠标移过它时突出显示每个实体。我有用于查找实体上最近点的算法等，但我不想为每个动作扫描整个实体数据存储。

我看过四叉树、kd 树等，但我迷失的是如何使用它们来缩小整个实体的焦点。我见过的大多数示例似乎都是面向“点”的。我假设我想根据边界矩形进行索引，然后在该矩形内搜索那些实体的最近点。

谁能指出我正确的方向？

4

3 回答 3

1

听起来您正在寻找类似R-trees的东西，它们是基于轴方向边界框的树，其中（与 Kd 树不同）兄弟子树的框允许重叠。如果我没记错的话，有许多基于不同更新启发式的变体。

关于空间数据结构的权威参考，其中包括很多关于 R-trees 及其亲属的内容：

  • 多维和度量数据结构的基础, Hanan Samet
于 2012-07-23T16:59:22.757 回答
1

思考“Kd 树”走向了正确的方向。现在您必须更进一步，将您的点扩展到具有位置和附加参数的多维图元。毕竟，Kd 的意思是“K 个维度”。

因此，对于圆或圆弧，您可以将中心位置存储在树的前两个维度中，然后将半径存储在第三个维度中（对于一组 2d 基元）。对于所有其他非圆形的基元，只需假设一个圆形边界区域。

对于线性基元，您可能需要查看 BSP 树。当然，您可以将 Kd 的概念与 BSP 结合起来，例如将 Kd 类节点用于弯曲图元，将 BSP 用于以线性凸段为界的图元。

于 2012-07-23T16:47:32.263 回答
0

空间分区背后的想法是减少您需要执行的测试数量（及其计算需求），以便获得可以使用更精细方法测试的基元子集。

您必须使用整个实体的边界框并首先确定移动鼠标时位于鼠标下方的实体是正确的。

您还有其他一些选择：

  1. 如此链接中所示的空间散列。这允许您使用低成本距离函数（这适用于 2D，但易于扩展到 3D）执行线性（或分层）搜索。
  2. OpenGL 拾取 - 如果您在渲染代码中实现了足够好的剔除方法，则可以使用OpenGL 拾取来快速确定鼠标下的当前对象。如果你的剔除代码很快，这也会很快。

还有许多其他我确定我错过了 - 我会在我想到更多时添加它们。：） 希望这可以帮助！

于 2012-07-23T16:55:20.003 回答