如果觉得再简述上阅读代码太困难可以点这里：最近点对问题
最近点对问题，即平面上有n个点P1,P2,...,Pn，n>1,Pi的直角坐标为(Xi,Yi),i=1,2,...,n.求距离最近的两个点及他们之间的距离。
对于这个问题，我们如果使用暴力求解的方法的话，n个点之间存在(n-1)*n/2个点对，将全部点对之间的距离计算出来并得到最短的距离，这个暴力算法将花费O(n^2)的时间，这个时间复杂度显然是不能让人接受的，接下来，我们使用分支的思想来解决这个问题。
直接来推导平面中的最近点对是有点困难的，我们不妨先考虑一下直线的情况：即求出直线上的最近点对
如上图所示：为了求出一条直线中距离最近的两个点，通过分治的思想，先将点根据大小进行排序，接下来我们可以在通过中点将直线划分为两部分,获得到S1区域的最小距离为d1,S2区域的最小距离为d2，d1,d2的计算我们可以通过递归实现,接下来考虑第三种情况:一个点在S1区域，一个点在S2区域，因为所有的点都在一条线段上，所以我们只要计算p3q3的距离d3,接下来就是获得最小值min=min{d1,d2,d3}。这样看来的话，对于一维情况下的最近点对，我们的时间复杂度为Olog(n)。
接下来，我们就继续来看看二维中如何求得最近点对，对比一维，我们需要解决一下两个难点：
一，如何将平面进行划分，使得我们可以用分治的思想去解决问题？
二，如果划分好了S1,S2两部分区域后，如何解决一个点在S1,一个点在S2中的第三种情况呢？
关于第一个问题，如下图所示，我们可以在平面中间通过一条线段LS将平面划分为两个区域：
二维情况下
我们先将平面中的点根据X轴进行排序，然后通过X轴的中点值进行划分，接下来递归到下一层，直到划分的区域中不能在划分为止
//这个就是递归终止条件：当区域中只剩下两个点甚至更少时，我们就计算出两个点之间的距离
if(head+1>=tail) {
if(head==tail) { //当区域为一个点时，这个时候将距离设为Double类型的最大值
return Double.MAX_VALUE;
}
return CalculateUtil.getDistance(data[head].getX(), data[head].getY(),
data[tail].getX(), data[tail].getY());
}
这样的话，我们就能获得到S1区域最小值d1,S2区域最小值d2
接下来我们就要考虑第三种情况了：当一个点存在S1区域，一个点存在S2区域时，我们怎么去获得d3呢，这个时候我们就需要了进行一个更细致地处理了：
在书籍《算法设计与分析》的分支策略中，关于最近点对问题，对上图有以下描述：(加上了一些本人的见解)
在P1区域任选一点坐标为(xi,yi)，在右边窄缝内距Pi小于min(d1,d2) 其纵坐标一定在yi-min(d1,d2),yi+min(d1,d2)之间，话句话说，这些点只能在图片中的矩形区域中。书中又给了这样一个结论，对于每个点而言，检查另一边是否有点与他的距离小于min(d1,d2),只要考虑常数个数，这个常数不大于6,想要深入了解这个结论的由来的朋友可以了解一下（鸽巢原理）
解决了这两个问题，接下来就是代码实现了，想要真正学会一个东西，就是去教会一个人，对于计算机领域而言，我们就是要去教会计算机如何去解决这个问题。
接下来是我自己实现的一份代码：(代码比较粗糙，在之后还会提供一份《Java语言程序设计（进阶篇）》第十版的最近点对问题解决代码)
首先是我的数据结构:Coordinates.java
/**
* 坐标系
*
*/
public class Coordinates implements Comparable<Coordinates>{
private Double x;
private Double y;
public Double getX() {
return x;
}
public void setX(Double x) {
this.x = x;
}
public Double getY() {
return y;
}
public void setY(Double y) {
this.y = y;
}
public Coordinates(Double x, Double y) {
super();
this.x = x;
this.y = y;
}
public Coordinates() {
super();
}
@Override
public String toString() {
return "Coordinates [x=" + x + ", y=" + y + "]";
}
//通过重写该方法，可以通过Arrays.sort()通过对x值对本对象进行排序
public int compareTo(Coordinates o) {
return new Integer(this.getX().compareTo(o.getX()));
}
}
我的生成数据工具类:IOOpera.java
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;
/**
* 生成用于测试的数据
*
*/
public class IOOpera {
private final static File DATA= new File("data.txt");
/**
* 随机生成区间(a,b)中num个数据，并将数据写入到data.txt文件中
* @param a
* @param b
* @param num
* @throws IOException
*/
public static void writeToFile(int a,int b,int num) throws IOException {
PrintWriter out=null;
try {
out=new PrintWriter(DATA);
//随机生成num个在(a,b)区间内的值
for(int i=0;i<num;i++) {
out.print((b-a)*Math.random()+a); //输入x
out.println(" "+Math.random()*200); //输入y
}
} catch (FileNotFoundException e) {
System.out.println("找不到文件!");
e.printStackTrace();
}finally {
if(null!=out) {
out.close();
}
}
}
public static ArrayList<Coordinates> readFromFile() {
Scanner in=null;
ArrayList<Coordinates> coordinatesList=new ArrayList<Coordinates>();
try {
in=new Scanner(DATA);
while (in.hasNext()) {
// System.out.println("(X:"+in.nextDouble()+",Y:"+in.nextDouble()+")");
coordinatesList.add(new Coordinates(in.nextDouble(),in.nextDouble()));
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}finally {
if(null!=in) {
in.close();
}
}
return coordinatesList;
}
public static void main(String[] args) throws IOException {
IOOpera.writeToFile(1, 1000, 200000);
ArrayList<Coordinates> list = IOOpera.readFromFile();
for (Coordinates coordinates : list) {
System.out.println(CalculateUtil.mult(coordinates.getX(), coordinates.getY()));
}
}
}
我的计算类:CalculateUtil.java
/**
*
* 计算工具类
*
*/
public class CalculateUtil {
//两数字想乘
public static double mult(double a,double b) {
return a*b;
}
//获得两点之间的距离
public static double getDistance(double x1,double y1,double x2,double y2) {
double distance=0;
distance=Math.sqrt(mult((x2-x1), (x2-x1))+mult((y2-y1), (y2-y1)));
return distance;
}
public static void main(String[] args) {
//测试
System.out.println(CalculateUtil.getDistance(3.7237733214685664, 21.833916865708613, 3.7384663016056487, 158.16628876345715));
}
}
重中之重——我的算法类：ClosestPair .java
import java.util.ArrayList;
import java.util.Arrays;
public class ClosestPair {
private static int[] temp; //通过y值进行排序时使用
//分治算法
public static double getMin() {
double min=Double.MAX_VALUE;
ArrayList<Coordinates> list = IOOpera.readFromFile();
//将ArrayList转换为[]
Coordinates[] data=new Coordinates[list.size()];
data=list.toArray(data);
temp=new int[data.length];
Arrays.sort(data); //对数组进行排序
min=getMinStance(0, data.length-1, data);
return min;
}
public static double getMinStance(int head,int tail,Coordinates[] data) {
double min=Double.MAX_VALUE;
if(head+1>=tail) {
if(head==tail) {
return Double.MAX_VALUE;
}
return CalculateUtil.getDistance(data[head].getX(), data[head].getY(), data[tail].getX(), data[tail].getY());
}
int mid=(head+tail)/2; //中点坐标
double leftMin=getMinStance(head,mid,data);
double rightMin=getMinStance(mid+1,tail,data);
double d=leftMin<rightMin?leftMin:rightMin; //d
int k=0;
//分离出宽度为d的区间
for(int i=head;i<tail;i++) {
if(Math.abs(data[mid].getX()-data[i].getX())<=d) {
temp[k++]=i;
}
}
/**将temp区域内的值根据y值进行排序
* 之所以在这个地方要根据y进行排序的原因是:
* 在接下来的嵌套for循环能够正常执行的前提就是y是排好序的
*/
sortTemp(data);
for(int i=0;i<k;i++) {
for(int j=i+1;j<k&&Math.abs(data[temp[j]].getY()-data[temp[i]].getY())<d;j++) {
double d3=CalculateUtil.getDistance(data[temp[i]].getX(), data[temp[i]].getY(),data[temp[j]].getX(), data[temp[j]].getY());
if(d3<d) {
d=d3;
// System.out.println("P1点坐标("+data[temp[i]].getX()+ ","+data[temp[i]].getY()+") P2点坐标("+ data[temp[j]].getX()+","+data[temp[j]].getY()+")");
}
}
}
return d;
}
public static void sortTemp(Coordinates[] data) {
int k=0;
//一个冒泡排序 这部分可以改进 希望朋友可以实现一下
while(true) {
if(k>=temp.length) {
break;
}
int j=0;
Coordinates tem=null;
while(j<k) {
if(data[temp[j]].getY()>data[temp[j+1]].getY()) {
tem=data[temp[j]];
data[temp[j]]=data[temp[j+1]];
data[temp[j+1]]=tem;
}
j++;
}
k++;
}
}
public static void main(String[] args) {
System.out.println(getMin());
}
}
上述就是我所有解决问题的类，对于上述的类，有以下几点不足之处，
1.关于数据结构类没有设计好，使得在之后的数据处理中非常棘手
2.通过y值进行排序的算法本人使用了时间复杂度为O(n^2)的冒泡算法，这个是需要改进的
接下来载提供一份《Java语言程序设计（进阶篇）》第十版的最近点对问题解决代码：
import java.util.Arrays;
/** This program works, but the design is not good. Redesign it */
public class ClosestPair {
// Each row in points represents a point
private double[][] points;
Point p1, p2;
public static void main(String[] args) {
double[][] points = new double[500][2];
for (int i = 0; i < points.length; i++) {
points[i][0] = Math.random() * 100;
points[i][1] = Math.random() * 100;
}
ClosestPair closestPair = new ClosestPair(points);
System.out.println("shortest distance is " +
closestPair.getMinimumDistance());
System.out.print("(" + closestPair.p1.x + ", " +
closestPair.p1.y + ") to ");
System.out.println("(" + closestPair.p2.x + ", " +
closestPair.p2.y + ")");
}
ClosestPair() {
}
public ClosestPair(double[][] points) {
setPoints(points);
}
public void setPoints(double[][] points) {
this.points = points;
}
public double getMinimumDistance() {
Point[] pointsOrderedOnX = new Point[points.length];
for (int i = 0; i < pointsOrderedOnX.length; i++)
pointsOrderedOnX[i] = new Point(points[i][0], points[i][1]);
Arrays.sort(pointsOrderedOnX);
// Locate the identical points if exists
if (checkIdentical(pointsOrderedOnX))
return 0; // The distance between the identical points is 0
Point[] pointsOrderedOnY = pointsOrderedOnX.clone();
Arrays.sort(pointsOrderedOnY, new CompareY());
return distance(pointsOrderedOnX, 0,
pointsOrderedOnX.length - 1, pointsOrderedOnY);
}
/** Locate the identical points if exist */
public boolean checkIdentical(Point[] pointsOrderedOnX) {
for (int i = 0; i < pointsOrderedOnX.length - 1; i++) {
if (pointsOrderedOnX[i].compareTo(pointsOrderedOnX[i + 1]) == 0) {
p1 = pointsOrderedOnX[i];
p2 = pointsOrderedOnX[i + 1];
return true;
}
}
return false;
}
/** Return the distance of the closest pair of points in
* pointsOrderedOnY.
* pointsOrderedOnX[low..high] and pointsOrderedOnY contain the
* same points. */
public double distance(
Point[] pointsOrderedOnX, int low, int high,
Point[] pointsOrderedOnY) {
if (low >= high) // Zero or one point in the set
return Double.MAX_VALUE;
else if (low + 1 == high) {
// Two points in the set
p1 = pointsOrderedOnX[low];
p2 = pointsOrderedOnX[high];
return distance(pointsOrderedOnX[low], pointsOrderedOnX[high]);
}
// Divide the points into two sets in pointsOrderedOnX.
// Store the points p into pointsOrderedOnYL if
// p.x <= pointsOrderedOnX[mid]. Otherwise, store it into
// pointsOrderedOnYR. The points in pointsOrderedOnYL and
// pointsOrderedOnYL are ordered on their y-coordinates
int mid = (low + high) / 2;
Point[] pointsOrderedOnYL = new Point[mid - low + 1];
Point[] pointsOrderedOnYR = new Point[high - mid];
int j1 = 0; int j2 = 0;
for (int i = 0; i < pointsOrderedOnY.length; i++) {
if (pointsOrderedOnY[i].compareTo(pointsOrderedOnX[mid]) <= 0)
pointsOrderedOnYL[j1++] = pointsOrderedOnY[i];
else
pointsOrderedOnYR[j2++] = pointsOrderedOnY[i];
}
// Recursively find the distance of the closest pair in the left
// half and the right half
double d1 = distance(
pointsOrderedOnX, low, mid, pointsOrderedOnYL);
double d2 = distance(
pointsOrderedOnX, mid + 1, high, pointsOrderedOnYR);
double d = Math.min(d1, d2);
// stripL: the points in pointsOrderedOnYL within the strip d
int count = 0;
for (int i = 0; i < pointsOrderedOnYL.length; i++)
if (pointsOrderedOnYL[i].x >= pointsOrderedOnX[mid].x - d)
count++;
Point[] stripL = new Point[count];
count = 0;
for (int i = 0; i < pointsOrderedOnYL.length; i++)
if (pointsOrderedOnYL[i].x >= pointsOrderedOnX[mid].x - d)
stripL[count++] = pointsOrderedOnYL[i];
// stripR: the points in pointsOrderedOnYR within the strip d
count = 0;
for (int i = 0; i < pointsOrderedOnYR.length; i++)
if (pointsOrderedOnYR[i].x <= pointsOrderedOnX[mid].x + d)
count++;
Point[] stripR = new Point[count];
count = 0;
for (int i = 0; i < pointsOrderedOnYR.length; i++)
if (pointsOrderedOnYR[i].x <= pointsOrderedOnX[mid].x + d)
stripR[count++] = pointsOrderedOnYR[i];
// Find the closest pair for a point in stripL and
// a point in stripR
double d3 = d;
int j = 0;
for (int i = 0; i < stripL.length; i++) {
while (j < stripR.length && stripL[i].y > stripR[j].y + d)
j++;
// Compare a point in stripL with six points in stripR
int k = j; // Start from r1 up in stripR
while (k < stripR.length && stripR[k].y <= stripL[i].y + d) {
if (d3 > distance(stripL[i], stripR[k])) {
d3 = distance(stripL[i], stripR[k]);
p1 = stripL[i];
p2 = stripR[k];
}
k++;
}
}
return Math.min(d, d3);
}
/** Compute the distance between two points p1 and p2 */
public static double distance(Point p1, Point p2) {
return distance(p1.x, p1.y, p2.x, p2.y);
}
/** Compute the distance between two points (x1, y1) and (x2, y2) */
public static double distance(
double x1, double y1, double x2, double y2) {
return Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
/** Define a class for a point with x- and y- coordinates */
static class Point implements Comparable<Point> {
double x;
double y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
public int compareTo(Point p2) {
if (this.x < p2.x)
return -1;
else if (this.x == p2.x) {
// Secondary order on y-coordinates
if (this.y < p2.y)
return -1;
else if (this.y == p2.y)
return 0;
else
return 1;
}
else
return 1;
}
}
/** A comparator for comparing points on their y-coordinates.
* If y-coordinates are the same, compare their x-coordinator. */
static class CompareY implements java.util.Comparator<Point> {
public int compare(Point p1, Point p2) {
if (p1.y < p2.y)
return -1;
else if (p1.y == p2.y) {
// Secondary order on x-coordinates
if (p1.x < p2.x)
return -1;
else if (p1.x == p2.x)
return 0;
else
return 1;
}
else
return 1;
}
}
}
