4

What I want to do is to sort these coordinates points:

Measured coordinates (x,y)= (2,2),(2,3),(1,2),(1,3),(2,1),(1,1),(3,2),(3,3),(3 ,1)

I need to get sequences or trajectories of this points to follow them by iteration.

user1310873
  • 389
  • 1
  • 6
  • 17
  • 3
    sort them with respect to what? x or y? – mathematician1975 Jul 24 '12 at 13:32
  • Well actually I have coordinate points of a function, but in disorder way, how to sort this points to make sequences(near-neighbour)? I mean, if I want to draw every coordinate point in order way, I need to start from the first point and continue with the nearest point. – user1310873 Jul 24 '12 at 13:41
  • Well this will be tricky. For a start many of your points are equidistant (eg (2,3) and (2,1) are same distance away from (2,2)) also you will need to define a start point. I dont think matlab has anything inbuilt for this - you will need to do it the hard way and decide how to deal with equidistant points – mathematician1975 Jul 24 '12 at 13:46

2 Answers2

6
data = [2,2 ; 2,3 ; 1,2 ; 1,3 ; 2,1 ; 1,1 ; 3,2 ; 3,3 ; 3 ,1]
% corresponding sort-value, pick one out or make one up yourself:
sortval = data(:,1); % the x-value
sortval = data(:,2); % y-value
sortval = (data(:,1)-x0).^2 + (data(:,2)-y0).^2; % distance form point (xo,y0)
sortval = ...

[~,sortorder] = sort(sortval);
sorted_data = data(sortorder,:);

But from you comment, I understand you actually need something to reconstruct a path and iteratively find the closest neighbour of the last found point (of the reconstructed path so far).

The following is how I would solve this problem (using pdist2 for calculating the distances between all the points for easiness):

data = [2,2 ; 2,3 ; 1,2 ; 1,3 ; 2,1 ; 1,1 ; 3,2 ; 3,3 ; 3 ,1];
dist = pdist2(data,data);

N = size(data,1);
result = NaN(1,N);
result(1) = 1; % first point is first row in data matrix

for ii=2:N
    dist(:,result(ii-1)) = Inf;
    [~, closest_idx] = min(dist(result(ii-1),:));
    result(ii) = closest_idx;
end

which results in:

result =
     1     2     4     3     6     5     9     7     8

being the indices to consecutive points on the curve. Here's a plot of this result:

enter image description here

As @mathematician1975 already mentioned, there can be equal distances to a point. This is solved here by using min which just finds the first occurrence of the minimum in an array. This means that if you order your input data differently, you can get different results of course, this is inherent to the equal-distance issue.

2nd remark: I don't know how this will behave when using large input data matrices, probably a bit slow because of the loop, which you can't avoid. I still see room for improvement, but that's up to you ;)

Gunther Struyf
  • 11,158
  • 2
  • 34
  • 58
3

Create a matrix from your points so that you have something like

  A = [2 2 1 1 2 1 3 3 3;
       2 3 2 3 1 1 2 3 1]';

then try

 B = sortrows(A,1);

to get a matrix with rows that are your points ordered by xvalue or 

 B = sortrows(A,2)

to get a matrix with rows that are your points ordered by their 'y' value. If your points are ordered with respect to some other ordering parameter (such as time) then sorting will not work unless you remember the order that they were created in.

mathematician1975
  • 21,161
  • 6
  • 59
  • 101