订购最接近给定点的点列表

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

首先，一些小事情：

• 您不应将列表声明为 a ArrayList，而只能声明为 a List（“编程到接口”是什么意思？）
• 对于点也是如此：它们不应该声明为Point2D.Double，而只能声明为 alsPoint2D

关于实际问题：该类Point2D已经具有用于（欧几里德和其他）距离计算的方法。但是，对于存储地理坐标的点，您可能必须自己实现距离函数。

一般来说，通过到给定点的距离进行比较的比较器可以如下例所示实现：

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），您可以在其中使用一些非常复杂的数据结构......