経度/緯度ポリゴンを使用して、ロサンゼルスの近隣を定義する geojson オブジェクトがあります。私の Web アプリケーションでは、クライアントは空間イベントのライブ ストリーム (基本的には経度/緯度座標のリスト) を処理する必要があります。クライアント (ブラウザ) で Javascript を使用して、これらの座標を近隣に分類するにはどうすればよいですか?
私は近隣が排他的であると仮定しても構わないと思っています。したがって、座標が近隣 X として分類されると、他の近隣についてそれをさらにテストする必要はありません。
ポイントがポリゴンに含まれているかどうかを判断するという一般的な問題を解決する方法については、ここに一連の優れた回答があります。あなたの場合、最も興味深いと思われる2つのオプションがあります。
@Bubbles が述べたように、最初にバウンディング ボックスのチェックを行います。これは非常に高速で、投影された座標でも保護されていない座標でも問題なく動作するはずです。近傍の SVG パスがある場合は、ネイティブ.getBBox()メソッドを使用してバウンディング ボックスをすばやく取得できます。
特に D3 v3 を使用できる場合は、複雑なポリゴンに対して次に試みることは、オフスクリーン キャンバスにレンダリングし、ピクセルの色をチェックすることです。D3 v3 は、キャンバス パスと SVG パスを生成できるジオ パス ヘルパーを提供します。近隣を事前にレンダリングできれば、これは非常に高速になるのではないかと思います。
更新: これは興味深い問題だと思ったので、ここで一般化されたラスターベースのプラグインを思いつきました: http://bl.ocks.org/4246925
これは、D3 および canvas 要素と連携して、ラスターベースのジオコーディングを行います。フィーチャがキャンバスに描画されると、実際のジオコーディングは O(1) になるため、非常に高速になるはずです。ブラウザ内で簡単にテストすると、1000 ポイントを ~0.5 秒でジオコーディングできます。これを実際に使用している場合は、ここで行うよりもエッジケースをうまく処理する必要があります。
ブラウザーで作業していない場合でも、node-canvasを使用してこれを実行できる場合があります。
これを行ういくつかのライブラリを見てきましたが、それらのほとんどはキャンバス ライブラリであり、必要以上に近似に依存している可能性があり、それらに直接依存する必要のないプロジェクトに適応するのは難しい場合があります。交差点用。
私が考えることができる他の唯一のまともなオプションは、 javascript でレイキャスティングを実装することです。このアルゴリズムはユークリッド幾何学用であり、緯度/経度座標はそうではありません (曲面上の点を示すため) ため、技術的に完全ではありませんが、都市の近隣のような小さな領域では、これが問題になるとは思えません。
基本的にこのアルゴリズムを実行するGoogle マップ拡張機能を次に示します。少し調整する必要がありますが、原則は非常に似ています。大きなことは、座標を 2 つの座標だけのパスに前処理する必要があることですが、それは実行可能なはずです.*
これは決して安価ではありません。分類する必要があるすべてのポイントについて、近隣ポリゴンのすべての線分をテストする必要があります。ユーザーがセッション間で同じ座標を何度も再利用すると予想される場合、データの一部として近隣を保存したくなるでしょう。そうではなく、非常に多くの近隣に対してテストする場合は、実装できる簡単な時間節約手段がいくつかあります。たとえば、すべての近隣の極端な座標を前処理し (最北端、最東端、最南端、最西端のポイントを取得)、これらを使用して町に内接する長方形を定義できます。次に、最初に候補近傍のポイントが長方形の内側にあるかどうかを確認してから、完全なレイ キャスティング アルゴリズムを実行します。
*このルートに進むことに決め、このコードを適応させるのに問題がある場合は、喜んでお手伝いします