二次元の点の集合から最も遠い点を「n」に選択する最適な方法

Question

私は（緯度、経度）の座標を持っています。

(13.0180552378288,77.6811561227539) 
(12.9905166666667,77.7278116666667) 
(12.9381400000000,77.7486000000000) 
and so on..............there can be upto 100 point 

私は実際に私がk initial centroidsが必要k-meansアルゴリズムを実装しています。

k個の点が互いに最も離れているように選択したいと思います。

PS。私は2つの場所をとり、それらの間の距離を与える機能を持っています。

ありがとうございます。

Answer 1

あなたは距離の節約のために別の配列は、今

$distnce_array = array(); 

のように、foreachループで、距離のために他のすべての要素を最初elemntを比較してくださいcordinatesが配列

$random_cordinates = array(); 

であるランダムに言うことができます。インデックス1で初めての値が他のすべてのインデックスと比較し、それが

$distnce_array[0] => 7; 

ようになるので、それは、第七の要素にマッチしているためと、そのインデックスなど一致指数 と第三配列$ distnce_arrayにcodinatesを保存

などもありますが、次のインデックスに移動するときは以前の座標を比較しません。インデックス5のurが0,1,2,3,4などをチェックしていない場合などです。値。 彼の意見ではなく、比較しているのは、evey loopの後ではあまりありません。

Answer 2

は、私は強くあなたの目標は

にある場合は、集合Mの中から、Nをn個の点の集合を見つけることが疑われる（| M |> = | N |）ここで、距離の 合計正しさの直感的な「証拠」は経口内部その任意のポイントである

Take the bounding-polygon of the global set of points, M 
Call the set of points that delimit this polygon P; if 
    1. |P| = |N|, then you have finished. 
     All points in P should belong to N 
    2. |P| > |N|, then you need to discard points from P. 
     For each point in P, 
      calculate its score as the delta-sum that it adds to the total. 
     Remove the lowest-scoring point until you reach |N| 
    3. |P| < |N|, then you need to add points to P. 
     For each point in M, 
      calculate its score as the delta-sum that it would add to the total. 
     Add the highest-scoring point until you reach |N| 

：最大

であるNの点の間、あなたは、この次のアルゴリズムを使用して解決することができますPによって区切られたlygonは、Pのメンバーとのデルタ距離が、Pが置換するポイントよりも短いデルタ距離を有する。 しかし、これは正式な証明ではありません。

アルゴリズムをPHPで実装するのは簡単です。 O（n）アルゴリズムを使用してfind P - in PHPも利用できます。そして、悪い場合にはポイントを追加するにはO((|N| - |P|) * |M|))が必要です（ケース3）。ポイントを破棄する必要がある場合（ケース2）はO((|P| - |N|)^2)となります。