c - 我需要 C 中的空间索引

Question

我正在研究 my gEDA fork并希望摆脱现有的简单的基于图 block 的系统¹，转而采用真正的空间索引²。

有效找到点的算法是不够的:我需要找到非零范围的对象。考虑具有边界矩形的对象，这几乎捕获了我在索引中需要的详细程度。给定一个搜索矩形，我需要能够高效地找到边界矩形在搜索矩形内或与搜索矩形相交的所有对象。

索引不能是只读的:gschem 是一个原理图捕获程序，它的全部目的是在原理图周围移动东西。所以事情将会发生变化。因此，虽然我可以承受插入比搜索稍微贵一点，但也不能贵很多，而且删除也必须既可行又相当便宜。但最重要的要求是渐近行为:如果不能为 O(1)，则搜索应该为 O(log n)。插入/删除最好是O(log n)，但O(n)也可以。我绝对不想要任何东西 > O(n)(每个操作；显然，所有对象操作都需要 O(n log n))。

我有哪些选择？我觉得不够聪明来评估the various options .理想情况下，会有一些 C 库可以为我做所有聪明的事情，但我会机械地实现一个算法，如果我必须的话，我可能会或可能不会完全理解。顺便说一句，gEDA 使用 glib，如果这有助于提出建议。

脚注:

¹ 标准 gEDA 将原理图划分为固定数量(目前为 100)的“图 block ”，用于加快在边界矩形中搜索对象的速度。这显然足以让大多数原理图足够快地进行搜索，但是这样做的方式会导致其他问题:太多的函数需要指向事实上的全局对象的指针。瓷砖的几何形状也是固定的:只需平移(并可能缩放)到仅由一个瓷砖覆盖的区域，就可以完全击败这个瓷砖系统。

² 一个合理的答案是保留平铺系统的元素，但要修复它的弱点:教它跨越整个空间，并在必要时进行 segmentation 。但在我独断地决定这是最好的方法之前，我希望其他人能加上他们的两分钱。

Answer 1

混合点和线的一个很好的数据结构是 R 树或其衍生物之一(例如 R*-Tree 或 Hilbert R-Tree)。鉴于您希望此索引是动态的和可序列化的，我认为使用 SQLite's R*-Tree module将是一种合理的方法。

如果你能忍受 C++，libspatialindex具有成熟灵活的 R-tree 实现，支持动态插入/删除和序列化。