我需要一个空间索引C

Question

我正在处理my gEDA fork并希望摆脱现有简单的基于磁贴的系统有利于实际空间索引。

有效找到点的算法还不够：我需要查找具有非零范围的对象。想象一下具有边界矩形的对象，这几乎可以捕捉我在索引中需要的详细程度。给定一个搜索矩形，我需要能够有效地找到边界矩形位于内部或与搜索矩形相交的所有对象。

索引不能是只读的：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）。这显然足以使大多数原理图足够快地进行搜索，但其实现方式会导致其他问题：太多的函数需要指向事实上的全局对象。瓷砖的几何形状也是固定的：仅通过平移（可能缩放）到仅由一个瓷砖覆盖的区域，就可以完全击败该瓷砖系统。

一个合理的答案是保持拼贴系统的元素，但要解决它的弱点：教它跨越整个空间，并在必要时进行细分。但是我希望别人在我专注地决定这是最好的方法之前补充两分钱。

Answer 1

点和线混合的一个很好的数据结构可能是一个R树或它的一个导数（例如R * -Tree或Hilbert R-Tree）。鉴于你希望这个索引是动态和可序列化的，我认为使用SQLite's R*-Tree module将是一个合理的方法。

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

Answer 2

这听起来像一个非常适合四叉树的应用程序（假设您只对2D感兴趣）。quadtree是分层的（适合搜索），它的空间分辨率是动态的（允许在需要它的区域获得更高分辨率）。

我一直滚我自己的四叉树，但这里是出现合理的库：http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C

Answer 3

这是很容易做到。做得很快很难。听起来像是我工作过的一个问题，那里有大量的最小值，最大值和给定值，它必须返回有多少最小值，最大值对与该值重叠。你只是在两个维度。所以你在两个方向上做两棵树。然后在结果上做一个十字路口。这真的很快。

#include <iostream> 
#include <fstream> 
#include <map> 

using namespace std; 

typedef unsigned int UInt; 

class payLoad { 
public: 
    UInt starts; 
    UInt finishes; 
    bool isStart; 
    bool isFinish; 
    payLoad() 
    { 
     starts = 0; 
     finishes = 0; 
     isStart = false; 
     isFinish = false; 
    } 
}; 

typedef map<UInt,payLoad> ExtentMap; 

//============================================================================== 
class Extents 
{ 
    ExtentMap myExtentMap; 

public: 

    void ReadAndInsertExtents (const char* fileName) 
    { 
     UInt start, finish; 
     ExtentMap::iterator EMStart; 
     ExtentMap::iterator EMFinish; 

     ifstream efile (fileName); 
     cout << fileName << " filename" << endl; 

     while (!efile.eof()) { 
      efile >> start >> finish; 
      //cout << start << " start " << finish << " finish" << endl; 
      EMStart = myExtentMap.find(start); 
      if (EMStart==myExtentMap.end()) { 
       payLoad pay; 
       pay.isStart = true; 
       myExtentMap[start] = pay; 
       EMStart = myExtentMap.find(start); 
       } 
      EMFinish = myExtentMap.find(finish); 
      if (EMFinish==myExtentMap.end()) { 
       payLoad pay; 
       pay.isFinish = true; 
       myExtentMap[finish] = pay; 
       EMFinish = myExtentMap.find(finish); 
      } 
      EMStart->second.starts++; 
      EMFinish->second.finishes++; 
      EMStart->second.isStart = true; 
      EMFinish->second.isFinish = true; 

//   for (EMStart=myExtentMap.begin(); EMStart!=myExtentMap.end(); EMStart++) 
//    cout << "| key " << EMStart->first << " count " << EMStart->second.value << " S " << EMStart->second.isStart << " F " << EMStart->second.isFinish << endl; 

     } 

     efile.close(); 

     UInt count = 0; 
     for (EMStart=myExtentMap.begin(); EMStart!=myExtentMap.end(); EMStart++) 
     { 
       count += EMStart->second.starts - EMStart->second.finishes; 
       EMStart->second.starts = count + EMStart->second.finishes; 
     } 

//  for (EMStart=myExtentMap.begin(); EMStart!=myExtentMap.end(); EMStart++) 
//   cout << "||| key " << EMStart->first << " count " << EMStart->second.starts << " S " << EMStart->second.isStart << " F " << EMStart->second.isFinish << endl; 

    } 

    void ReadAndCountNumbers (const char* fileName) 
    { 
     UInt number, count; 
     ExtentMap::iterator EMStart; 
     ExtentMap::iterator EMTemp; 

     if (myExtentMap.empty()) return; 

     ifstream nfile (fileName); 
     cout << fileName << " filename" << endl; 

     while (!nfile.eof()) 
     { 
      count = 0; 
      nfile >> number; 
      //cout << number << " number "; 

      EMStart = myExtentMap.find(number); 
      EMTemp = myExtentMap.end(); 

      if (EMStart==myExtentMap.end()) {   // if we don't find the number then create one so we can find the nearest number. 
       payLoad pay; 
       myExtentMap[ number ] = pay; 
       EMStart = EMTemp = myExtentMap.find(number); 
       if ((EMStart!=myExtentMap.begin()) && (!EMStart->second.isStart)) 
       { 
        EMStart--; 
       } 
      } 

      if (EMStart->first < number) { 
       while (!EMStart->second.isFinish) { 
        //cout << "stepped through looking for end - key" << EMStart->first << endl; 
        EMStart++; 
        } 
       if (EMStart->first >= number) { 
        count = EMStart->second.starts; 
        //cout << "found " << count << endl; 
        } 
      } 
      else if (EMStart->first==number) { 
       count = EMStart->second.starts; 
       } 

      cout << count << endl; 

      //cout << "| count " << count << " key " << EMStart->first << " S " << EMStart->second.isStart << " F " << EMStart->second.isFinish<< " V " << EMStart->second.value << endl; 

      if (EMTemp != myExtentMap.end()) 
      { 
       myExtentMap.erase(EMTemp->first); 
      } 
     } 
     nfile.close();  
    } 

}; 

//============================================================================== 

int main (int argc, char* argv[]) { 
    Extents exts; 

    exts.ReadAndInsertExtents ("..//..//extents.txt"); 
    exts.ReadAndCountNumbers ("..//../numbers.txt"); 

    return 0; 
} 

范围测试文件为1。的5MB：

0 200000 
1 199999 
2 199998 
3 199997 
4 199996 
5 199995 
.... 
99995 100005 
99996 100004 
99997 100003 
99998 100002 
99999 100001 

号的文件是这样的：

102731 
104279 
109316 
104859 
102165 
105762 
101464 
100755 
101068 
108442 
107777 
101193 
104299 
107080 
100958 
..... 

即使从磁盘中读取两个文件，盘区1.5MB和数字分别为780K和真正的大数值和查找，这在几分之一秒内运行。如果在记忆中它会闪电般快速。

Answer 4

您的需求听起来非常类似于用于游戏和物理模拟的碰撞检测算法。有几个开源的C++库可以在2-D (Box2D)或3-D (Bullet physics)中处理此问题。虽然你的问题是针对C，你可能会发现他们的文档和实现有用。

这通常被分成two phases：

1. 快速宽泛阶段近似于通过轴对齐包围盒（AABB）中的对象，并且确定对那个触摸或的AABB重叠。
2. 一个较慢的窄阶段，用于计算AABB接触或重叠的物体对的几何重叠点。

物理引擎还使用空间一致性来进一步减少比较的对象对，但这种优化可能不会帮助您的应用程序。

通常用O（N log N）算法实现宽相位，如Sweep and prune。您可以通过将其与当前平铺方法结合使用来加速实现（one of Nvidia's GPUGems描述了这种混合方法）。对于每一对来说，这个狭窄的阶段是相当昂贵的，并且可能会为你的需要矫枉过正。 GJK algorithm通常用于此步骤中的凸对象，但对于更特殊的情况（例如：盒/圆和盒/球碰撞）存在更快的算法。