/*
问题1：如何解决 cannot be cast to java.lang.Comparable问题？
产生原因：TreeSet的特点是可排序、不重复，即TreeSet要求存放的对象必须是可排序的。如果对象之间不可排序，就会抛出这个异常。
解决：实现Comparable接口
问题2：Java ArrayList toArray() 方法
解决：https://www.runoob.com/java/java-arraylist-toarray.html
问题3：TreeSet有重复元？
解决：注意比较器comareTo的写法
问题4：堆栈溢出java.lang.StackOverflowError(当点的数量很多，但集中在一块区域的时候)
解决：因为解决了问题3这个问题也解决了
*/
import java.util.ArrayList;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
/*
* 建立自己的类Point,建立在主函数外面
*/
class Point implements Comparable<Point>{
private int x;
private int y;
public Point() {
x=0;
y=0;
}
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
//问题1的解决：
public int compareTo(Point o) {
//x是比较的主要条件，y是比较的次要条件
return this.x-o.getX()== 0 ? this.y-o.getY():this.x-o.getX();
}
}
public class 最近点对 {
public static void main(String[] args) {
Set<Point> testData=new TreeSet<Point>();
Random random=new Random();
int x=0;
int y=0;
for (int i = 0; i < 10000; i++) {
//()里面是返回的随机数的界限，必须是正数
//返回一个伪随机、均匀分布的int值，介于0（包括）和n（不包括）之间
x=random.nextInt(10000);
y=random.nextInt(10000);
System.out.println("x:"+x+" y:"+y);
testData.add(new Point(x,y));
}
Point[] S=new Point[testData.size()];
S=(Point[])testData.toArray(S);
for (int i = 0; i < S.length; i++) {
System.out.println("("+S[i].getX()+","+S[i].getY()+")");
}
System.out.println(testData.size());
//mergeSort(S,"x"); treeSet生成的结果本身就是有序的
Point[] ans=new Point[2];
ans=closestPoint(S);
System.out.println("最近的两点分别为是("+ans[0].getX()+","+ans[0].getY()+")和("
+ans[1].getX()+","+ans[1].getY()+")，最近距离为："+
Math.sqrt(Math.pow(ans[0].getX()-ans[1].getX(), 2)+
Math.pow(ans[0].getY()-ans[1].getY(), 2)));
}
private static Point[] closestPoint(Point[] S) {
// TODO Auto-generated method stub
Point[] res=new Point[2];
/**
* 0.首先，解决该问题的边界，当数组长度在一定范围内时直接求出最近点，蛮力求解
*/
double dmin=Double.POSITIVE_INFINITY;//正无穷
double tmpmin=0;
if(S.length<=20) {
for (int i = 0; i < S.length; i++) {
for (int j = i+1; j < S.length; j++) {
tmpmin=Math.sqrt(Math.pow(S[i].getX()-S[j].getX(), 2)+Math.pow(S[i].getY()-S[j].getY(), 2));
if(tmpmin<dmin) {
dmin=tmpmin;
res[0]=S[i];
res[1]=S[j];
}
}
}
return res;
}
/**
* 1.求所有点在X坐标中的中位数
*/
// int minX=(int)Double.POSITIVE_INFINITY;//保证假设的初始最小值
// int maxX=(int)Double.NEGATIVE_INFINITY;//保证假设的初始最大值
// for(int i=0;i<S.length;i++) {
// if(S[i].getX()<minX)
// minX=S[i].getX();
// if(S[i].getX()>maxX)
// maxX=S[i].getX();
// }
int midX=(S[0].getX()+S[S.length-1].getX())/2;
/**
* 2.以midX为界将所有点分成两组分别存放在两个表中
*/
ArrayList T1=new ArrayList();
ArrayList T2=new ArrayList();
for (int i = 0; i < S.length; i++) {
if(S[i].getX()<=midX) //是否要=号？
T1.add(S[i]);
if(S[i].getX()>midX)
T2.add(S[i]);
}
/**
* 3.将两张表转化为数组类型，并分别按X坐标升序排序
*/
Point[] S1=new Point[T1.size()];
Point[] S2=new Point[T2.size()];
T1.toArray(S1);
T2.toArray(S2);
//mergeSort(S1,"x");//按X坐标升序排列
//mergeSort(S2,"x");//按X坐标升序排列
/**
* 4.求S1中的最近距离的两个点
*/
Point[] res1=new Point[2];
res1=closestPoint(S1);
/**
* 5.求S2中的最近距离的两个点
*/
Point[] res2=new Point[2];
res2=closestPoint(S2);
/**
* 6.求两个最近距离的最小值
*/
double d1=Math.sqrt(Math.min(Math.pow(res1[0].getX()-res1[1].getX(), 2)+Math.pow(res1[0].getY()-res1[1].getY(), 2),
Math.pow(res2[0].getX()-res2[1].getX(), 2)+Math.pow(res2[0].getY()-res2[1].getY(), 2)));
if(Math.pow(res1[0].getX()-res1[1].getX(), 2)+Math.pow(res1[0].getY()-res1[1].getY(), 2)<
Math.pow(res2[0].getX()-res2[1].getX(), 2)+Math.pow(res2[0].getY()-res2[1].getY(), 2))
res=res1;
else
res=res2;
/**
* 7.在S1、S2中收集距离中线小于d1的点，分别存放在两个表中
*/
ArrayList T3=new ArrayList();
//ArrayList T4=new ArrayList();
for (int i = 0; i < S1.length; i++) {
if(midX-S1[i].getX()<d1)
T3.add(S1[i]);
}
for (int i = 0; i < S2.length; i++) {
if(S2[i].getX()-midX<d1)
//T4.add(S2[i]);
T3.add(S2[i]);
}
/**
* 8.分别将表T3、T4转化为数组类型的S3、S4，并将其分别按Y坐标升序排列
*/
Point[] S3=new Point[T3.size()];
//Point[] S4=new Point[T4.size()];
T3.toArray(S3);
//T4.toArray(S4);
mergeSort(S3,"y");
//mergeSort(S4,"y");
/**
* 求解S3、S4两者之间可能的更近（相比于d1）距离，以及构成该距离的点
*/
double tmp=Double.POSITIVE_INFINITY;
for (int i = 0; i < S3.length; i++) {
for (int j = i+1; j < S3.length; j++) {
if(S3[j].getY()-S3[j].getY()>d1)
continue;
else {
tmp=Math.sqrt(Math.pow(S3[i].getX()-S3[j].getX(),2)+Math.pow(S3[i].getY()-S3[j].getY(),2));
if(tmp<d1) {
res[0]=S3[i];
res[1]=S3[j];
d1=tmp;
}
}
}
}
// double d=Double.POSITIVE_INFINITY;
// for (int i = 0; i < S3.length; i++) {
// for (int j = 0; j < S4.length; j++) {
// if(Math.abs(S3[i].getY()-S[4].getY())<d1) {
// double tmp=Math.sqrt(Math.pow(S3[i].getX()-S4[j].getX(),2)+Math.pow(S3[i].getY()-S4[j].getY(),2));
// if(tmp<d) {
// d=tmp;
// res[0]=S3[i];
// res[1]=S4[j];
// }
// }
// }
// }
return res;
}
private static void mergeSort(Point[] a, String s) {
// TODO Auto-generated method stub
Point[] tmpArray=new Point[a.length];
mergeSort(a,tmpArray,0,a.length-1,s);
}
private static void mergeSort(Point[] a, Point[] tmpArray, int left, int right, String s) {
// TODO Auto-generated method stub
if(left<right) {
int mid=left+((right-left)>>1);
//分治
mergeSort(a,tmpArray,left,mid,s);
mergeSort(a,tmpArray,mid+1,right,s);
//合并
merge(a,tmpArray,left,mid,right,s);
}
}
private static void merge(Point[] a, Point[] tmpArray, int left, int mid, int right, String s) {
// TODO Auto-generated method stub
System.arraycopy(a, left, tmpArray, left, right-left+1);
int l=left,r=mid+1;
int current=left;
while(l<=mid&&r<=right) {
if(s.equals("x")) {
if(tmpArray[l].getX()<=tmpArray[r].getX()) {
a[current++]=tmpArray[l++];
}else {
a[current++]=tmpArray[r++];
}
}else if(s.equals("y")) {
if(tmpArray[l].getY()<=tmpArray[r].getY()) {
a[current++]=tmpArray[l++];
}else {
a[current++]=tmpArray[r++];
}
}else {
throw new RuntimeException();
}
}
while(l<=mid) {
a[current++]=tmpArray[l++];
}
}
}注：本篇博客做了部分修改和优化
源码参考：(8条消息) 分治法-最近距离问题Java实现_过顶擒龙的博客-CSDN博客
标签：Java,Point,int,分治,getX,getY,new,Math,法求 From： https://blog.51cto.com/u_15470952/6188278