擅长:python、mysql、java
<p>类似于Caleb的答案,但是如果您得到的距离大于某个先前的最小距离,您可以停止迭代循环(抱歉-没有代码)。在</p>
<p>我以前常编视频游戏。计算两点之间的实际距离需要太多的CPU。我们所做的是将“屏幕”划分成更大的笛卡尔平方,并且如果Delta-X或Delta-Y“太远”则避免实际的距离计算-这只是减法,所以也许类似这样的东西来限定需要实际欧几里德距离度量计算的地方(根据需要扩展到n维)?在</p>
<p>编辑-扩展“太远”候选对选择注释。
为了简洁起见,我将假设一个二维的场景。
取兴趣点(X0,Y0)并围绕该点“画”一个nxn正方形,原点是(X0,Y0)。在</p>
<p>浏览初始点列表,并在该方格内形成候选点列表。在此过程中,如果DeltaX[ABS(Xi-X0)]在正方形之外,则无需计算DeltaY。在</p>
<p>如果没有候选点,则使正方形变大并迭代。在</p>
<p>如果只有一个候选点,并且它在正方形表示的圆的半径内,那就是你的最小值。在</p>
<p>如果有“太多”候选项,将正方形缩小,<em>,但只需重新检查此迭代中的候选项列表,而不是所有点。</em></p>
<p>如果没有“太多”候选对象,则计算该列表的距离。执行此操作时,首先计算第一个候选人的DeltaY^2+DeltaY ^2。如果对于后续候选对象,DetlaX^2大于到目前为止的minumin,则不需要计算DeltaY^2。在</p>
<p>如果最小值在正方形内接圆的半径内,则该计算得出的最小值为最小值。在</p>
<p>如果没有,则需要返回上一个候选列表,该列表包含半径为该最小值的圆内的点。例如,如果以一个2x2正方形中的一个候选对象结束,该正方形恰好位于顶点X=1,Y=1上,则距离/半径将为SQRT(2)。所以回到前面的一个候选列表,这个列表的正方形变灰或等于2xSQRT(2)。在</p>
<p>如果有必要,生成一个新的候选列表,该列表只包含带有+/-SQRT(2)正方形的点。
按上述方法计算这些候选点的距离-忽略目前为止超过最小计算值的任何点。在</p>
<p>只有一个候选者时,才需要求增量^2和的平方根。在</p>
<p>如何调整初始正方形的大小,或者它是否应该是一个矩形,以及如何增加或减少正方形/矩形的大小都会受到数据分布应用知识的影响。在</p>
<p>如果您使用的语言支持递归算法,我会考虑使用递归算法。在</p>