时间戳

首页 > 解决方案 > 两组 2D 点 (x1,y1) , (x2,y2) 之间的最小距离

algorithm - 两组 2D 点 (x1,y1) , (x2,y2) 之间的最小距离

问题描述

我遇到了标题中描述的问题，我正在使用 MATLAB 2020。

我有 2 组 2D 点，我想找到与所有其他点的距离最小的两个点（每个点来自不同的集合）min(distance(pi,pj)) 我做了一些研究（谷歌）并找到了这篇文章：“Optimal Algorithms for计算两个有限平面集之间的最小距离”在这个网页：

计算两组点之间最小距离的最快算法是什么？

我尝试使用 MATLAB 和 Garbriel 图的代码（我在 google 中找到）在这里实现该算法：

http://matgeom.sourceforge.net/doc/api/matGeom/graphs/gabrielGraph.html

问题是当我运行代码时，假设是算法与“蛮力算法”（两个循环），蛮力总是更快......无论我使用了多少点，而且速度更快...这与逻辑（我的）和上面提到的文章相反。

当我检查代码行的执行时间时，我发现该行

dist = dist + (repmat(p1(:,i), [1 n2])-repmat(p2(:,i)', [n1 1])).^2;

在 ：

minDistancePoints(p1, varargin)

是“问题”和建议？谢谢你

ps让

set1=random(100,2) 
set2=random(100,2)

我想找到 set1 中的 point1 和 set2 中的 point2 与所有其他点的距离最小。

标签： algorithmmatlab

解决方案

使用隐式扩展，我们可以一次计算所有可能的组合，然后找到p1使距离之和最小的点：

p1 =    [0 -1;
         2 3;
         8 8]
p2 =    [1 1;
         2 3;
         3 5;
         3 3]
         
[~,closest_p1] = min(sum(sum((permute(p1,[3,2,1])-p2).^2,2).^0.5))

p1我在with:中添加了一个维度permute(p1,[3,2,1])，所以现在我们可以计算这个新的第三维度中的所有组合。

closest_p1给出使 中每个点之间的欧几里得距离之和最小化的点的索引p2. 在这个例子closest_p1 = 2中。

还注意到您使用的算法似乎也计算了所有可能的组合。

推荐阅读