最近点对问题算法

A. C语言课设，最近点对问题，求大神用分治法做出来，图片是具体要求，谢谢😜

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>

typedefstruct
{
doublex;
doubley;
}Building;

//创建所有建筑的坐标
Building*creatCoordinate(intiBuilNum)
{
inti,j;
doublex,y;
srand((int)time(NULL));
Building*bBuil=(Building*)malloc(sizeof(Building)*iBuilNum);
for(i=0;i<iBuilNum;i++)
{
x=(rand()%10000)*0.01;
y=(rand()%10000)*0.01;
for(j=0;j<i;j++)
{
if(x==bBuil[j].x&&y==bBuil[j].y)
{
i--;
continue;
}
}
bBuil[i].x=x;
bBuil[i].y=y;
}

returnbBuil;
}

//求两点间的距离
doublegetDis(BuildingbA,BuildingbB)
{
doubledDifferenceX=bA.x-bB.x;
doubledDifferenceY=bA.y-bB.y;
returnsqrt(dDifferenceX*dDifferenceX+dDifferenceY*dDifferenceY);
}

//求所有点间的距离
double*getAllDis(Building*abCoordinate,intiBuilNum,intiDisNum,int*aiMinIndex)
{
inti,j,k;
doubledMin=1000.0;
double*adDis=(double*)malloc(sizeof(double)*iDisNum);
for(i=iBuilNum-1,k=0;i>0;i--)
{
for(j=i;j>0;j--)
{
//printf("%d%d
",iBuilNum-i-1,iBuilNum-j);
adDis[k]=getDis(abCoordinate[iBuilNum-i-1],abCoordinate[iBuilNum-j]);
//截取最小距离
if(adDis[k]<dMin)
{
dMin=adDis[k];
//截取最小距离相应坐标数组的下标
aiMinIndex[0]=iBuilNum-i-1;
aiMinIndex[1]=iBuilNum-j;
}
k++;
}
}

returnadDis;
}

intmain(void)
{
intiBuilNum,iDisNum=0,aiMinIndex[2],i;
printf("%s
","请输入建筑物数量：");
scanf("%d",&iBuilNum);
for(i=1;i<iBuilNum;i++)
iDisNum+=i;

Building*abCoordinate=creatCoordinate(iBuilNum);
double*adDis=getAllDis(abCoordinate,iBuilNum,iDisNum,aiMinIndex);

//输出所有坐标
printf("%s
","所有建筑物的坐标为：");
for(i=0;i<iBuilNum;i++)
printf("x:%0.2lfy:%0.2lf
",abCoordinate[i].x,abCoordinate[i].y);

//输出距离最近两个点的坐标
printf("%s
","距离最近两个建筑物的坐标为：");
printf("x:%0.2lfy:%0.2lf
",abCoordinate[aiMinIndex[0]].x,abCoordinate[aiMinIndex[0]].y);
printf("x:%0.2lfy:%0.2lf
",abCoordinate[aiMinIndex[1]].x,abCoordinate[aiMinIndex[1]].y);

//输出距离最近两个点的距离
printf("%s
","距离最近两个建筑物的距离为：");
printf("%0.2lf
",getDis(abCoordinate[aiMinIndex[0]],abCoordinate[aiMinIndex[1]]));

//输出所有距离
//printf("%s
","所有建筑物的距离为：");
//for(i=0;i<iDisNum;i++)
//printf("%0.2lf
",adDis[i]);

free(abCoordinate);
free(adDis);

return0;
}

B. 最近点对问题

#include<stdio.h>
#include<math.h>
void main()
{
int n,i,j,k=0;
float a[5000],b[5000],c[5000],min;
printf("请输入点的数目：");
scanf("%d",&n);
printf("请输入点的坐标：");
for(i=0;i<n;i++)
scanf("%f%f",&a[i],&b[i]);
min=(a[0]-a[1])*(a[0]-a[1])+(b[0]-b[1])*(b[0]-b[1]);
for(j=0;j<n-1;j++)
for(i=j+1;i<n;i++)
{
c[k]=(a[j]-a[i])*(a[j]-a[i])+(b[j]-b[i])*(b[j]-b[i]);
c[k]=sqrt(c[k]);
if(c[k]<min)
{min=c[k];}
k++;
}
min=(int)(min*100)+0.5;
min=min/100;//四舍五入
printf("%.2f\n",min);
}

C. python如何在众多的点中找到与特定点最近的点的算法

首先目测一下查询大概不止一次所以前面那些统统乘个Q就大爆炸吧。
平民的做法写个kdtree基本sqrt n复杂度对付10w的数据量应该轻松愉快，动态的话套个替罪羊。
泥垢无聊的话动态v图欢迎入坑 传闻是logn的我没写过不知道会不会比上面的慢。
啊找到了我记得这个大轮子应该可以很简单（不如手写）的解决你的问题
PCL - Point Cloud Library (PCL)
-

单纯的替罪羊套kdt放到这种场合可能不大合适……毕竟修改一次可能锁死整个子树……（当然可以不用替罪羊，缓存sqrt n个修改，然后每sqrt n个修改暴力重构整个树，重构完成之前就先用原来的，然后再加上各种奇怪的优化……。）
然后再YY一下，我个人觉得他们可能是这样干的，首先把地图切成一块一块的每块足够小。然后随便YY一下按照每个地方人数的多少，取一个合适的am^2范围内最多有x人，然后只要这个x够小，查询的时候只查询当前用户所在的区块和周围的几个区块就好了，然后你就可以用轮子哥那样的sql查询啦～
如果还是有问题要么加服务器，或者最不济还可以对这个区块再维护kdtree。而且这样修改起来还方便。
至于用户周围都没有人，最近的有人区块在几十公里外…

D. 高分求算法：寻找与特定对象距离最近的对象

用现在的ID,X,Y三个元素来找最近点的话无论什么办法,都至少要与每个点进行一次距离的判断,比较X或者Y也好,计算距离(当然这个距离是不用开平方的,与其他所有点的距离都不开平方也能比较相对的距离长短)也好,所以如果只有这三个元素的话,其实再怎么改也不会有太大的优化的。

最好还是添加一些辅助信息，比较常用的就是以划分网格的方法，将所有点分派在不同的网格中，然后以网格为基础找最近点，这样的话就要加一个网格的结构（以空间换时间），里面存放的就是属于这个网格的点的ID，通过编号规则可以很快的找最近的网格，然后再找里面的点，这样可以提高点查找速度。

呵呵,不好意思,没想清楚就写了:P,改一下,改一下,再加一步就好了

1.给点添加一个所属网格的信息:
Class A
{
public int ID;
public int X;
public int Y;
publci int Index;//所属网格编号
}
2.构造一个点链表,这是为了减少空间和方便处理而加的,后面的算法里会感觉到用处
(为每个点对象建立一个点链表节点)
Class I
{
public A *pAObject; //指向一个点对象
publci I *pNextA; //指向下一个
}
3.构件一个网格信息结构
Class G
{
public int ID; //网格编号
public I *pAObjects; //指向一个点链表(至于这个是带头节点还是不带头节点的都一样啦)
//这里用链表比较好
//第一,因为点可移动,那么点对象个数可以随意,可以发挥链表的扩展性
//第二,不需要取中间节点,也就没有用到数组的长处
}
4.构建网格,比如以1000为长度(长度可以自己定义,关键是平衡空间和速度关系),建立正方形的网格,那么(0,0)到(1000000,1000000)就是有1000*1000个网格(在给网格编号的时候最好有规律,那么就能通过List或者其他数组容器的下标来获得网格信息)
5.添加点的时候,先判断属于哪个网格,然后在点信息中添加网格编号,同时构建对应的点链表节点,并添加到所属网格的链表中
6.最后就是查询点了,首先获得出发点中的所属网格信息,看这个网格中是否有其他点:有,则一个个的判断距离(距离的平方),那么最近点一定在这些点里面(如果点还是太多,那么就考虑缩小网格的范围);没有,那就找所属网格周边8个网格中是否有点,有,则再找最近点,没有就再往外扩(如果感觉网格太多,可以加大网格的范围)
7.以找到的最近点到出发点的距离为基准,看看出发点到周边网格在这个距离内会接触到的(没有在6中遍历过的)有几个网格,把这些网格中的点再查看有没有更近的就行了

注:
1.如果还要优化就是加大网格的层次,可以用多层网格,这就会更复杂一点
2.在网格信息结构(G)中,因为点会移动,那么删点链表节点会有一个查找过程,如果觉得这个慢,那么就在点对象结构体中加一个所属点链表的指针:
class I;
Class A
{
public int ID;
public int X;
public int Y;
publci int Index;//所属网格编号
publci I *pI;
}
....

呵呵，看了lipai006的回答，想了下似乎也是可以实现的，只要多花点内存就可以达到比较好的速度了，而且也不需要真的从X坐标出发这样慢慢的以扇形扩展了啦，通过做一些辅助结构，就直接可以从出发点的X坐标出发，找同X不同Y中Y坐标与出发点最近的就行啦，循环结束条件就是X的扩展距离已经大于当前最小距离，因为再往外也肯定比当前最小距离大了。这个方法也就是要更复杂一些的辅助结构做索引，添加点的时候也要多做些事情，而且实现上的代码相对网格方法复杂一些，但查找速度应该比网格会快一点，因为毕竟是直接找点去了，其实网格方法就是把一批点的X，Y坐标看成是一样的，这样先过滤一批而已，是个速度与复杂度的折中。

xx_lzj:划分区域的目的就是为了使每个区域内的点不能太多，根据我的结构，每个区域有没有点，一个bool判断就够了，不会存在太稀疏影响效率的事情，不过最坏的情况的确会退化到遍历整个点空间，所以这个方法的时间复杂度仍然是O(n)。
你的方法其实和lipai006说的原理是差不多的（如果我对你们链表结构的猜想准确的话），无非就是通过X,Y坐标形成一个二维双向链表，在形成这个链表的过程会比网格相对复杂一点，而且也不是像你想的只要判断8个点就够的，当只有一个点在中间，其他点分布成以这个点为圆心的圆周上时，按照贴主的要求，难道只有8个最近点吗？？在这个情况下，你的最坏复杂度还是O(n)，但就如我说过的，这个方法的平均时间复杂度在参数上是会比网格的低一点，但是算法本身的代码复杂度上会高一点，而且在插入点的过程中的时间消耗会大一点而已。我觉得这是一个整体的过程，不能为了查找的快速牺牲太多其他的时间。
*************
xx_lzj:不好意思，你的链表我还有些不明白的地方:1.二维双向链表每个节点有4个指针，你能否把这4个指针如何获得的说一下，最好不要取边界线上的点，取中间的一个点进行介绍。2.对于初始化和修改点坐标的时候，现有数据如果是链表结构（不是数组），如何能不依靠其他辅助数据进行折半查找？3.修改某个点坐标之后，根据你的链表结构，我感觉不是删除、插入节点这么简单的，能不能具体点说明。