google-maps - 一連の点が与えられたときに、どのように最も多くの終点を見つけるか?

Question

ポイントのセットから最も端点を見つけ、それらを通るポリゴンを描画する必要があります。タスクは次のようになります。

1) 赤い点はLatLng、マップ上の一連のポイントです。

2) それらの中で最も遠いものを特定し、それらを通るポリゴン (緑の線) を描く必要があります。

座標が分かっていれば多角形を描くのは難しくありません。しかし、最も遠い点を特定する方法がわかりません。

更新 1:

今のところ、このタスクには名前があることがわかりました。「頂点カバー」といいます。

更新 2:

このタスクは「凸包」と呼ばれます。これは、タスクの視覚的な実装ですhttp://computacion.cs.cinvestav.mx/~anzures/geom/hull.php

Answer 1

ドロネー三角形分割を使用して、一連の点の凸包を計算できます。次に、超三角形に接続されたすべての頂点を探すことができます。私の php クラスの凸包は、@ phpclasses.org からダウンロードできます。php クラスの凹型ハルも書きました。カントリー シェイプは常に凸型とは限らないため、凹型の船体をお勧めします。以下に例を示します: http://www.phpdevpad.de/geofence。