0

Problem

I'm working with openstreetmap-data and want to test for point-features in which polygon they lie. In total there are 10.000s of polygons and 100.000.000 of points. I can hold all this data in memory. The polygons usually have 1000s of points, hence making point-in-polygon-tests is very expensive.

Idea

I could index all polygons with an R-Tree, allowing me to only check the polygons whose bounding-box is hit.

Probable new problem

As the polygons are touching each other (think of administrative boundaries) there are many points in the bounding-box of more than one polygon, hence forcing many point-in-polygon-tests.

Question

Do you have any better suggestion than using an R-Tree?

4

2 に答える 2

1

Quad-Trees はラスター化よりもうまく機能しない可能性があります - それらは基本的に 2x2 画像へのラスター化の繰り返しです... しかし、ラスターのテストは可能な限り高速である必要があるため、すべての簡単なケースではラスター化を確実に活用してください。そして、ポイントの 90% を簡単に解決できれば、残りの時間に余裕ができます。

また、最初に重複を削除してください。インデックスは重複することが多く、テストするには明らかに冗長です。

R* ツリーはおそらく試してみるのに良い方法ですが、本当に慎重に実装する必要があります。

あなたが探している操作は、包含空間結合です。使用できる実装はないと思いますが、パフォーマンスの問題については、とにかく自分で慎重に実装します。また、パラメーターを調整し、コードをプロファイリングしてください。

結合の基本的な考え方は、2 つのツリーを構築することです。1 つはポイント用、もう 1 つはポリゴン用です。次に、各ツリーのルート ノードから開始し、リーフ レベルまで以下を再帰的に繰り返します。

  • ディレクトリ以外のノードの場合:
    • 2 つのノードが重なっていない場合: return
    • 展開するディレクトリ ノードをヒューリスティックに決定します (この部分を理解する必要があります。「より大きな拡張」で開始できる場合があります)。
    • 新しい各ノードに再帰的に加えて、開いていない他のノードを新しいペアとして追加します。
  • 葉ノード:
    • 高速テスト ポイントとポリゴンのバウンディング ボックス
    • ポリゴン内の遅いテスト ポイント

ポリゴン、特にポリゴン内の長方形の高速内部テストがある場合、これをさらに加速できます。高速であれば、概算であればそれで十分かもしれません。

詳細については、r-tree 空間結合を検索してください。

于 2014-09-04T17:03:31.843 に答える