Java - ポイントのセットで4つの「極端なコーナー」を見つけるための素早い方法？

Question

たとえば、x < = 10、y < = 10.ランダムな座標の集合に対して、xとyの境界（境界Aと境界Bを呼び出すことができます）が与えられているとします。4点を見つける最も速い方法（0,0）に最も近い、（A、0）、（A、B）、（0、B）？それが速ければ、ポイントは最小から最大まで順番に並べ替えることができます。これは私が現在持っているものですが、私はこのような感じを高速化することができます。

private void quadrilateral(){ 
    NW = null; 
    NE = null; 
    SE = null; 
    SW = null; 
    Point NWbound = new Point(0,B); 
    Point NEbound = new Point(A,B); 
    Point SEbound = new Point(A, 0); 
    Point SWbound = new Point(0,0); 
    for (Point p : points){ 
     if (NW == null || p.distance(NWbound) < NW.distance(NWbound)){ 
      NW = p; 
     } 
     if (NE == null || p.distance(NEbound) < NE.distance(NEbound)){ 
      NE = p; 
     } 
     if (SE == null || p.distance(SEbound) < SE.distance(SEbound)){ 
      SE = p; 
     } 
     if (SW == null || p.distance(SWbound) < SW.distance(SWbound)){ 
      SW = p; 
     } 
    } 

}

を私はまだ注文したリストを利用することができていない、と私は場合にもわからないんだけどリストを注文することはまったく役に立ちます。

Answer 1

もっと速くするには、p.distance（）の代わりにp.distanceSq（）を使用します。また、最も近い4つの距離二乗値をそれぞれ保存して、反復ごとに計算を続ける必要はありません。