Effacer les filtres
Effacer les filtres

Sorting of points (2D) clockwise with respect to the center of gravity

30 vues (au cours des 30 derniers jours)
Alberto Acri
Alberto Acri le 24 Déc 2022
Modifié(e) : Karim le 25 Déc 2022
I am using this code. Can anyone tell me how I can improve it to be able to sort the points (matrix coordinates) clockwise with respect to G?
data = readmatrix('data.txt');
G = mean(data,1);
% Convert to polar coordinates
rad = cart2pol(data(:,1), data(:,2));
radWrapped = mod(rad,2*pi);
radWrapped(radWrapped==0 & rad>0) = 2*pi;
[~, sortIdx] = sort(radWrapped, 'descend');
sortedData = data(sortIdx,:);
% Figure
figure
plot(data(:,1), data(:,2),'k.','Markersize',15)
hold on
plot(G(:,1), G(:,2),'k*','Markersize',15)
a = 14;
plot(data(a,1), data(a,2),'r.','Markersize',15) % display point 14
b = 15;
plot(data(b,1), data(b,2),'g.','Markersize',15) % display point 15
c = 16;
plot(data(c,1), data(c,2),'m.','Markersize',15) % display point 16
d = 17;
plot(data(d,1), data(d,2),'y.','Markersize',15) % display point 17
e = 18;
plot(data(e,1), data(e,2),'b.','Markersize',15) % display point 18
hold off
grid off
axis equal
xlabel('x')
ylabel('y')
  2 commentaires
Sulaymon Eshkabilov
Sulaymon Eshkabilov le 24 Déc 2022
can you share your data?
Alberto Acri
Alberto Acri le 24 Déc 2022
yes, sorry I forgot to attach the file

Connectez-vous pour commenter.

Réponse acceptée

Karim
Karim le 24 Déc 2022
Modifié(e) : Karim le 25 Déc 2022
Edit: modified the code after the OP added data...
The sort trick with the angle won't work due to the shape of the curve. Below you can find a bit mory tricky method. We look for the closest point and then march on looping over al the points. See below for some coments and a working example.
% read the data
data = readmatrix('data.txt');
% determine the order of the closest points for each point
idx = knnsearch(data,data,'K',size(data,1));
% create a vector to store the order of the points
order = zeros(size(data,1),1);
% we use point 1 as the starting point
order(1) = 1;
% loop over the other points
for i = 2:size(data,1)
% extract the indexes of the points closest to the current point
% these are ordered by distance vie the knnsearch
currPoints = idx(order(i-1),:);
% keep looking for the closest point we havent used so far
for j = 2:size(data,1)
if all(order(1:(i-1)) ~= currPoints(j))
% we found the next point, store in the order and stop the
% internal loop
order(i) = currPoints(j);
break
end
end
end
% sort the points using the order
data = data(order,:);
% add the first point at the end, to close the curve in the figure
data(end+1,:) = data(1,:);
% make a figure
figure
plot(data(:,1),data(:,2),'LineWidth',1.5)
grid on
title('sorted points')
  4 commentaires
Alberto Acri
Alberto Acri le 25 Déc 2022
Thank you @Karim! Very helpful. Can I just ask you how to connect the first and the last point?
Karim
Karim le 25 Déc 2022
You are welcome, you can add the first point at the end of the array. This will give the appearance of a closed region, i will edit the answer accordingly.

Connectez-vous pour commenter.

Plus de réponses (1)

John D'Errico
John D'Errico le 24 Déc 2022
Modifié(e) : John D'Errico le 24 Déc 2022
I'm confused. Have you already subtracted off the center of gravity from the columns of data? I don't see that operation. If not, then nothing in what you wrote does it, so your code would be incorrect.
Next, what you wriote is this:
rad = cart2pol(data(:,1), data(:,2));
HUH? The first argument returned from cart2pol is not a radius, in fact it is the SECOND argument returned from cart2pol. Ok, I suppose you wanted it to mean RADIANS. Sigh. Good code is self documenting. So the variables should have meaningful names that will not confuse you when you try to read it.
But all you need to do is a mod, and THEN a sort. You did some other fussing around that makes no sense that I can see.
rad = sort(mod(rad,2*pi),'descend');
For example (Sorry, that I refuse to use rad for an angle. It just hurts my brain to do so.)
data = rand(20,2);
G = mean(data,1);
datashifted = data - G;
theta = cart2pol(datashifted(:,1),datashifted(:,2));
[theta,ind] = sort(mod(theta,2*pi),'descend');
plot(data(ind,1),data(ind,2),'-o',data(ind(1),1),data(ind(1),2),'rs')
I've plotted the first point with a red square here, so you can see the points are now sorted in a clockwise order.
  2 commentaires
Alberto Acri
Alberto Acri le 24 Déc 2022
Modifié(e) : Alberto Acri le 24 Déc 2022
Thanks for the reply @John D'Errico! I attached you the "date" file I forgot to attach!
The code works fine however there are some issues related to the curve I attached.
John D'Errico
John D'Errico le 24 Déc 2022
Modifié(e) : John D'Errico le 24 Déc 2022
Your points lie along a "polygon", yet sufficiently non-convex that you cannot use the scheme I suggested. I would instead use a traveling salesman solver, so a scheme that finds the shortest route between successive points along the curve. There are a few of them on the file exchange.

Connectez-vous pour commenter.

Catégories

En savoir plus sur Loops and Conditional Statements dans Help Center et File Exchange

Produits


Version

R2021b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by