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) の「タイル」に分割します。これは、外接する四角形内のオブジェクトの検索を高速化するのに役立ちます。これは明らかに、ほとんどの回路図を検索するのに十分なほど高速にするのに十分ですが、その方法は他の問題を引き起こします: あまりにも多くの関数が事実上のグローバル オブジェクトへのポインタを必要とします。タイルのジオメトリも固定されています。1 つのタイルだけでカバーされている領域にパン (および場合によってはズーム) するだけで、このタイル システムを完全に無効にすることができます。

2正当な答えは、タイル システムの要素を維持することですが、その弱点を修正することです。空間全体に広がり、必要に応じて分割するように教えることです。しかし、私が独裁的にこれが最善の方法であると判断する前に、他の人に 2 セント追加してもらいたいと思います。

4

4 に答える 4

2

あなたのニーズは、ゲームや物理シミュレーションの衝突検出アルゴリズムで使用されているものと非常によく似ています。これを 2-D (Box2D)または 3-D (Bullet physics)で処理するオープン ソースの C++ ライブラリがいくつかあります。あなたの質問は C に関するものですが、C のドキュメントと実装が役に立つかもしれません。

通常、これは2 つのフェーズに分割されます。

  1. 軸に沿ったバウンディング ボックス (AABB) によってオブジェクトを近似し、接触またはオーバーラップする AABB のペアを決定する、高速で広範なフェーズ。
  2. AABB が接触またはオーバーラップしているオブジェクトのペアの幾何学的オーバーラップ ポイントを計算する低速の狭いフェーズ。

物理エンジンも空間コヒーレンスを使用して、比較するオブジェクトのペアをさらに減らしますが、この最適化はおそらくアプリケーションには役に立ちません。

ブロードフェーズは通常、 Sweep や pruneなどの O(N log N) アルゴリズムで実装されます。現在のタイル アプローチと組み合わせて使用​​することで、これを高速化できる場合があります ( Nvidia の GPUGems の 1 つがこのハイブリッド アプローチについて説明しています)。狭いフェーズは、ペアごとに非常にコストがかかり、必要に応じて過剰になる可能性があります. GJK アルゴリズムは、このステップの凸オブジェクトによく使用されますが、より特殊なケース (例: ボックス/円およびボックス/球体の衝突) にはより高速なアルゴリズムが存在します。

于 2012-06-27T14:25:09.647 に答える
2

点と線の組み合わせに適したデータ構造は、R ツリーまたはその派生物の 1 つ (たとえば、R* ツリーまたは Hilbert R ツリー) です。このインデックスを動的かつシリアライズ可能にしたい場合、SQLite の R*-Tree モジュールを使用するのが合理的な方法だと思います。

C++ を許容できる場合、libspatialindexには、動的な挿入/削除とシリアル化をサポートする成熟した柔軟な R ツリー実装があります。

于 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

やり方は簡単です。速くするのは難しい。最小、最大値の膨大なリストがあり、その値が重複する最小、最大ペアの数を返さなければならない値が与えられた場所で私が取り組んだ問題のように聞こえます。あなたはそれを二次元で持っているだけです。したがって、各方向に 2 つのツリーを使用して実行します。次に、結果に対して交差を行います。これは本当に速いです。

#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.5 MB でした:

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

ディスクから 2 つのファイルを読み取っても、エクステントは 1.5 MB、数値は 780 K で、非常に多数の値とルックアップがあり、これは一瞬で実行されます。記憶にあれば、電光石火の速さです。

于 2012-06-27T14:07:20.927 に答える