MATLAB: Find i,j of non-sorted points

MATLABpointssort

Hello everyone !
I'd like to know how to sort points with i,j indexes.
I have a N*2 matrix which hold the x and y coordinates of points. I am looking for an algorithm to assign i and j indexes to each point, so that I can easily find the upper one, for example.
Thanks a lot for your answers !

Best Answer

There are probably faster/better ways, but this code should do. I commented out two figures that are worthwhile at the exploratory stage.
%(replace this with your own code to get the Nx2 array)
IM=imread('image.png');
centroids=regionprops(IM(:,:,1)==255&IM(:,:,2)==0,'Centroid');
centroids=cell2mat(struct2cell(centroids)');
c=centroids;
% %here you can see that each row is clearly distinguisable, but cols are not
% figure(1),clf(1)

% subplot(1,2,1)
% plot(sort(c(:,1)),'.')
% ylabel('x-value'),xlabel('index')
% subplot(1,2,2)
% plot(sort(c(:,2)),'.')
% ylabel('y-value'),xlabel('index')
% %here you can see that it should be easy to separate out the different rows
% cy=sort(c(:,2));
% figure(1),clf(1)
% plot(diff(cy))
% ylabel('\Deltay-value'),xlabel('index')
[cy,idx]=sort(c(:,2));cx=c(idx,1);%could be done with sortrows as well
row_index=zeros(size(cy));
L=diff(cy) > 2*mean(diff(cy));
row_index([true;L(:)])=1;%mark all indices that start a new row with 1
row_index=cumsum(row_index);%this is now contains the row number for each point
num_of_rows=max(row_index);
cell_array=cell(num_of_rows,1);
for n=1:size(cell_array,1)
    matching_idx=row_index==n;
    cell_array{n}=[cx(matching_idx) cy(matching_idx)];
end
len=cellfun('length',cell_array);max_len=max(len);
for n=1:size(cell_array,1)
    if len(n)~=max_len
        %pad with NaN
        cell_array{n}((len(n)+1):max_len,:)=NaN;
    end
    row=cell_array{n};
    [~,order]=sort(row(:,1));row=row(order,:);%sort based on x-value
    cell_array{n}=mat2cell(row,ones(1,max_len),2)';
end
cell_array=reshape([cell_array{:}],max_len,num_of_rows)';
%Shift the rows with missing points, so everything alligns again.
%How to dectect the correct shift automatically is left as an exercise to
%the reader.
for row=12:19
    cell_array(row,:)=cell_array(row,[end 1:(end-1)]);
end
Related Question