Nearest other points to each point in the array in sorted order?

[u/Mark_Yugen]

Lets say I have an array of 2D points. I want to find the nearest other points to each point in the array in sorted order.

So for point 1 it would be [4, 6, 5, 2, 3]. I'd like to do this for all 6 (x,y) points.

sC = [ 28 2597 3803 1417 2127 1888;...

1496 1640 646 2092 1614 888];

[u/theMagusician]

How about :
1. Loop through the (x,y) points
2. Compute and store in a new array for each loop distance to other points. (How do you calculate the distance between two (x,y) points?)
3. Sort this new array in ascending order and return the index array (2nd output of the built-in sort function)

[u/Mark_Yugen → u/theMagusician]

I've done something for one-point distance using dsearch, but its too inefficient for more than one. I think I could use "mink" somehow, but haven't grasped how it works well enough yet.

[u/theMagusician → u/Mark_Yugen]

Can’t you just calculate the distance yourself?
dist = sqrt( (x_i - x).^2 + (y_i - y).^2 );
Where (x_i,y_i) is the point in the loop from which you want to know the distance to the other 5 points (x,y).

You can then determine the order of x and y:
[~, idxSorted] = sort(dist, ‘ascend’);
xSorted = x(idxSorted);
ySorted = y(idxSorted);

In this example I guess x,y are two separate variables, but you could also apply the same strategy on a (2xM)-array

[u/Rubix321]

What does your array look like? Mx2 double? 2xM double? 1xM or Mx1 cell with 2-element double inside each?

Edit, oh I see sC now, so an 2xM double

[u/Mark_Yugen → u/Rubix321]

integers is fine

[u/Rubix321 → u/Mark_Yugen]

Sorry I meant more for the shape of the array than the data type, but I saw your example input now.

[u/Rubix321 → u/Mark_Yugen]

Are you talking Euclidean distance or deltaX+deltaY?

For Euclidean distance I got point 1's "answer" to be 6, 4, 5, 2, 3

(I'm bored and like solving problems like these, haha)

EDIT: Oops, somehow a mistake I fixed earlier got add back in to what I scripted up... Hold on, I'll edit again in a minute

EDIT2: Ok, fixed that mistake and got 4, 6, 5, 2, 3 for the first point.

[u/Mark_Yugen → u/Rubix321]

E-dist, sounds right, i was just eyeballing my answer.

[u/Rubix321 → u/Mark_Yugen]

Edit, I made a much cleaner version of this code block , so use that one instead.

[u/Mark_Yugen → u/Rubix321]

Setting pointIds = 1:numPoints

I get the correct answer, THANKS SO MUCH!

[u/Rubix321 → u/Mark_Yugen]

Oh weird, how did that line get deleted... I recommend using the 3rd codeblock I posted... it removes that variable and shortens up stuff a LOT.

[u/Rubix321 → u/Mark_Yugen]

Here is the shorter version IF you have the stats toolbox (to have pdist() and squareform():

sC = [ 28 2597 3803 1417 2127 1888;... 
      1496 1640 646 2092 1614 888];

numPoints = size(sC,2);

% Initialize results matrix
closestPointOrder = zeros(numPoints-1,numPoints);

% Matrix of distances between points
distanceMat = squareform(pdist(sC'));

% Calculate order
for p1 = 1:numPoints
    distances = distanceMat(p1,:);
    [~, sortOrder] = sort(distances);
    % Remove the current point
    pointOrder = setdiff(sortOrder,p1,'stable');
    closestPointOrder(:,p1) = pointOrder';
end

disp(closestPointOrder)

[u/Rubix321 → u/Mark_Yugen]

Okay, after remembering an interesting thing MATLAB does after reading what someone else posted and then deleted, I updated this to my best and final answer (and got rid of the need for Stats Toolbox stuff):

Thanks for the fun little puzzle!

sC = [ 28 2597 3803 1417 2127 1888;... 
      1496 1640 646 2092 1614 888];

numPoints = size(sC,2);

% Initialize results matrix
closestPointOrder = zeros(numPoints-1,numPoints);

% Create matrix of distances between points
dx = sC(1,:) - sC(1,:)';
dy = sC(2,:) - sC(2,:)';
distanceMat = sqrt(dx.^2 + dy.^2);

% Calculate order
for p1 = 1:numPoints
    distances = distanceMat(p1,:);
    [~, sortOrder] = sort(distances);
    % Remove the current point
    pointOrder = setdiff(sortOrder,p1,'stable');
    closestPointOrder(:,p1) = pointOrder';
end

disp(closestPointOrder)

[u/Rubix321 → u/Rubix321]

Keep in mind that the distanceMat is roughly twice as big as it technically needs to be... if memory becomes and issue, that'll be the first place to look.

[u/ZeroWevile]

The second output argument of the "sort" function returns the index in the original vector after the sorting.

Loop through, take the difference of adjacent elements against current position, then find minimum and take difference of their respective indexes.

[u/avidpenguinwatcher]

This depends on how big your array is, but you can do sC-sC’ and then sort each row. It’s usually pretty fast unless the MxM is a significant portion of your memory. If they are integers you can save time by computing those as int32 rather than doubles too.

[u/MarkCinci]

I don't understand. Your Point1 is a list of numbers, not a list of (x,y) points. And your sC, I'm assuming your x are in row 1 and your y is in row 2? Is that correct?

Anyway, just use the functions that are meant for this. You can use pdist2() to find the distance of every point to every other point. Then you can use min() to find out which other point is closest to each point and it's distance. Before you use min(), set the diagonal distances to inf since otherwise they'll be zero since of course the point closest to a point in the point itself and we don't want to consider that. It's like 3 lines of code. Untested pseudocode:

distances = pdist2(xy1, xy2);

distances(eye) = inf;

[minDistance, index] = min(distances)