Java - Быстрый способ найти четыре «экстремальных угла» в наборе точек?

Question

Предполагая, что нам присваиваются граничные значения x и y (позволяет называть границы A и B) для набора случайных координат, например x < = 10, y < = 10. Каков самый быстрый способ найти четыре точки ближайшего к (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.distanceSq() вместо p.distance(). Кроме того, сохраните каждый из четырех самых близких значений квадратов, чтобы вам не приходилось постоянно их вычислять для каждой итерации.