最近点对算法

本文主要是介绍最近点对算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

最近点对算法

1.问题

在N个点中，寻找两个点使其距离最小。
如下为点的生成方式

2.解析

利用分治法，不断递归地将点集划分，如下x=m将图像划分为了左右两个子集。并最终求出左右两个子集的最短间距。并将该间距与分别存在于两个点子集中可能存在的比该间距更小的点对距离做比较，得解。

3.设计

最近点对算法

class Solve{

    private static double distance(Point p1, Point p2){ return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2)); }
    public static void preSort(Point[] PointArray){
        Arrays.sort(PointArray, new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return (o1.x > o2.x)?1:0;
            }
        });
    }

    static double solve(Point[] PointArray, int left, int right){
        double minDis = Double.MAX_VALUE;
        if(left == right)   return minDis;
        if(left + 1 == right)   return distance(PointArray[left], PointArray[right]);

        int middle = (left + right) / 2;
        double leftMinDis = solve(PointArray, left, middle);
        double rightMinDis = solve(PointArray, middle, right);

        minDis = Math.min(leftMinDis, rightMinDis);

        List<Integer> PINDEX = new ArrayList<>();
        for(int i = left; i <= right; i ++) if(Math.abs(PointArray[middle].x - PointArray[i].x) < minDis)   PINDEX.add(i);

        for (int i = 0; i < PINDEX.size(); i ++){
            for (int j = i  + 1; j < PINDEX.size(); j ++){
                if(Math.abs(PointArray[PINDEX.get(j)].y - PointArray[PINDEX.get(i)].y) > minDis) continue;

                double tempDis = distance(PointArray[PINDEX.get(i)], PointArray[PINDEX.get(j)]);

                minDis = Math.min(tempDis, minDis);
            }
        }

        return minDis;
    }
}

4.分析

O(n) =nlogn

5.源码

https://github.com/JessySnow/Algorithm/blob/master/src/T5/Distance.java

这篇关于最近点对算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！