我需要C中的空间索引

Question

我正在研究我的gEDA分支,并希望摆脱现有的简单的基于区块的系统¹,而不是真正的空间索引².

有效地找到点的算法是不够的:我需要找到具有非零范围的对象.考虑具有边界矩形的对象,这几乎可以捕获索引中所需的细节级别.给定一个搜索矩形,我需要能够有效地找到其边界矩形在搜索矩形内部或相交的所有对象.

索引不能是只读的:gschem是一个原理图捕获程序,它的全部内容是在原理图中移动.所以事情将变得一团糟.因此,虽然我可以负担得起插入比搜索更昂贵,但它不能太昂贵,并且删除也必须既可能又合理便宜.但最重要的要求是渐近行为:如果不能是O(1),搜索应该是O(log n).插入/删除最好应为O(log n),但O(n)可以.我绝对不希望任何事情> O(n)(每个动作;显然O(n log n)是全对象操作的预期).

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

脚注:

¹标准gEDA将原理图分为固定数量(当前为100个)的"瓦片",用于加速搜索边界矩形中的对象.这显然足以使大多数原理图足够快以进行搜索,但它的完成方式会导致其他问题:太多的函数需要指向事实上的全局对象的指针.瓷砖几何形状也是固定的:只要通过平移(并可能缩放)到仅由一个瓷砖覆盖的区域,就可以完全打败这种拼接系统.

²合理的答案是保留平铺系统的元素,但要解决其缺点:教导它跨越整个空间,并在必要时进行细分.但我希望其他人在我自我决定这是最好的方式之前加上他们的两分钱.

Answer 1

点和线混合的一个很好的数据结构是 R 树或其衍生物之一（例如 R* 树或希尔伯特 R 树）。考虑到您希望该索引是动态且可序列化的，我认为使用SQLite 的 R*-Tree 模块将是一种合理的方法。

如果您可以容忍 C++，libspatialindex有成熟且灵活的 R 树实现，支持动态插入/删除和序列化。