find closest Coordinates to a point

I need to find closest point to A=[6,8] among B=[1,2 ; 5,7 ; 3,10 ; ...], and i need to return those coordinates: for example in this case: [5,7]

Answer 1

[W. Owen Brimijoin]

In your example, you are returning A, rather than the closest point in B... assuming that the answer you are looking for was actually [5,7], then the following should get the job done:

%make some example random values:
A = rand(1,2);
B = rand(10,2);

%compute Euclidean distances:
distances = sqrt(sum(bsxfun(@minus, B, A).^2,2));

%find the smallest distance and use that as an index into B:
closest = B(find(distances==min(distances)),:);

Should work fine!

[Aidin]

Yes sorry for the wrong info!

[Aidin]

It works like a charm! thank you so much

[Azzi Abdelmalek]

You don't need to use find

closest = B(distances==min(distances)),:)

[yashvin]

Does this solution works event for negative number search?

[Walter Roberson]

Yes.

[D.J. Klomp]

You don't need the sqrt in the answer, dropping it significantly decreases computation time for large arrays.

[Jan]

@D.J. Klomp: Exactly. Since Matlab R2016b you do not need bsxfun also:

%make some example random values:
A = rand(1,2);
B = rand(10,2);
%compute Euclidean distances:
dist2 = sum((B - A) .^ 2, 2);
%find the smallest distance and use that as an index into B:
closest = B(dist2 == min(dist2),:);

[nihed sboui]

hi , i have two graph one is fixed and the other one is changing (64 graphe )i want to find the most close graphe to the fixed one .please help??

[Dora de Jong]

How do you make the script when you have more points for A?

%make some example random values:

A = rand(2,2); %So not A = rand(1,2) but A = rand(2,2)

B = rand(10,2);

%compute Euclidean distances:

dist2 = sum((B - A) .^ 2, 2);

%find the smallest distance and use that as an index into B:

closest = B(dist2 == min(dist2),:);

[Image Analyst]

@Dora Jong, use pdist2() if you have the Signal Processing Toolbox.

[Dora de Jong]

Thank you for your respons. I don't have that toolbox. I am making a for loop. But it does not work. Can you help me?

%A and B
A = [1 2 ; 
    5 6];
B = [2 3;
    4 5];
for s=1:2
dist2= ( (B(:,1) - A((s),1)).^2  + (B(:,2) - A((s),2)).^2 ) .^0.5;
B_INDX=dist2 == min(dist2);
closest(s)=B_INDX'.*B;
end

[Walter Roberson]

A = [1 2 ; 
    5 6];
B = [2 3;
    4 7];

dist2 = reshape(sqrt(sum(((A - permute(B, [3 2 1])).^2),2)),size(A,1),[])

dist2 = 2×2

1.4142 5.8310 4.2426 1.4142

Read this as the first column of the result is comparing each row of A to the first row of B, then the second column of the result is comparing each row of A to the second row of B, and so on. You would take the minimum across the second dimension to find which row of B that each row of A is closest to.

[Dora de Jong]

Thank you all!!

In the end I used pdist2! Is works really nice.

But every one thank you for the help

Answer 2

[Azzi Abdelmalek]

A = rand(1,2);
B = rand(10,2);
dist=bsxfun(@hypot,B(:,1)-A(1),B(:,2)-A(2));
out = B(dist==min(dist),:)

[Aidin]

Yes i found out that it is better to not use Find as '==' is more efficient

[MA-Winlab]

How to get the closest N points to the centroids in Kmeans?

Any help is appreciated

Thank you

[Walter Roberson]

Closest for each group, or closest overall ?

When the separation between groups is not crisp, a point associated with cluster A could end up being one of the N closest points to cluster B. Even with sharp clusters, some of the clusters could end up small.

If N closest overall is good enough, then pdist2() and sort the distances with indices output and take the first N per row.

[MA-Winlab]

@Walter, thank you for the reply. I want to get (for example) the 10 closest points to the centroid in each cluster.

What do you mean by closes overall? to which point(centroid) they will be closest?

[Walter Roberson]

A1         A3
   AC   A2
     B1B2B3
       BCB4

Here, A1 and A2 are part of a cluster with centroid AC. B1, B2, B3, B4 are part of a cluster with centroid BC. The two closest points to AC over all of the points are A1 and B1. The two closest points to AC within the cluster are A1 and A2.

Would the answer you would be looking for, for 2 closest points, be A1, A2, or would it be A1, B1 ?

[MA-Winlab]

I see. I undestarnd from the example that B1 in a diffrent cluster than that if A1 after doing the clustering.

If my assumption is correct, then I want A1 & A2, i.e. the points that belong to the cluster of that given centroid, after doing the clustering.

Answer 3

[Peter Barsznica]

dsearchn: N-D nearest point search.

[k, d] = dsearchn(A,B) "returns the distances, d, to the closest points. d is a column vector of length p."

http://au.mathworks.com/help/matlab/ref/dsearchn.html?s_tid=gn_loc_drop

Answer 4

[Peyman Obeidy]

This is very helpful, thank you for sharing.

A question, how do I get the indexes for B (I want the index of the value which are in B list and have been selected as the closest to A values)?

Many thanks for your help

[Jan]

In the suggested codes this is done by:

distances==min(distances)        % logical indexing
find(distances==min(distances))  % With FIND

This considers multiple occurrences of the minimal value. If only one occurrence is required, use:

[distances, index] = min(distances);

Answer 5

[Peyman Obeidy]

I have multiple values for A, so what I did is as follows;

 PointinCh1 = 

    20   482
    19   359
    45   438
    61   248
    90   403
   104    95
   149   335
   148   392
   161    73
   186    29
   188   236
   189   319
   200   162
   208    70
   204   198
   203   343
   214   250
   225   307
   233   171
   238   205
   237   245
   253   148
   264   362
   281    34
   300   341
   306    88
   305   203
   328   234
   326   164
   330    20
   364   199
   424   241
   433   314
   491   187
PointinCh2 = 

    99   399
   104    95
   149   335
   148   392
   158    82
   184   238
   190   320
   202   343
   236   246
   263   361
   299   342
   330    20
   493   193
%compute Euclidean distances:
for idis=1: length(PointinCh1)
distances = sqrt(sum(bsxfun(@minus, PointinCh2, PointinCh1(idis,:)).^2,2));
%find the smallest distance and use that as an index into B:
closestForPin2toPin1(idis,:)= PointinCh2(find(distances==min(distances)),:);
end

[Jan]

You can use the 2nd output of the min command:

[value, index] = min(distances);
closestForPin2toPin1(idis,:)= PointinCh2(index,:);

This uses the first occurence, while your code fails, if the minimal distance exists multiple times.

[Johannes Stoerkle]

If A has multiple points which should be found nearby a grid named B, one can first crop the grid to the points. Second, one can do a coase search by means of a square and finally, the closest points to the grid can be computed:

% find points in A next to grid B, where size(A)>>size(B)
A = rand(2000,2); % point positions
[X, Y] = meshgrid(linspace(0,1,5),linspace(0,1,5));
B = [X(:), Y(:)]; % grid positions

% crop B to area A
dxA = max(A(:,1))-min(A(:,1));
dyA = max(A(:,2))-min(A(:,2));
scaleWind = 0.1;
xRangeA = [min(A(:,1))-dxA*scaleWind max(A(:,1))+dxA*scaleWind];
yRangeA = [min(A(:,2))-dyA*scaleWind max(A(:,2))+dyA*scaleWind];
idxB_inA = xRangeA(1)<=B(:,1) & B(:,1)<=xRangeA(2) & ...
           yRangeA(1)<=B(:,2) & B(:,2)<=yRangeA(2);
B = B(idxB_inA,:);

% coase search: find points in squares centered at grid points
Npoints = size(A,1);               % number of points
Ngrid   = size(B,1);               % number of points on grid
dX = max(B(:,1))-min(B(:,1));
dY = max(B(:,2))-min(B(:,2));
% charactersitic length for the square (empirical determined)
dL = max(abs([dX;dY]))/sqrt((Npoints+Ngrid)/20); 
idxPreSearch =  A(:,1)>B(:,1).'-dL & A(:,1)<B(:,1).'+dL & ...
                A(:,2)>B(:,2).'-dL & A(:,2)<B(:,2).'+dL;

% find index-number of closest point for each grid-item
nIdxPointMinAll = nan(Ngrid,1);
for iGrid=1:Ngrid
    idxTemp = idxPreSearch(:,iGrid);
    nIdxTemp = find(idxTemp);
    % compute Euclidean distances
    dist2 = sum((B(iGrid,:) - A(idxTemp,:)).^ 2, 2);
    nIdexPointMin = dist2 == min(dist2); 
    if ~isempty(nIdexPointMin)
        nIdxPointMinAll(iGrid) = nIdxTemp(nIdexPointMin);
    end
end
nIdxPointMinAll(isnan(nIdxPointMinAll)) = [];
nIdxPointMinAll = unique(nIdxPointMinAll);

figure; hold on; plot(A(:,1),A(:,2),'.g'); 
plot(B(:,1),B(:,2),'*r')
plot(A(idxPreSearch(:,floor(Ngrid/3)),1),A(idxPreSearch(:,floor(Ngrid/3)),2),'.k')
plot(A(nIdxPointMinAll,1),A(nIdxPointMinAll,2),'+b')

Answer 6

[alberto bodoque]

So the problem that I need to solve is that I have 6 landfills and I have to place 2 treatment plants but I have to do this considering the minimum total distance between the landfills and the plants. For example: lets say that 1 plant supports landfill 1 and 2 and that the other supports 3,4,5 and 6. That was one possibility but I need to explore all the possibilities and then see which one gives me the less total distance that it has to be cover between the landfills and the plants that is translated in transportation cost.

Let me know if you have more doubts about the statement of this problem and I hope you can help me!

[Jan]

Please do not attach a new question to an existing thread, even if the topics are similar. Open your own question. If it seems to be useful, add a link to this thread. Then please delete this message here, because it is not an answer.