5

与えられたポリゴンのセットに点が存在するかどうかを見つける方法は？私は次のような座標を持っています

polygonA = 1(0,0),2(0,5),3(3,4),4(3,5),5( 2,2)
polygonB = 1(10,10),2(10,15),3(13,14),4(13,15),5(12,12)

（6,4）としてポイントがあります。このポイントがこのポリゴンのいずれかにあるか、両方にあるか、またはどのポリゴンに最も近いかを検索したいと思います。

そのようなデータ（ポリゴン）を保存する方法は？この検索を行うためのシステム/データベース/アルゴリズムはありますか？

更新：このような迅速な対応に感謝します...私はもっと具体的にする必要があると思います...

検索方法=はい...同じアルゴリズムとライブラリのリストを取得しました。

保存方法=私の調査に基づくSQLとNoSQLデータベースには解決策があります。NoSQL=MongoDbは私が必要としていたものに最も近いようです。しかし、問題は、「db.places.find（{"loc"：{"$ within"：{"$ hybrid"：polygonB}}}）」のようにクエリできることです。しかし、db.places.find（{"のようにクエリを作成することはできません。 loc "：{" $ within "：{}}}）SQLはpostgreとopenGISをチェックして助けを求めました。しかし、それが可能かどうかはわかりません。

誰かがそれを手伝ってくれるなら...よろしくお願いします。

4

2 に答える 2

3

基本的な方法 (ポリゴンの数が少ない場合) は、すべてのポリゴンをコレクションに格納し、要素をループしてポイントがポリゴンの内部にあるかどうかを確認することです。

一方、かなりの数のポリゴンがある場合は、標準ライブラリでは利用できない R ツリー データ構造を使用することをお勧めします。R ツリー オプションを使用する場合は、このプロジェクトを確認する必要があります: http://sourceforge.net/projects/jsi/。

R ツリーを使用すると、四角形 (この場合はポリゴンのバウンディング ボックス) にインデックスを付けることができます。したがって、R ツリーを使用すると、少数の候補ポリゴンを非常に高速に見つけることができます。次に、候補リストをループして最終結果を取得できます。

于 2012-05-27T13:53:00.710 に答える
1

GeneralPath クラスを使用すると、ポイントがポリゴンと交差するかどうかを判断するのに役立ちます。まず、座標を追加して GeneralPath を作成します。

    GeneralPath gp = new GeneralPath();
    double[] x = ...
    double[] y = ...
    gp.moveTo(x[0], y[0]);
    for (int i =1; i < x.length; i++) {
        gp.lineTo(x[i], y[i]);
    }
    gp.closePath();

    if (gp.contains(pointX, pointY)) {
        ...
    }

ポイントがどのポリゴンに近いかという問題の場合、これは、ソリューションが必要な精度に少し依存します。

正確な解の場合、これは (最適化なしで) 次のようになります。

  • ポイントと、各ポリゴンの頂点を結ぶ各線 (セグメント) との間の最短距離を取得します (Java2D は明らかにこの方法を提供していませんが、点から線までの最短距離はかなり単純な計算です)
  • 点までの距離が最も短い直線を持つ多角形は?

実際には、一部のアプリケーションではこのプロセスを概算できます。たとえば、これをはるかに効率的に行うことができます。

  • 各ポリゴンの境界矩形の中心点を取得します (GeneralPath.getBounds() がこれを提供します)
  • クエリポイントとこれらの各中心点の間の距離を取り、どれが最も近いかを確認します。

正確な答えが必要な場合は、これらの手法を組み合わせて、すべての頂点の検索を最適化できます。たとえば、「中心点」(上記で定義) までの距離でポリゴンを並べ替えることができます。最小距離から最大距離まで検索します。これまでに見つかったセグメントまでの最小距離が d の場合、クエリ ポイントからその「中心点」までの距離が d + r である多角形 P を自動的に除外できます。ここで、r は長さの半分です。 P の境界矩形の対角線 (つまり、簡単にするために、その境界ボックスの周りに境界円を想像し、その境界円までの距離が、他の多角形でこれまでに見つかった最も近い点よりも遠いことを確認します)。

データベースについてはよくわかりません。ポリゴンは一連のポイントとして定義されています。これらをメモリ/ファイルに保存する方法は、アルゴリズムに本質的な違いはありません。

于 2012-05-27T15:21:36.253 に答える