平面最近点对问题求解—基于Java语言

Love The Way You Lie 2022-05-14 05:25 371阅读 0赞

### 平面最近点对问题求解—基于Java语言 ###

## ##

### 1. 问题描述： ###

本问题来自《编程之美2.11—寻找最近点对》，文中给出了两种解法：暴力解法，分治解法。其中，暴力解法很简单，求出所有点之间的距离并做比较，便可找到距离最小的点对；当然，这不是最优解，时间复杂度为O(n^2)。文中还介绍了分治法，不过，没有给出源代码，网上的解法也多是基于C写的，本文将基于Java用分治法解决这个问题。

![70][]

## 2.分治法解法思想 ##

分治法思路：   
1) 把它分成两个或多个更小的问题；   
2) 分别解决每个小问题；   
3) 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。

> 这里的分治算法的主要思路是将平面上的n个点分为两个子集S1,S2。每个子集中有n/2个点，然后递归的在每个子集中求解最近点对，两边求得的结果如图所示：
> 
> ## ![这里写图片描述][20160726001541359] ##
> 
> 那么可以看出左边的最近点对的距离为**d1**,右边为**d2。**但是最近对可能一个点在S1中而另一个点在S2中。这样，我们，就要去想办法对其进行合并,然后求得合并区域的最近对距离，假设为**d3**，那么只需要比较**d1,d2,d3**的大小关系即可，最小的就是平面最近对的距离。通过分析我们可以知道，如果存在这样的最近对的点，那么这个点在S1集合中，肯定是横坐标最靠近中位线 ***L*** 的点，S2中同理。那么这个范围如何划定呢？
> 
> --------------------
> 
> 设***d=min(d1,d2)***假定中位线横坐标为**X**，那么范围就是***\[X-d,X+d\]***.这个范围是怎么划定的呢？根据平面中点的位置我们就可以知道，两点的距离为横纵坐标之间的差值的平方和。那么如果要存在这样的点，他们之间的横坐标之间的差值的绝对值必须要小于等于**d**（这里包括这点恰好就在中位线 ***L*** 上）。这样可以筛选出横坐标为***\[X-d,X+d\]***的区域。如下图所示：
> 
> --------------------
> 
> ![这里写图片描述][20160726012613123]
> 
> 可以看出这个区域中包含三个点，只需要求出这三个点之间的最近点对即可（蛮力法）。这里还需要注意一点，上面是通过横坐标筛选的这个区域，这里可以根据纵坐标将纵坐标差的绝对值大于 **d** 的坐标剔除。

### 3. 基于分治法的解法代码 ###

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Comparator;
    import java.util.List;
    
    public class MinDis
    {
    
        public static void main(String[] args)
        {
            // 测试用例
            Point[] points = new Point[7];
    
            points[0] = new Point(1, 1);
            points[1] = new Point(1, 9);
            points[2] = new Point(2, 5);
            points[3] = new Point(3, 1);
            points[4] = new Point(4, 4);
            points[5] = new Point(5, 8);
            points[6] = new Point(6, 2);
    
            // 预处理，基于x轴坐标排序，便于分治法实施
            Arrays.sort(points, new Comparator<Point>()
            {
                @Override
                public int compare(Point p1, Point p2)
                {
                    return (p1.x > p2.x) ? 1 : (p1.x == p2.x) ? 0 : -1;
                }
    
            });
            // 测试
            System.out.println(divide(0, points.length-1, points));
        }
        
        /**
         * 求平面上距离最近的两个点
         * 
         */
        public static double divide(int left, int right, Point[] points)
        {
            // 当前最小两点距离，初始值设置为无穷大
            double curMinDis = 1e20;
            // 如果只有一个点，则不存在最近两点距离，返回无穷大
            if (left == right)
            {
                return curMinDis;
            }
            // 这里是判断是否为只有两个点，如果只有两个点的话那么直接求解。
            if (left + 1 == right)
            {
                return distance(points[left], points[right]);
            }
    
            // 分治法：第一步：分区，并求取左右分区最小两点距离
            // 通过右移运算除2，对区域进行合理的划分，使得左右两边保持大致相等个数点
            int middle = (left + right) >> 1;
            double leftMinDis = divide(left, middle, points);
            double rightMinDis = divide(middle, right, points);
    
            curMinDis = (leftMinDis <= rightMinDis) ? leftMinDis : rightMinDis;
    
            // 分治法：第二步：假设距离最近的两点分别在左右分区中
            // 关键代码，距离最近的两个点，一个位于左边区域，一个位于右边区域，x轴搜索范围[middle-curMinDis, middle+curMinDis]
            // 记录搜索区间内的点的索引，便于进一步计算最小距离
            List<Integer> validPointIndex = new ArrayList<>();
            for (int i = left; i <= right; i++)
            {
                if (Math.abs(points[middle].x - points[i].x) <= curMinDis)
                {
                    validPointIndex.add(i);
                }
            }
            // 基于索引，进一步计算区间内最小两点距离
            for (int i = 0; i < validPointIndex.size() - 1; i++)
            {
                for (int j = i + 1; j < validPointIndex.size(); j++)
                {
                    // 如果区间内的两点y轴距离大于curMinDis，则没必要计算了，因为，它们的距离肯定大于curMinDis，
                    if (Math.abs(points[validPointIndex.get(i)].y
                            - points[validPointIndex.get(j)].y) > curMinDis)
                    {
                        continue;
                    }
                    double tempDis = distance(points[validPointIndex.get(i)],
                            points[validPointIndex.get(j)]);
    
                    curMinDis = (tempDis < curMinDis) ? tempDis : curMinDis;
                }
            }
    
            return curMinDis;
        }
    
        /**
         * 计算两点间的距离
         */
        public static double distance(Point p1, Point p2)
        {
            return Math.sqrt((p2.y - p1.y) * (p2.y - p1.y) + (p2.x - p1.x) * (p2.x - p1.x));
        }
    }
    /**
     * 定义点
     * 
     */
    class Point
    {
        public int x;
        public int y;
    
        Point(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }

### 特别说明： ###

本文部分内容摘录自博客：[https://blog.csdn.net/Up\_junior/article/details/52019943][https_blog.csdn.net_Up_junior_article_details_52019943]

[70]: /images/20220514/7b52c5c26fe84aa0b295b5ddfd39a8f4.png
[20160726001541359]: /images/20220514/e45ad3154b2849df9ebccc4e8e4c7ee1.png
[20160726012613123]: /images/20220514/99e3af1a9ff2435ea62df8bea64b47d0.png
[https_blog.csdn.net_Up_junior_article_details_52019943]: https://blog.csdn.net/Up_junior/article/details/52019943