訂購最接近指定點的點列表

Question

我想按給定點距離排列點列表。

該應用程序將查找到您當前的GPS座標最近的地標（GPS座標）。

所以如果你把下面的代碼：

public static void main(String[] args) throws SQLException { 
     ArrayList<Point2D.Double> points = new ArrayList<Point2D.Double>(); 

     Point2D.Double point1 = new Point2D.Double(1,1); 
     Point2D.Double point2 = new Point2D.Double(2,2); 
     Point2D.Double point3 = new Point2D.Double(3,3); 

     points.add(point1); 
     points.add(point2); 
     points.add(point3); 

     Point2D.Double myPoint = new Point2D.Double(4,4); 

    } 

如果我使用一個比較，以點陣列，我會獲得積分的一個很好的排序列表進行排序，但我怎麼覺得哪一個更接近myPoint？距離是多少？

這應該肯定回答我的問題，但對於獎勵積分..如果給出最大距離，我如何限制點的結果。例如：返回不超過100英里的有序座標列表。

Answer 1

首先，一些小事情：

• 你不應該申報清單作爲ArrayList，而只是作爲一個List（What does it mean to "program to an interface"?）
• 同爲兩點：他們不應該被聲明爲Point2D.Double ，但只有ALS Point2D

至於實際的問題：Point2D類已經爲（歐幾里得等）距離COMPUT方法ations。但是，對於存儲地理座標的點，您可能必須自行實施距離函數。

一般而言，由所述距離進行比較，以一個給定的點可以被實施爲在以下示例的比較：

import java.awt.geom.Point2D; 
import java.util.ArrayList; 
import java.util.Collections; 
import java.util.Comparator; 
import java.util.List; 

public class PointsByDistanceTest 
{ 
    public static void main(String[] args) 
    { 
     List<Point2D> points = new ArrayList<Point2D>(); 

     points.add(new Point2D.Double(1,1)); 
     points.add(new Point2D.Double(2,2)); 
     points.add(new Point2D.Double(3,3)); 
     points.add(new Point2D.Double(4,4)); 
     points.add(new Point2D.Double(5,5)); 
     points.add(new Point2D.Double(6,6)); 

     Point2D myPoint = new Point2D.Double(4,4); 

     Collections.sort(points, createComparator(myPoint)); 

     double maxDistance = 2.0; 
     int index = 0; 
     for (Point2D p : points) 
     { 
      if (p.distanceSq(myPoint) > maxDistance * maxDistance) 
      { 
       break; 
      } 
      index++; 
     } 
     List<Point2D> result = points.subList(0, index); 
     System.out.println(
      "The closest points with distance <="+maxDistance+" are "+result); 
    } 

    private static Comparator<Point2D> createComparator(Point2D p) 
    { 
     final Point2D finalP = new Point2D.Double(p.getX(), p.getY()); 
     return new Comparator<Point2D>() 
     { 
      @Override 
      public int compare(Point2D p0, Point2D p1) 
      { 
       double ds0 = p0.distanceSq(finalP); 
       double ds1 = p1.distanceSq(finalP); 
       return Double.compare(ds0, ds1); 
      } 

     }; 
    } 

} 

有關限制也被該樣品中的目標點的數量的問題：它將返回距離不大於maxDistance的點。不過，你仍然可以整個點的列表。如果你想避免排序整個列表，然後這變成了「K最近鄰居」的問題（http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm），在那裏你可以採用一些非常複雜的數據結構...

Answer 2

簡單math檢查它。

 int dist = Math.sqrt(Math.pow(b1.x - b2.x,2) - Math.pow(b1.y-b2.y,2)) 

編輯：在B2X

Answer 3

加點如果你有有序列表，那麼你可以通過編寫兩個列表，其中一個是X座標和一個Y座標查找最近點。然後檢查列表中的點的位置，並且具有最低索引的點是最近的點。

只是一個建議。

Answer 4

你有沒有考慮過使用這種算法 - Planar divide and conquer？

* Sort points according to their x-coordinates. 
* Split the set of points into two equal-sized subsets by a vertical line x=xmid. 
* Solve the problem recursively in the left and right subsets. This yields the 
    left-side and right-side minimum distances dLmin and dRmin, respectively. 
* Find the minimal distance dLRmin among the pair of points in which one 
    point lies on the left of the dividing vertical and the second point lies 
    to the right. 
* The final answer is the minimum among dLmin, dRmin, and dLRmin. 

您也提到使用GPS座標，如果這些被存儲爲經/緯度，也許你應該使用Haversine formula計算距離。

Answer 5

public class DistanceComparator implements Comparator<Point2D.Double>{ 

Point2D.Double refPoint; 

public DistanceComparator(Double refPoint) { 
    super(); 
    this.refPoint = refPoint; 
} 


@Override 
public int compare(Double o1, Double o2) { 
    return (refPoint.distance(o1)<refPoint.distance(o2)?-1:1); 
} 

}

Answer 6

這應該做的工作：

public static void main(final String[] args) { 
     ArrayList<Point2D.Double> points = new ArrayList<Point2D.Double>(); 

     Point2D.Double point1 = new Point2D.Double(1, 1); 
     Point2D.Double point2 = new Point2D.Double(2, 2); 
     Point2D.Double point3 = new Point2D.Double(3, 3); 

     points.add(point1); 
     points.add(point2); 
     points.add(point3); 

     final Point2D.Double myPoint = new Point2D.Double(4, 4); 

     Collections.sort(points, new Comparator<Point2D.Double>() { 

      @Override 
      public int compare(final Double o1, final Double o2) { 
       double dist1 = Math.sqrt(Math.pow(o1.x - myPoint.x, 2) - Math.pow(o1.y - myPoint.y, 2)); 
       double dist2 = Math.sqrt(Math.pow(o2.x - myPoint.x, 2) - Math.pow(o2.y - myPoint.y, 2)); 
       return Double.compare(dist1,dist2); 
      } 
     }); 
    }