How to order a set of unordered points

I have a set of unordered points,would appreciate it if some advice can be given on how to reorder them,so that when you draw a line plot the result is continous

Basically,i would like to apply the idea behind RRT.

In RRT,we randomly choose a point,and then find its closest neighbour.We then connect the start point to that neighbour and do tha till we reach the goal.

Given the below img,do you think that idea will work here.

Side note: I have already computed the nearest neigbours for all the points using this,and would appreciate it if we can combine my approach with the one I am talking about in this post.

For ref encosed is the unordered point image as well as the points file

https://in.mathworks.com/matlabcentral/answers/482865-finding-the-10-nearest-points-to-every-point-with-corresponding-distances-within-a-single-variable

Answer 1

[Wan Ji]

Use boundary(x,y) function

load('pts.mat');
x=X_pts(:,1);
y = X_pts(:,2);
k = boundary(x,y,1);
plot(x(k),y(k))
 set(gca,'YDir','reverse')

[Wan Ji]

And you may do by following code (not so stable):

load('pts.mat');
X_pts = unique(X_pts,'rows');
x=X_pts(:,1);
y = X_pts(:,2);
p0 = 2;%randi([1,numel(x)],1,1);
flag = false(size(x));
flag(p0) = true;
ct = 1;
marker = zeros(size(x));
marker(1) = p0;
while (~all(flag))
    dis = max(abs(x(p0) - x) , abs(y(p0)-y));
    [i, idx] = sort(dis);
    for j = 1:1:numel(idx)
        if(~flag(idx(j)))
            ct = ct+1;
            marker(ct)=idx(j);
            p0 = idx(j);
            flag(idx(j)) = true;
            break;
        end
    end
end
marker = [marker;marker(1)];
plot(x(marker),y(marker))
set(gca,'YDir','reverse')

[sparsh garg]

thanks wang i tried boundary it doesn't work for all images

I found this method and it gives some ok results but it has bugs in it ,as it leads to lot of unnecesary lines and orphaned points

https://in.mathworks.com/matlabcentral/fileexchange/35488-connect-randomly-ordered-2d-points-into-a-minimal-nearest-neighbor-closed-contour

[Wan Ji]

I have got a more stable one, but I need more time to consider this problem

load('pts.mat');
X_pts = unique(X_pts,'rows');
x=X_pts(:,1);
y = X_pts(:,2);
p0 = randi([1,numel(x)],1,1);
flag = false(size(x));
flag(p0) = true;
ct = 1;
marker = zeros(size(x));
marker(1) = p0;
dissum = 0;
while (~all(flag))
    dis = max(abs(x(p0) - x) , abs(y(p0)-y));
    [i, idx] = sort(dis);
    for j = 1:1:numel(idx)
        if(~flag(idx(j)))
            ct = ct+1;
            if(ct>2 && dis(idx(j))>10*ave)
                ct = ct-1;
                 flag(idx(j)) = true; 
                 break;
            end
            dissum = dissum + dis(idx(j));
            ave = dissum/ct;
            marker(ct)=idx(j);
            p0 = idx(j);
            flag(idx(j)) = true;
            break;
        end
    end
end
marker = marker(1:ct);
marker = [marker;marker(1)];
plot(x(marker),y(marker))
set(gca,'YDir','reverse')

[sparsh garg]

sure that's ok.

Do you think the idea in the rapid random exploring paper where they connect vertices might work on this problem

[Wan Ji]

I think if you have many 'rings' of points, the first thing is to considering a clustering algrithm to partition them into every single ring.

[Wan Ji]

I have got some answer from others

See the attached files @sparsh garg

[sparsh garg]

Hey wan just wanted to thank you once more for taking the time out to help me.Really learned a lot from you.