谁能告诉我扩管的理论算法。谢了

谁能告诉我扩管的理论算法。谢了

用现在的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.修改某个点坐标之后，根据你的链表结构，我感觉不是删除、插入节点这么简单的，能不能具体点说明。