0

I have a problem as described in the title and I am using MATLAB 2020.

I have 2 sets of 2D points, and I want to find the two points (each point from a different set) that has the minimal distance from all the other points min(distance(pi,pj)) I done some research (google) and found this article: "Optimal Algorithms for Computing the Minimum Distance Between Two Finite Planar Sets" in this web page:

What is the fastest algorithm to calculate the minimum distance between two sets of points?

I tried to implement the algorithm, using MATLAB, and a code for Garbriel graph (which I found in google) here:

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

the problem is that when I run the code,which suppose to be the algorithm vs a "brute force algorithm" (two loops) , the brute force is always faster... no matter how many points I used , and it is way faster... which is in contrast to logic (mine) and the article mention above.

when I check the execution time of the code lines, I found that the line

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

in :

minDistancePoints(p1, varargin)

is the "problem" and advises? thank you

p.s let

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

i want to find the point1 in set1 and the point2 in set2 that have minimum distance from all the other points.

obchardon
  • 10,614
  • 1
  • 17
  • 33
Nevo Brimberg
  • 1
  • 1
  • Can you share an example? Bruteforce will be faster if each of your set of 2D points have 1 point. Likely the alternative will be faster if you have 1 million points. Maybe the implementations of each of the methods are suboptimal. We can't know without a complete example – Ander Biguri Jul 28 '20 at 07:49
  • 1
    That Gabriel graph routine (1) seems to itself compute all pairs distances (2) calls `delaunayn`. You should just build on top of `delaunayn` directly. – David Eisenstat Jul 28 '20 at 10:52
  • 1
    Have you tried [dsearchn](https://www.mathworks.com/help/matlab/ref/dsearchn.html)? – rahnema1 Jul 29 '20 at 02:38

1 Answers1

0

Using implicit expansion, we can compute all the possible combination at once and then find point in p1 that minimize the sum of the distance:

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))

I add a dimension to p1 with: permute(p1,[3,2,1]), so now we can compute all the combination in this new third dimension.

closest_p1 give the index of the point that minimize the sum of the euclidian distance between each points in p2. In this example closest_p1 = 2.

Noticed also that the algorithm that you use seems to also compute all the possible combination.

obchardon
  • 10,614
  • 1
  • 17
  • 33
  • i forgot to mention that, since my code suppose to run several times with a large amount of points (data) , i want the code to be efficient as possible, from what i read the most efficient is of O(nlog n) – Nevo Brimberg Jul 28 '20 at 10:09