我正在研究my gEDA fork，并希望摆脱现有的基于简单图块的系统，而转而使用真实的空间索引2。
有效查找点的算法还不够:我需要查找非零范围的对象。考虑具有边界矩形的对象，这几乎捕获了我在索引中需要的详细程度。给定一个搜索矩形，我需要能够有效地找到边界矩形在搜索矩形内或与搜索矩形相交的所有对象。
索引不能是只读的:gschem是一个原理图捕获程序，它的全部目的是在原理图上移动内容。因此，情况将会发生变化。因此，尽管我可以负担得起插入要比搜索贵一点，但它却不能贵太多，并且删除也必须既可行又便宜。但是最重要的要求是渐近行为:如果不能为O(1)，则搜索应为O(log n)。插入/删除最好应为O(log n)，但O(n)可以。我绝对不希望> O(n)(每个 Action ；显然，对于全对象操作，O(n log n)是期望的)。
我有什么选择？我对评估the various options不够聪明。理想情况下，有一些C库可以为我做所有聪明的事情，但是我会机械地实现一个算法，我可能会或可能不会完全理解我是否必须这样做。 gEDA顺便使用了glib，如果这有助于提出建议的话。
脚注:
1标准gEDA将示意图划分为固定数量(当前为100个)的“平铺”，用于加速在边界矩形中搜索对象。显然这足以使大多数原理图足够快地进行搜索，但是这样做的方式会引起其他问题:太多的函数需要指向实际全局对象的指针。磁贴的几何形状也固定:通过平移(并可能缩放)到仅一个磁贴所覆盖的区域，有可能完全击败该平铺系统。
2一个合理的答案是保留平铺系统的元素，但要纠正其薄弱环节:教导其覆盖整个空间，并在必要时进行 segmentation 。但是我希望其他人加二分钱，然后再专心决定这是最好的方法。
最佳答案
混合使用点和线的一种不错的数据结构是R树或它的派生词之一(例如R * -Tree或Hilbert R-Tree)。考虑到您希望该索引是动态的和可序列化的，我认为使用SQLite's R*-Tree module是一种合理的方法。
如果您可以忍受C++，则libspatialindex具有成熟且灵活的R树实现，它支持动态插入/删除和序列化。