2d矢量图形的最佳数据存储算法

我正在研究我希望使用非常简单但功能强大的2D跨平台CAD软件包。我知道已经有一些这样的东西了，但是我比其他任何东西都更喜欢学习体验。2d矢量图形的最佳数据存储算法

我使用我的OpenGL渲染，我希望能突出每个实体在它的鼠标移动。我有用于查找实体上最近点的算法等，但我不想遍历整个实体的数据存储区以查看每个运动。

我已经看了四叉树，KD树等，但在那里我迷路了怎么那些可以用来缩小对整个实体的焦点。我见过的大多数例子似乎都是以“点”为导向的。我假设我想要基于边界矩形进行索引，然后对该矩形内的那些实体进行最近点搜索。

任何人都可以为我指出正确的方向吗？

来源

2012-07-23 Russ

思考“Kd树”进入正确的方向。现在，您必须更进一步，将您的观点扩展到具有位置和其他参数的多维基元。毕竟，Kd meand“K维”。

因此，在圆形或圆弧的情况下，您应该在树的前两个维度中存储中心位置，然后在第三维中存储半径（对于一组2d原语）。对于其他所有不是圆形的基元，只需假设一个圆形边界区域。

对于你可能要考虑BSP树线性元。当然，您可以将Kd的概念与BSP结合使用，如使用Kd类似弯曲基元的节点和BSP来处理由线性凸起段限定的基元。

来源

2012-07-23 16:47:32 datenwolf

空间分割背后的想法是，以减少测试（和他们的计算需求）的数量，你需要为了得到可以使用更细的方法来测试原语的一个子集来执行。

你说得对，不必使用整个实体的边框和首先确定是什么实体的鼠标下时，被移动它。

您也有一些其他的选择：在this链接显示

空间散列。这使您可以使用低成本的距离函数（这适用于2D，但易于扩展到3D）执行线性（或分层）搜索。
OpenGL的采摘 - 如果你已经实现了你的渲染代码一个足够好的方法扑杀，您可以使用OpenGL picking来快速确定你的鼠标下的当前对象。如果你的剔除代码很快，这也会很快。

还有很多其他的我确信我错过了 - 我会加入他们，因为我想的更多。：）希望这可以帮助！

来源

2012-07-23 16:55:20 Ani

我要对空间哈希进行更多的研究。看起来他们正在使用希尔伯特曲线，我对这些曲线不是很熟悉。我确实看过opengl挑选，但是这个选项仍然意味着我必须渲染实体到背板，所以我仍然需要缩小我渲染的实体的数量。在这一点上，我倾向于Comingstorm关于r-trees的想法。 – Russ 2012-07-23 22:37:43

这听起来像你正在寻找像R-trees这样的树，它是基于轴向边界框的树，其中（与K-d树不同）允许同胞子树的框重叠。如果我没有记错，那么根据不同的更新启发式就会有一些变化。

对空间数据结构明确的参考，其中包括多对R-树和他们的亲属：多维和公制数据结构的

基础，通过哈南沙美

来源

2012-07-23 16:59:22 comingstorm

我只是看了一些信息，我喜欢这个选项。具体来说，它看起来像R *树很适合。 C++似乎有一些很好的选择。谢谢你的提示。 – Russ 2012-07-23 22:30:34

2d矢量图形的最佳数据存储算法

回答

相关问题