マップ上のポイントをポリゴンに変換する

Question

マップには何千ものポイントがあります。ポイントは、人が移動するにつれて定期的に測定されるため、各ポイントの位置はウィンドウ内でランダムですが、データを見ると、取得されたパスがわかります。 データをより速くレンダリングするには、クラスター化された点をポリゴンに変換して描画する必要があります（ズームレベルの右ポリゴンの詳細を選択することで、失われた詳細を処理できます）。

このようなことを行うための優れた高速アルゴリズムはありますか？

Answer 1

多角形をどのように表現しますか？移動したパスの領域をカバーする閉領域のようにポリゴンを意味しますか（境界のみ）？または、訪問されたすべてのポイント間の線分の正確なポリゴンですか？後者は、ポイントを持つよりも多くのコーナーを持つポリゴンとなるため、ポイント自体よりも描画が高速になることはありません。

人が（都市の一部をカバーする配達ドライバーのような）エリアを移動する場合、ポイントの凸包によって彼の「カバーエリア」を近似することができます。これは、データセットにN個の点がある場合は、3とNのコーナーの間にある閉じた凸多角形です。

定義

http://mathworld.wolfram.com/ConvexHull.html

アルゴリズム

http://en.wikipedia.org/wiki/Convex_hull_algorithms

あなたはパスではなく、いくつかのカバーエリアの近似値を作成したい場合、あなたは常に、粗を作ることができますLODアルゴリズムは、（例えば）7点ごと、次に5点ごと、3点ごとに描画するユーザーがさらにズームしたときに表示されます。より洗練されたLODアルゴリズムは、点p0と点p1から始まり、点を通る方向を使用し、点線から点p2までの距離を見ることができます。 p2が行に十分接近していれば、それはスキップされ、p3が調べられます。旅行の方向に十分大きな変化がある場合は、最後の2点を現在のコースとしてマークし、繰り返します。許容される方向の変更は、描かれる点の数を決定するLODパラメータになります。このアルゴリズムは、（方向が変わる）パス上の「重要な」点を近似しようとします。

Answer 2

正確なのパスを知ることは不可能だと思いますが、特定のポイントに最も近いポイントがパス上の次のポイントであると仮定することはかなり合理的な仮定になります。どのサイズのポリゴンを扱っているのかよく分かりませんが、最終的にマップ上のどのポイントが現在のポイントに最も近いかを計算し、そのポイントがポリゴンの次のポイントになるように計算します。多角形が非常に大きい場合は、精度を確保するために点間の大きな円の距離を計算する必要があります。