英国の郡の輪郭を定義するポリゴンがあります。これらの形状は非常に詳細 (それぞれ 10k から 20k ポイント) であるため、関連する計算 (ポリゴン P 内の点 X ですか?) は計算コストが非常に高くなります。
したがって、ポリゴンを「サブサンプリング」して、同様の形状を取得しますが、ポイントは少なくします。そうするためのさまざまなテクニックは何ですか？
些細なことは、ポイントごとに1つ取得することですN（したがって、係数でサブサンプリングしますN）が、これは「粗雑」すぎると感じます。私はむしろ、ポイントの平均化、またはその味の何かをしたいと思います。ポインターはありますか？
2 つの解決策が思い浮かびます。
1) 英国の地図は適度に四角いので、郡でビットマップをレンダリングすることを選択できます。それぞれに特定の色を割り当て、境界線を 1 または 2 ピクセルの太さの黒い線でレンダリングします。これは、サンプルがたまたま境界上にある場合にのみ、高価な内部/外部計算を実行する必要があることを意味します。ビットマップが大きいほど、これが発生する頻度は低くなります。
2) 郡の輪郭を単純化します。再帰的なRamer–Douglas–Peuckerアルゴリズムを使用して、境界を再帰的に単純化できます。結果をキャッシュするようにしてください。また、郡の境界全体ではなく、共有された境界に対してのみこれを解決して、ギャップがないようにする必要がある場合もあります。これはかなり難しいかもしれません。
ここで、あなたの問題を正確に扱っているプロジェクトを見つけることができます。主にポイントで「塗りつぶされた」領域で機能しますが、「周囲」タイプの定義で機能するように設定できます。
領域の計算に k 最近傍法を使用します。
サンプル:
ここでは、論文のコピーをリクエストできます。
計算を要求するためのオンライン サービスを提供する予定だったようですが、私はそれをテストしておらず、おそらく実行されていません。
チッ！
ここでは、ポリゴンの三角形分割が役立ちます。多くのポリゴンをチェックする必要がありますが、これらは現在三角形であるため、チェックが容易であり、いくつかの最適化を使用して、特定の領域またはポイントをチェックするポリゴンの小さなサブセットのみを決定できます。
三角形だけでなく、ポリゴンに必要なすべてのアルゴリズムがあるように見えるので、三角形分割後または三角形の数が多すぎる場合に、小さすぎるいくつかの三角形をマージすることもできます。