查找上一个统一的网格距离最近点的点云-算法algorithm-CodeGo.net
查找上一个统一的网格距离最近点的点云
我有大小AxBxC与平等的距离d，在网格中的点之间的三维网格。给定一个点数，什么是寻找到最近点的距离对于每个网格点（每个网格点应该包含到最近的点，点云的距离）给出以下假设的最好方法是什么？
有A，B和C的关系为D比较大，给人一种也许500x500x500一个网格，并且将有大约1万点。
此外 CodeGo.net，如果以最近点的距离exceds D的距离，我们并不关心最近点的距离，它可以安全地设置大量的（D也许是2至10天）
由于将有网格点和点大量从一个简单的搜索
for each grid point:
for each point:
if distance between points & minDistance:
minDistance = distance between points
是不是一个很好的选择。
我在想沿着线做的：
create a container of size A*B*C where each element holds a container of points
for each point:
define indexX = round((point position x - grid min position x)/d)
// same for y and z
add the point to the correct index of the container
for each grid point:
search the container of that grid point and find the closest point
if no points in container and D & 0.5d:
search the 26 container indices nearest to the grid point for a closest point
.. continue with next layer until a point is found or the distance to that layer
is greater than D
基本上是：把个水桶，做一个径向向外搜索，直到点被发现在每个网格点。这是解决问题的好方法，还是有更好/更快的方法？一个解决方案，这是很好的并行化是首选。
本文地址 ：CodeGo.net/5053131/
-------------------------------------------------------------------------------------------------------------------------
1.其实，我觉得我有更好的办法去，因为网格点的数目比采样点的数量大得多。让|网格|=N，|样|=M，则最近邻搜索算法就会像O（N LG M），当你需要查找所有N个网格点，每个查询的（最好的情况）O（ LG M）。
相反 CodeGo.net，遍历所有的样本点。存储每个网格点迄今发现最接近的采样点。对于每一个样本点，只检查中的样品的距离为D的所有网格点，以查看是否当前采样比任何处理的样品接近。
运行然后为O（N +（D / D）^ 3米），应该会更好当D / D较小。
甚至当D / D越大，你仍然可能是好的，如果你能制定出一个截断的策略。例如，如果我们正在检查从我们的样本网格点距离5，和网格点已标记为从样品距离为1，则所有的网格点“超越”的网格点不需要进行检查样品被保证是比当前的示例中，我们正在处理接近。所有你需要做的是（我不认为这是很容易的，但应该是可行的）定义什么是“超越”的意思，并找出如何通过电网进行迭代，以避免做任何工作领域的“超越”这样的网格点。
看看八叉树。他们是一个数据结构，能够有效地分割三维空间以这样的方式，以提高查询的是靠近对方空间对象的效率。
您可以在采样点建立一个近邻搜索结构（维基百科），然后问它为每个网格点。有一堆的维基百科页面上。也许octtrees，KD-树，或R-树是适当的。
一种方法，可能会或可能不适合你的应用，是reshape你的思想，并确定每个网格“点”是一个立方体，其将你的空间进入cell的中心。然后，具有这样的cell的三维数组和存储点的cell-选择最合适的数据结构。你自己的话，把分在桶摆在首位。
我猜你可能正在运行某种大规模仿真和建议的做法是不是在这样的应用。在每一个步骤（如果我猜对了），你必须重新计算从小区的距离最近的点，并从cell移动点至cell。这将parallelise很容易。
编辑：谷歌搜索周围的粒子，粒子与粒子粒子可以扔了的想法你。
在基思?兰德尔“的说明
扩大炮弹或立方体周围的startpoints：
人们可以在订单扩大。这里的python式伪：
S = set of 1m startpoints
near = grid 500x500x500 -& nearest s in S
initially s for s in S, else 0
for r in 1 .. D:
for s in S:
for p in shell of radius r around s:
if near[p] == 0:
near[p] = s
if nnew == 0:
remove s from S # bonk, stop expanding from s
“停止从早期的扩展”是天晴1D（邦克左，邦克右）;
但二维/三维壳是不规则的。
它更容易/更快做整个立方体的一个通道：
near = grid 500x500x500 -& { dist, nearest s in S }
initially { 0, s } for s in self, else { infinity, 0 }
for s in S:
for p in approximatecube of radius D around s:
if |p - s| & near[p].dist: # is s nearer ?
near[p] = { |p - s|, s }
这里的“approximatecube”可能是一个完整的DxDxD立方体，
或者你可以砍掉像角（这里2D）
此外FWIW，
与Erik的数字，平均有500立方公尺/ 1M〜2 ^ 7〜5 ^ 3空瓶
每个采样点。
所以，我起初以为是1M左右的采样点5×5×立方体
将覆盖最全格。
事实并非如此，在格点的〜1 / E留下空-泊松艾笛森。
本文标题 ：查找上一个统一的网格距离最近点的点云
本文地址 ：CodeGo.net/5053131/
Copyright (C) 2014 CodeGo.net从传感器和算法原理讲起 机器人是如何避障的_网易科技
从传感器和算法原理讲起 机器人是如何避障的
用微信扫码二维码
分享至好友和朋友圈
避障是指移动机器人在行走过程中，通过传感器感知到在其规划路线上存在静态或动态障碍物时，按照 一定的算法实时更新路径，绕过障碍物，最后达到目标点。避障常用哪些传感器不管是要进行导航规划还是避障，感知周边环境信息是第一步。就避障来说，移动机器人需要通过传感器 实时获取自身周围障碍物信息，包括尺寸、形状和位置等信息。避障使用的传感器多种多样，各有不同的原理和特点，目前常见的主要有视觉传感器、激光传感器、红外传感器、超声波传感器等。下面我简单介绍一下这几种传感器的基本工作原理。超声波超声波传感器的基本原理是测量超声波的飞行时间，通过d=vt/2测量距离，其中d是距离，v是声速，t是 飞行时间。由于超声波在空气中的速度与温湿度有关，在比较精确的测量中，需把温湿度的变化和其它因素考虑进去。上面这个图就是超声波传感器信号的一个示意。通过压电或静电变送器产生一个频率在几十kHz的超声波脉冲组成波包，系统检测高于某阈值的反向声波，检测到后使用测量到的飞行时间计算距离。超声波传感器一般作用距离较短，普通的有效探测距离都在几米，但是会有一个几十毫米左右的最小探测盲区。由于超声传感器的成本低、实现方法简单、技术成熟，是移动机器人中常用的传感器。超声波传感器也有一些缺点，首先看下面这个图。因为声音是锥形传播的，所以我们实际测到的距离并不是 一个点，而是某个锥形角度范围内最近物体的距离。另外，超声波的测量周期较长，比如3米左右的物体，声波传输这么远的距离需要约20ms的时间。再者，不同材料对声波的反射或者吸引是不相同的，还有多个超声传感器之间有可能会互相干扰，这都是实际应用的过程中需要考虑的。红外一般的红外测距都是采用三角测距的原理。红外发射器按照一定角度发射红外光束，遇到物体之后，光会反向回来，检测到反射光之后，通过结构上的几何三角关系，就可以计算出物体距离D。当D的距离足够近的时候，上图中L值会相当大，如果超过CCD的探测范围，这时，虽然物体很近，但是传感器反而看不到了。当物体距离D很大时，L值就会很小，测量?精度会变差。因此，常见的红外传感器 测量距离都比较近，小于超声波，同时远距离测量也有最小距离的限制。另外，对于透明的或者近似黑体的物体，红外传感器是无法检测距离的。但相对于超声来说，红外传感器具有更高的带宽。激光常见的激光雷达是基于飞行时间的（ToF，time of flight），通过测量激光的飞行时间来进行测距d=ct/2，类似于前面提到的超声测距公式，其中d是距离，c是光速，t是从发射到接收的时间间隔。激光雷达包括发射器和接收器 ，发射器用激光照射目标，接收器接收反向回的光波。机械式的激光雷达包括一个带有镜子的机械机构，镜子的旋转使得光束可以覆盖 一个平面，这样我们就可以测量到一个平面上的距离信息。对飞行时间的测量也有不同的方法，比如使用脉冲激光，然后类似前面讲的超声方案，直接测量占用的时间，但因为光速远高于声速，需要非常高精度的时间测量元件，所以非常昂贵；另一种发射调频后的连续激光波，通过测量接收到的反射波之间的差频来测量时间。图一图二比较简单的方案是测量反射光的相移，传感器以已知的频率发射一定幅度的调制光，并测量发射和反向信号之间的相移，如上图一。调制信号的波长为lamda=c/f，其中c是光速，f是调制频率，测量到发射和反射光束之间的相移差theta之后，距离可由lamda*theta/4pi计算得到，如上图二。激光雷达的测量距离可以达到几十米甚至上百米，角度分辨率高，通常可以达到零点几度，测距的精度也高。但测量距离的置信度会反比于接收信号幅度的平方，因此，黑体或者远距离的物体距离测量不会像光亮的、近距离的物体那么好的估计。并且，对于透明材料，比如玻璃，激光雷达就无能为力了。还有，由于结构的复杂、器件成本高，激光雷达的成本也很高。一些低端的激光雷达会采用三角测距的方案进行测距。但这时它们的量程会受到限制，一般几米以内，并且精度相对低一些，但用于室内低速环境的SLAM或者在室外环境只用于避障的话，效果还是不错的。视觉常用的计算机视觉方案也有很多种， 比如双目视觉，基于TOF的深度相机，基于结构光的深度相机等。深度相机可以同时获得RGB图和深度图，不管是基于TOF还是结构光，在室外强光环境下效果都并不太理想，因为它们都是需要主动发光的。像基于结构光的深度相机，发射出的光会生成相对随机但又固定的斑点图样，这些光斑打在物体上后，因为与摄像头距离不同，被摄像头捕捉到的位置也不相同，之后先计算拍到的图的斑点与标定的标准图案在不同位置的偏移，利用摄像头位置、传感器大小等参数就可以计算出物体与摄像头的距离。而我们目前的E巡机器人主要是工作在室外环境，主动光源会受到太阳光等条件的很大影响，所以双目视觉这种被动视觉方案更适合，因此我们采用的视觉方案是基于双目视觉的。双目视觉的测距本质上也是三角测距法，由于两个摄像头的位置不同，就像我们人的两只眼睛一样，看到的物体不一样。两个摄像头看到的同一个点P，在成像的时候会有不同的像素位置，此时通过三角测距就可以测出这个点的距离。与结构光方法不同的是，结构光计算的点是主动发出的、已知确定的，而双目算法计算的点一般是利用算法抓取到的图像特征，如SIFT或SURF特征等，这样通过特征计算出来的是稀疏图。要做良好的避障，稀疏图还是不太够的，我们需要获得的是稠密的点云图，整个场景的深度信息。稠密匹配的算法大致可以分为两类，局部算法和全局算法。局部算法使用像素局部的信息来计算其深度，而全局算法采用图像中的所有信息进行计算。一般来说，局部算法的速度更快，但全局算法的精度更高。这两类各有很多种不同方式的具体算法实现。能过它们的输出我们可以估算出整个场景中的深度信息，这个深度信息可以帮助我们寻找地图场景中的可行走区域以及障碍物。整个的输出类似于激光雷达输出的3D点云图，但是相比来讲得到信息会更丰富，视觉同激光相比优点是价格低很多，缺点也比较明显，测量精度要差 一些，对计算能力的要求也高很多。当然，这个精度差是相对的，在实用的过程中是完全足够的，并且我们目前的算法在我们的平台NVIDIA TK1和TX1上是可以做到实时运行。KITTI采集的图实际输出的深度图，不同的颜色代表不同的距离在实际应用的过程中，我们从摄像头读取到的是连续的视频帧流，我们还可以通过这些帧来估计场景中 目标物体的运动，给它们建立运动模型，估计和预测它们的运动方向、运动速度，这对我们实际行走、避障规划是很有用的。以上几种是最常见的几种传感器 ，各有其优点和缺点，在真正实际应用的过程中，一般是综合配置使用多种不同的传感器 ，以最大化保证在各种不同的应用和环境条件下，机器人都能正确感知到障碍物信息。我们公司的E巡机器人的避障方案就是以双目视觉为主，再辅助以多种其他传感器，保证机器人周边360度空间立体范围内的障碍物都能被有效侦测到，保证机器人行走的安全性。避障常用算法原理在讲避障算法之前，我们假定机器人已经有了一个导航规划算法对自己的运动进行规划，并按照规划的路径行走。避障算法的任务就是在机器人执行正常行走任务的时候，由于传感器的输入感知到了障碍物的存在，实时地更新目标轨迹，绕过障碍物。Bug算法Bug算法应该是最简单的一种避障算法了，它的基本思想是在发现障碍后，围着检测到的障碍物轮廓行走，从而绕开它。Bug算法目前有很多变种， 比如Bug1算法，机器人首先完全地围绕物体，然后从距目标最短距离的点离开。Bug1算法的效率很低，但可以保证机器人达到目标。Bug1算法示例改进后的Bug2算法中，机器人开始时会跟踪物体的轮廓，但不会完全围绕物体一圈，当机器人可以直接移动至目标时，就可以直接从障碍分离，这样可以达到比较短的机器人行走总路径。Bug2算法示例除此之外，Bug算法还有很多其他的变种， 比如正切Bug算法等等。在许多简单的场景中，Bug算法是实现起来比较容易和方便的，但是它们并没有考虑到机器人的动力学等限制，因此在更复杂的实际环境中就不是那么可靠好用了。势场法（PFM）实际上，势场法不仅仅可以用来避障，还可以用来进行路径的规划。势场法把机器人处理在势场下的 一个点，随着势场而移动，目标表现为低谷值，即对机器人的吸引力，而障碍物扮演的势场中的一个高峰，即斥力，所有这些力迭加于机器人身上，平滑地引导机器人走向目标，同时避免碰撞已知的障碍物。当机器人移动过程中检测新的障碍物，则需要更新势场并重新规划。上面这个图是势场比较典型的示例图，最上的图a左上角是出发点，右下角是目标点，中间三个方块是障碍物。中间的图b就是等势位图，图中的每条连续的线就代表了一个等势位的一条线，然后虚线表示的在整个势场里面所规划出来的一条路径，我们的机器人是沿着势场所指向的那个方向一直行走，可以看见它会绕过这个比较高的障碍物。最下面的图，即我们整个目标的吸引力还有我们所有障碍物产生的斥力最终形成的一个势场效果图，可以看到机器人从左上角的出发点出发，一路沿着势场下降的方向达到最终的目标点，而每个障碍物势场表现出在很高的平台，所以，它规划出来的路径是不会从这个障碍物上面走的。一种扩展的方法在基本的势场上附加了?另外两个势场：转运势场和任务势场。它们额外考虑了由于机器人本身运动方向、运动速度等状态和障碍物之间的相互影响。转动势场考虑了障碍与机器人的相对方位，当机器人朝着障碍物行走时，增加斥力， 而当平行于物体行走时，因为很明显并不会撞到障碍物，则减小斥力。任务势场则排除了那些根据当前机器人速度不会对近期势能造成影响的障碍，因此允许规划出 一条更为平滑的轨迹。另外还有谐波势场法等其他改进方法。势场法在理论上有诸多局限性， 比如局部最小点问题，或者震荡性的问题，但实际应用过程中效果还是不错的，实现起来也比较容易。向量场直方图（VFH）它执行过程中针对移动机器人当前周边环境创建了一个基于极坐标表示的局部地图，这个局部使用栅格图的表示方法，会被最近的一些传感器数据所更新。VFH算法产生的极坐标直方图如图所示：图中x轴是以机器人为中心感知到的障碍物的角度，y轴表示在该方向存在障碍物的概率大小p。实际应用的过程中会根据这个直方图首先辨识出允许机器人通过的足够大的所有空隙，然后对所有这些空隙计算其代价函数，最终选择具有最低代价函数的通路通过。代价函数受三个因素影响： 目标方向、机器人当前方向、之前选择的方向，最终生成的代价是这三个因素的加权值，通过调节不同的权重可以调整机器人的选择偏好。VFH算法也有其他的扩展和改进，比如在VFH+算法中，就考虑了机器人运动学的限制。由于实际底层运动结构的不同，机器的实际运动能力是受限的，比如汽车结构，就不能随心所欲地原地转向等。VFH+算法会考虑障碍物对机器人实际运动能力下轨迹的阻挡效应，屏蔽掉那些虽然没有被障碍物占据但由于其阻挡实际无法达到的运动轨迹。我们的E巡机器人采用的是两轮差动驱动的运动形式，运动非常灵活，实际应用较少受到这些因素的影响。具体可以看 一下这个图示：类似这样传统的避障方法还有很多，除此之外，还有许多其他的智能避障技术，比如神经网络、模糊逻辑等。神经网络方法对机器人从初始位置到目标位置的整个行走路径进行训练建模，应用的时候，神经网络的输 入为之前机器人的位姿和速度以及传感器的输 入，输出期望的下一目标或运动方向。模糊逻辑方法核心是模糊控制器，需要将专家的知识或操作人员的经验写成多条模糊逻辑语句，以此控制机器人的避障过程。 比如这样的模糊逻辑：第一条，若右前方较远处检测到障碍物，则稍向左转；第 二条，若右前方较近处检测到障碍物，则减速并向左转更多角度；等等。避障过程中存在哪些问题传感器失效从原理上来讲，没有哪个传感器是完美的，比方说机器人面前是一块完全透明的玻璃，那么采用红外、激光雷达或视觉的方案，就可能因为这个光线直接穿过玻璃导致检测失败，这时候就需要超声波这样的传感器来进行障碍物的侦测。所以我们在真正应用的过程中，肯定都需要采取多种传感器的结合，对不同传感器采集到的数据进行一个交叉验证，以及信息的融合，保证机器人能够稳定可靠的工作。除此之外也有其他模式可能导致传感器失效，比如超声波测距，一般需要超声阵列，而阵列之间的传感器如果同时工作的话，会容易互相产生干扰，传感器A发射的光波反射回来被传感器B接收，导致测量结果出现错误，但是如果按照顺序一个个工作，由于超声波传感器采样的周期相对比较长，会减慢整个采集的速度，对实时避障造成影响，这就要求从硬件的结构到算法都必须设计好，尽可能提高采样速度，减少传感器之间的串扰。还有比如说，机器人如果需要运动的话，一般都需要电机和驱动器，它们在工作过程中都会产生电容兼容性的问题，有可能会导致传感器采集出现错误，尤其是模拟的传感器，所以在实现过程中要把电机驱动器等设备、传感器的采集部分，以及电源通信部分保持隔离，保证整个系统是能够正常工作的。算法设计在刚刚提到的几个算法，很多在设计的时候都并没有完善考虑到整个移动机器人本身运动学模型和动力学模型，这样的算法规划出来的轨迹有可能在运动学上是实现不了的，有可能在运动学上可以实现，但是控制起来非常困难，比如刚刚提到的如果一台机器人的底盘是汽车的结构，就不能随心所欲地原地转向，或者哪怕这个机器人是可以原地转向，但是如果一下子做一个很大的机动的话，我们的整个电机是执行不出来的。所以在设计的时候，就要优化好机器人本身的结构和控制，设计避障方案的时候，也要考虑到可行性的问题。然后在整个算法的架构设计的时候，我们要考虑到为了避让或者是避免伤人或者伤了机器人本身，在执行工作的时候，避障是优先级比较高的任务，甚至是最高的任务，并且自身运行的优先级最高，对机器人的控制优先级也要最高，同时这个算法实现起来速度要足够快，这样才能满足我们实时性的要求。总之，在我看来，避障在某种程度上可以看做机器人在自主导航规划的一种特殊情况，相比整体全局的导航，它对实时性和可靠性的要求更高一些，然后，局部性和动态性是它的一个特点，这是我们在设计整个机器人硬件软件架构时一定要注意的。读者提问环节多机协同的避障策略有哪些？多机协同避障策略在整个SLAM方向上都还是一个在钻研的热点领域，单纯就避障来说，目前的方案是，当有两个或多个机器人协同工作的时候，每个机器人会在一个局部各自维护一个相对的动态地图，所有机器人共享一个相对静态的地图，而对于单个机器人来说，它们会各自维护一个更加动态的地图，这样当两个机器人接近一个位置时，它们会将它们维护的动态地图合并起来。这样子有什么好处呢，比如视觉只能看到前方一个方向，这时候跟后面机器人的动态地图合并之后，就能看到前后整个局部的动态信息，然后完成避障。多机协同的关键在于，两个局部地图之间的分享，就是它们分别在整个相对静态的全局地图上是有一小块一个窗口的位置，到这两个窗口可能融合的话，会把它们融合在一起，同时去指导两个机器人的避障。在具体实现过程中，也要考虑整个信息传输的问题，如果是自己本身的局部地图，由于都是本机的运算，速度一般都比较快，如果是两个机器人协作的话，就要考虑到传输的延时，以及带宽的问题。避障有无标准的测试标准和指标？目前就我所了解业界并没有什么统一的测试标准和指标，我们目前测试的时候会考虑这些指标，比如在单个障碍物或是多个障碍物，障碍物是静态的或动态的情况下避障效果如何，以及实际规划出的路径完美度如何，还有这个轨迹是否平滑，符合我们观感的效果。当然，这个最重要的指标我觉得应该避障是否失败就是成功率的问题，要保证这个避障不管是碰到静态的或者是动态的物体，然后那个物体不管是什么材质，比如说如果是动态的人，我们穿什么样的衣服会不会对整个避障功能造成影响，另外就是不同的环境又会有什么样的影响，比如光线充足或暗淡。对于避障来说，成功率才是最为关键的。AI新时代-产业新动能，参加2016中国人工智能产业大会，抢占通往未来的年票！（如无法点击请打开网址/4BYwdQ）
本文来源：雷锋网
责任编辑：张彬彬_NT5025
用微信扫码二维码
分享至好友和朋友圈
加载更多新闻
热门产品:　　　
:　　　　　　　　
:　　　　　　　　　
热门影院：
阅读下一篇
用微信扫描二维码
分享至好友和朋友圈4170人阅读
理论随谈（3）
问题描述：给定平面上N个点的坐标，找出距离最近的两个点。
这是编程之美2.11的一道题目，从昨天到现在就一直在设法解决它；如果用常规的解法，只需要将N个点两两计算距离，然后找出最小距离的两个点就可以了；但是这种解法的算法复杂度为O(N^2); 为了降低算法的复杂度，我们需要有更好的方法。这里我们找到的解法是分治法。
设点集为S，|S|=N，S的横坐标集合为Sx，纵坐标集合为Sy;
算法的步骤如下：
1.找出Sx的中位数:median_Sx;用median_Sx对点集S进行划分，左边的为S1，右边的为S2;
2.分别求出S1和S2中的最近点对，设S1和S2中最近点对的距离分别为:delta(S1), delta(S2);
3.求出S1和S2最近点对距离的较小值：Delta = min{delta(S1), delta(S2)};
4.找出S2中y值前6大的点，设为S2’.(此处不用排序，用O(n)时间找出第i大的点，因为排序的时间复杂度为O(n*logn), 网上绝大部分的算法是用排序，显然用排序的方法来找出前6大的点效率低下）;
5.对于S1中的每一个点，与S2’中的每一个点计算距离delta’, 如果delta’ & Delta，令Delta=delta’;
现在我们分析一下上述算法的时间复杂度，由于我们采用中位数进行划分，每一次划分都能确保点集被分为大小相当的两个部分，所以：
T(n)= 2*T(n/2) + 合并复杂度。 由于合并的时候，是用S1中的n/2个点和S2中最多6个点进行比较，比较的次数为n/2 * 6 = 3n. 所以
T(n)= 2*T(n/2)+O(n). 由《算法导论》中文第二版44页的主定理，可知T(n) = O(n*log(n));
算法第4步中，为什么只用选取S2中最多前6大的6个点进行比较呢？对这个问题，《编程之美》上没有说清楚，这里再详细的论证下；
如下图所示：
在上图中，我们有一系列的点，按照上述的算法，我们利用median(中位数)将点分为了S1和S2两个部分，安装算法的第2、3步我们可以求得δ，在图中median线的左边和右边，距离其δ的距离，分别作两条直线，和直线median一起，我们得到了两个区域，分别为a1、a2，如图所示。由于δ是S1和S2中距离较小者，由此可知，a1和a2区域内不可能再存在距离&δ的两个点对。那么，最近点对要么是S1，S2各自内部的某两个点，或者是一个点在S1中、一个点在S2中。在求得δ后，我们只需要查看是否存在两个点，他们满足条件：一个在a1中，一个在a2中；并且它们之间的距离d&δ;
仔细观察上图，我们来证明区域a2中最多只可能存在6个点；
根据δ定义，我们知道，a2中的任意两点的距离都必须大于δ，否则与δ的定义相矛盾。如下图所示，我们将*2δ的矩形区域，分成边长为1/2δ
*2/3δ的六个小矩形，如图中的红色编号1..6所示。我们假设该区域内的点大于6个，那么根据鸽笼原理，那么必然有一个小矩形中存在至少两个点，这两个点的距离必然小于边长为1/2δ *2/3δ矩形的对角线，即D^2&（1/2δ)^2 + (2/3δ)^2=(5/6δ)^2&δ^2;所以a2矩形区域当中的点数不可能大于6.最多就6个点，这种情况是如上图中红色的A,B…EF所示。
根据上面的算思想，我们利用线性时间O(n)查找中位数的算法，来找到中位数，并且对集合进行划分，这样就确保了每次都是T(n)=T(n/2)+O(n).关于中位数和顺序统计学可以参考：
本问题的代码如下所示（有点长），有错误的地方还望大家批评指正~~
Author:JustinZhang
Time:日11:29:25
End: 日16:56:35
Desc:平面上有N个点，找出N个点中距离最近的两个点；如果用穷举法，那么算法的复杂度将达到O(n^2)；
本算法采用分治法，可以将复杂度降低到O(n*log(n));
#include &iostream&
#include &vector&
#include &iomanip&
#include &algorithm&
#include &cmath&
using namespace
//delta=min{min(dest(S1), min(dest(S2}}.
double delta = INT_MAX;
void swap(int &x, int &y)
//插入排序算法
void insert_sort(vector&int&&A, int p, int r)
int key = 0;
for (i=p+1; i&=r; i++)
key = A[i];
j = i - 1;
while (j&=p && A[j]&key)
A[j+1] = A[j];//将A[j]往前移动
A[j+1] =
//将整型容器划分为两个部分
int partion(vector&int& &A,int p, int r)
int count = p - 1;
int key = A[r];
for (int i=p; i&=r-1; i++)
if (A[i] & key)
count++;
swap(A[count],A[i]);
swap(A[count+1],A[r]);
return count+1;
//根据算法导论上的思想，取得中位数的中位数
int get_median(vector&int&&data, int p, int r)
int i=0, j=0;
int n = r - p + 1;
//获得原始数组数据个数
int remains = n%5;
int int_count = n -
int int_group = int_count/5;
int group_count = (n+4)/5;
//计算出五个元素一组的组数；
//int *group_median = new int[group_count];
vector&int& group_median(group_count);
return data[p];
//以下代码求出五个元素为一组的中位数
if (0 == remains) //如果元素的个数正好可以分为以5个元素为单位的整数组
for (i=p; i&=r-4; i=i+5)
insert_sort(data, i, i+4);
group_median[(i-p)/5] = data[p+2];
for (i=p; i&=(r-remains-4);i=i+5)
insert_sort(data, i, i+4);
group_median[(i-p)/5] = data[i+2];
//处理不够5个元素的组，改组开始的序号为r-remains+1，结束序号为r
insert_sort(data,r-remains+1,r);
group_median[group_count-1] = data[r-remains+1+remains/2];
if (group_count==1)
return group_median[0];
return get_median(group_median,0,group_count-1);
/*就是因为get_position函数写错了，导致很久都没有能够发现错误，要仔细啊~~*/
int get_position(vector&int& &A, int p, int r, int key)
for (int i=p; i&=r; i++)
if (A[i]==key)
return -1;
//该函数是为了找到数组A中，第seq小的数
int select(vector&int& &A,int p, int r, int seq)
//获得数组A的中位数的中位数，将其作为划分数组的支点
int pivot_key = get_median(A, p, r);
int pos = get_position(A,p,r,pivot_key);
swap(A[pos],A[r]);
int i = partion(A, p, r);
int x = i - p + 1;
if (seq == x)
return A[i];
else if (seq & x)
select(A, p, i-1, seq);
select(A, i+1, r, seq-x);
class Point
Point(int x=0, int y=0)
Point& operator=(const Point &p)
this-&x = p.x;
this-&y = p.y;
return *this;
Point(const Point &pp)
this-&x = pp.x;
this-&y = pp.y;
friend ostream &operator&&(ostream &os, const Point & p)
os&&&(&&&p.x&&&,& && p.y && &)&;
//将两个点交换
void swap_point(Point &p1, Point &p2)
Point tmp = p1;
//根据点容器的最后一个点，将点集合划分为两个部分
int partion_Point_Set(vector&Point& &p,int l, int r)
int count = -1;
int key = p[r].x;
for (unsigned i=0; i&=p.size()-2; i++)
if (p[i].x&key)
count++;
swap_point(p[i],p[count]);
swap_point(p[count+1],p[r]);
return count+1;
//获得两点间的距离
double Distance(const Point &p1, const Point &p2)
int x = (p1.x - p2.x);
int y= (p1.y - p2.y);
double distance = sqrt((double)(x*x+y*y));
//找到两个数的最小值
double min(double x, double y)
//按照点的x坐标来检索点在容器中的位置
int get_point_position_x(const vector&Point& &p, int l, int r, int x_key)
for (int i=l; i&=r; i++)
if (p[i].x == x_key)
return -1;
//按照点的y坐标来检索点在容器中的位置
int get_point_position_y(const vector&Point& &p, int l, int r, int y_key)
for (int i=l; i&=r; i++)
if (p[i].y == y_key)
return -1;
//找到p中y坐标第order大的点
Point select_point(vector&Point& &p,int l, int r, int order)
vector&int& point_y;
for (int i=l; i&=r; i++)
point_y.push_back(p[i].y);
int key_y = select(point_y,0,point_y.size()-1,order);
int position_y = get_point_position_y(p, 0, p.size()-1,key_y);
return p[position_y];
double get_minimum_distance(vector&Point& &p,int l, int r,vector&Point& &result)
int i=0,j=0;
if ((r-l+1)==2)//如果点数为两个
double ret = Distance(p[l],p[r]);
if (ret & delta)
result[0]=p[l];
result[1]=p[r];
else if ((r-l+1)==3) //如果点数为3个
double tmp_dis1 = Distance(p[l],p[l+1]);
double tmp_dis2 = Distance(p[l],p[l+2]);
double tmp_dis3 = Distance(p[l+1],p[l+2]);
double ret = min(min(tmp_dis1,tmp_dis2),tmp_dis3);
if (ret &delta )
if (tmp_dis1 == ret)
result[0] = p[l];
result[1] = p[l+1];
else if (tmp_dis2==ret)
result[0]=p[l];
result[1]=p[l+2];
result[0]= p[l+1];
result[1]= p[l+2];
else //大于三个点的情况
//求出点集p的x坐标和y坐标
vector&int& P
vector&int& P
for (i=l; i&=r; i++)
Pointx.push_back(p[i].x);
Pointy.push_back(p[i].y);
//找到点x坐标的中位数
int x_median = select(Pointx,0,Pointx.size()-1,(Pointx.size()+1)/2);
int point_median_pos = get_point_position_x(p,l,r,x_median);
swap_point(p[point_median_pos],p[r]);
//利用找到的中位数对点集进行划分
int point_pivot_index = partion_Point_Set(p,l,r);
//利用x坐标作为中位数，将点集合划分好后，递归的求中位数左边点集S1和右边点集合S2距离最小值；
//考虑如何将距离最小的两个点保存下来
double min_s1 = get_minimum_distance(p,l,point_pivot_index,result);
double min_s2 = get_minimum_distance(p,point_pivot_index+1,r,result);
if (min_s1&min_s2)
delta = min_s2;
//result[0] = tmp_result1;
//result[1] = tmp_result2;
delta = min_s1;
//现在已经递归的求到了S1和S2中点集合最短距离，下面开始求S1和S2之间点之间的距离
//找出点集合S2中，y坐标前六大的点,如果|S2|&6，则只需找出|S2|个点
int size_s2 = (r-point_pivot_index&6)?r-point_pivot_index:6;
vector&Point& S2;
for (i=1;i&=size_s2;i++)
tmp = select_point(p,point_pivot_index+1,r,i);
S2.push_back(tmp);
for (i=l; i&=point_pivot_ i++)
for (j=0; j&size_s2; j++)
double d = Distance(p[i],S2[j]);
if (d & delta)
result[0]= p[i];
result[1]= S2[j];
void getinput(vector&Point& &p)
int Pointnumber = 0;
cout && &please input Point numbers& &&
for (i=0; i&P i++)
cin && pp.x;
cin && pp.y;
p.push_back(pp);
int main()
vector&Point& result(2);
vector&Point&
getinput(input);
double minimum_distance = get_minimum_distance(input,0,input.size()-1,result);
cout && &The nearest point is: &&&result[0] && & and & && result[1] &&
cout && &their distance is : &&&minimum_distance &&
运行结果如下：
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：29667次
排名：千里之外
原创：24篇
转载：12篇
(1)(6)(6)(1)(1)(4)(7)(1)(1)(1)(9)}