8

我正在研究我的 gEDA 分支，并希望摆脱现有的简单基于图块的系统1以支持真正的空间索引2。

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

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

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

脚注：

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

2一个合理的答案是保留平铺系统的元素，但要修复它的弱点：教它跨越整个空间，并在必要时细分。但在我独裁决定这是最好的方法之前，我希望其他人加两分钱。

4

4 回答 4

2

您的需求听起来与游戏和物理模拟的碰撞检测算法中使用的非常相似。有几个开源 C++ 库可以在 2-D (Box2D)或 3-D (Bullet Physics)中处理这个问题。尽管您的问题是针对 C 的，但您可能会发现它们的文档和实现很有用。

通常这分为两个阶段：

  1. 通过轴对齐边界框 (AABB) 逼近对象的快速宽相位，并确定接触或重叠的 AABB 对。
  2. 一个较慢的窄阶段，计算 AABB 接触或重叠的对象对的几何重叠点。

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

宽相通常使用 O(N log N) 算法（如Sweep 和 prune ）实现。您可以通过将其与当前的 tile 方法结合使用来加速这一过程（Nvidia 的 GPUGems 之一描述了这种混合方法）。窄阶段对于每对来说都是相当昂贵的，并且对于您的需求来说可能是多余的。GJK算法通常用于此步骤中的凸对象，尽管对于更特殊的情况（例如：盒/圆和盒/球碰撞）存在更快的算法。

于 2012-06-27T14:25:09.647 回答
2

混合点和线的一个很好的数据结构是 R-tree 或其派生类之一（例如 R*-Tree 或 Hilbert R-Tree）。鉴于您希望该索引是动态的和可序列化的，我认为使用SQLite 的 R*-Tree 模块将是一种合理的方法。

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

于 2012-06-27T14:27:44.733 回答
0

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

我总是推出自己的四叉树，但这里有一个看起来很合理的库：http: //www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C

于 2012-06-27T13:59:04.107 回答
-1

这很容易做到。很难做到快。听起来像是我处理的一个问题，其中有大量的最小值、最大值列表，并且给定一个值，它必须返回与该值重叠的最小值、最大值对。你只是在两个维度上拥有它。因此，您可以为每个方向使用两棵树。然后对结果做一个交集。这真的很快。

#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
.....

即使从磁盘读取这两个文件，extent 为 1.5mb，数字为 780k，而且值和查找的数量非常大，运行时间不到几分之一秒。如果在记忆中它会闪电般快速。

于 2012-06-27T14:07:20.927 回答