9

の空間インデックスデータ構造の王様を実装したいと思いMKAnnotationsます。現在、距離基準に基づいてそれらをフィルタリングしようとすると、ひどく遅くなります（3〜4kの場所、現在は単純なダブルで非常に遅いfor...）。

MKAnnotationsのクラスターを作成して、別のクラスターに近いかどうかを判断したいと思います。また、これらの場所はある程度（作成）の順序であり、「前」/「次」の機能が「ジャンプ」するために必要になります（これは必須ではありません）。kd-treeと構造について読んだことがr-treeあり、どちらもフィルタリング/クラスタリングの高速距離/隣接取得オプションを満たしているようですが、どちらが私に最適か、または他のオプションもあるかどうかはわかりません。どのアルゴリズム/データ構造を使用する必要がありますか？

更新：これらの場所をCore Dataデータベースに保存します。これらは、パスを表します。マップを開くと、それらは配列にフェッチされ、距離の計算と注釈の作成にその配列を使用します。ユーザーがマップを移動/ズームするとき、私はそれらをループして、マップ上で何を変更する必要があるかを決定するので、全体が少し静的です。私が理解したように、私が木を使用している場合、そこに場所を保存することができ、ズーム/移動が発生したときに、それを検索して新しい領域の場所を取得するだけです。これは本当ですか ？

動的な場合でも、この配列に新しい場所を追加できる場合、それは1回の挿入であり、ほとんど発生しません。

4

2 に答える 2

8

それはあなたの使用パターンが何であるか（例えば、私の書き込みがどのようにメモリ内またはディスク上にあるか）とあなたのデータがどのように見えるか（それがどのように分散されるか）に大きく依存します。

Rツリーはバランスが取れており、更新できるため、優れています。私の経験では、R *ツリーは分割戦略があるため、他のバリアントよりも明らかに優れています。利点は、他の戦略よりも多くの正方形のページを生成するため、多くのクエリでスキャンする必要のあるページが少なくなることです。

kd-treesは、メモリ内にあり、静的である場合に適しています。それらを更新することは非常に悪いです、あなたはかなり頻繁にインデックスを再構築する必要があるでしょう。

また、データがあまり頻繁に変更されない場合は、Rツリーの一括読み込みが非常にうまく機能します。Sort-Tile-Recursive一括読み込みを実行できます。これは、基本的に（部分的に）XとYでデータを交互に並べ替える必要があるO(n log n)ため、ツリーを構築するのに時間がかかります。バイナリ分割の代わりにマルチ分割することを除いて、kdツリーの一括読み込みと非常によく似ています。これはとても人気があります。

さらに、各ページのオブジェクトの数を追跡できます。地図上に物事を表示するとき、ページが画面上で小さすぎる（つまりマーカーよりも小さい）場合は、早期に停止することをお勧めします。この時点では、そのページをスキャンするのではなく、オブジェクトの数を取得し、ユーザーがズームインするまでそれをクラスター化されたマーカーとして表示します。

限られた価値のドメインを持つ2Dデータの場合、単純なことを見落とさないでください。四分木も非常にうまく機能します！シンプルさにより、物事の最適化がはるかに簡単になります。または、従来のグリッドアプローチ。ユーザーが注釈を領域に広げる傾向がある場合（すべてを1つの場所に配置しない場合）、整数のx、yグリッド座標を計算し、それらをハッシュして各グリッドセルのリストを作成できます。

于 2012-10-03T21:02:40.433 に答える
0

私はiOS開発者ではありませんが、ドキュメントを調べて次のことを見つけました。

MKMapView.annotationsInMapRect：

指定されたマップ長方形にある注釈オブジェクトを返します。

(NSSet *)annotationsInMapRect:(MKMapRect)mapRect

パラメーター

  • mapRect：注釈を検索するマップの部分。

戻り値 mapRectにある注釈オブジェクトのセット。

説明 このメソッドは、マップの特定の部分にある注釈オブジェクトをすばやく取得する方法を提供します。このメソッドは、アノテーションプロパティ内のオブジェクトを自分で線形検索するよりもはるかに高速です。

これは、NKMapViewすでに注釈が空間インデックス構造に編成されていることを示しています。この方法はあなたのニーズを満たしますか？

そうでない場合は、効率を気にするのではなく、2D空間インデックス構造の既存のオープンソース実装を探し、最高のドキュメント、最もクリーンなインターフェイスなどを備えたものを選択します。コードフォームを最初から作成する必要がある場合は、クアッドツリーを実装するのが最も簡単だと思います。一方、Rツリーに関するウィキペディアの記事は、KDツリーやクアッドツリーよりもマッピングをより具体的に対象としているようです。

于 2012-10-03T19:00:39.410 に答える