擅长:python、mysql、java
<p>接受的答案并不能完全解决问题,问题要求找到两组点之间的最小距离,而不是两组中每个点之间的距离。</p>
<p>尽管原问题的直接解决方法确实包括计算每个</strong>对之间的距离并随后找到最小值,但如果只对</strong>最小值</strong>距离感兴趣,则这是不必要的。对于后一个问题有一个更快的解决方案。</p>
<p>所有建议的解决方案都有一个运行时间,可扩展为<code>m*p = len(xy1)*len(xy2)</code>。这对于小数据集来说是可以的,但是可以编写一个最佳的解决方案,它可以扩展为<code>m*log(p)</code>,从而为大型<code>xy2</code>数据集带来巨大的节省。</p>
<p>使用<a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.cKDTree.html" rel="noreferrer">scipy.spatial.cKDTree</a>可以实现这种最佳的执行时间缩放,如下所示</p>
<pre><code>import numpy as np
from scipy import spatial
xy1 = np.array(
[[243, 3173],
[525, 2997]])
xy2 = np.array(
[[682, 2644],
[277, 2651],
[396, 2640]])
# This solution is optimal when xy2 is very large
tree = spatial.cKDTree(xy2)
mindist, minid = tree.query(xy1)
print(mindist)
# This solution by @denis is OK for small xy2
mindist = np.min(spatial.distance.cdist(xy1, xy2), axis=1)
print(mindist)
</code></pre>
<p>其中<code>mindist</code>是<code>xy1</code>中的每个点与<code>xy2</code>中的一组点之间的最小距离</p>