我正在开发一个非常简单易用但功能强大的2D跨平台CAD软件包。我知道已经有一些了,但我这样做更多的是为了学习,而不是其他任何事情。
我使用OpenGL进行渲染,我希望能够在鼠标移动时高亮显示每个实体。我有算法可以找到实体上最近的点等,但我不想每次移动都扫描实体的整个数据存储。
我看过四叉树、kd树等,但我不知道如何使用它们来缩小整个实体的焦点。我看到的大多数例子似乎都是以"点"为导向的。我假设我想根据边界矩形进行索引,然后对该矩形内的实体进行最近点搜索。
有人能为我指明正确的方向吗?
思考"Kd树"的方向是正确的。现在,您必须更进一步,将点扩展到多维基元中,这些基元具有位置和其他参数。Kd毕竟是指"K维度"。
因此,对于圆或圆弧,您可以将中心位置存储在树的前两个维度中,然后将半径存储在第三个维度中(对于一组二维基本体)。对于所有其他不是圆形的基元,只需假设一个圆形边界区域。
对于线性基元,您可能需要查看BSP树。当然,你可以将Kd的概念与BSP结合起来,比如将Kd样节点用于曲线基元,将BSP用于由线性凸段限定的基元。
听起来你在寻找类似R树的东西,R树是基于面向轴的边界框的树,其中(与K-d树不同)允许兄弟子树的框重叠。如果我没有记错的话,有许多基于不同更新启发法的变体。
关于空间数据结构的权威参考,其中包括许多关于R树及其亲属的参考:
- 《多维和度量数据结构基础》,Hanan Samet著
空间分区背后的理念是减少需要执行的测试数量(及其计算需求),以便获得可以使用更精细方法进行测试的基元子集。
必须使用整个实体的边界框,并在移动鼠标时首先确定鼠标下的实体,这一点是正确的。
你还有一些其他选择:
- 如此链接所示的空间哈希。这允许您使用低成本的距离函数执行线性(或分层)搜索(这适用于2D,但易于扩展到3D)
- OpenGL拾取-如果你在渲染代码中实现了一个足够好的剔除方法,你可以使用OpenGL拾取来快速确定鼠标下的当前对象。如果你的筛选代码很快,这也会很快
还有很多我肯定我错过了——我会随着时间的推移添加它们。:)希望这能有所帮助!