sort 2D points in counter- clockwise way

[Ahmad]

Is there a quick way to order points in a counter-clockwise
fashion. i.e. if we have these set of points in 2D space:
[4 1]
[1 4]
[4 4]
[1 1]

we need to organize them in a counter-clockwise fashion:
[1 1]
[1 4]
[4 4]
[4 1]

Oh....and the polygon is not necessarily regular

[Bruno Luong]

"Ahmad " <ahmad...@gmail.com> wrote in message
<g6h4un$rs6$1...@fred.mathworks.com>...

Is it convex? If yes you might take the convexhull (qhull)
to order them and take the algebra area to see how they are
oriented.

Bruno

Bruno

[Bruno Luong]

> Is it convex? If yes you might take the convexhull (qhull)
> to order them and take the algebra area to see how they are
> oriented.
>
> Bruno
>

Another idea that might or might not work depending on the
shape of your polygons is to remove the barycenter of all
vertexes and take the polar-angle (use function atan2, or
transform to complex and use function angle), and sort the
vertexes with respect to angle.

Bruno

[Matt]

> Oh....and the polygon is not necessarily regular

If the polygon is not convex, the problem is very ill-
defined, which leads me to think you might want to add
specifics to the problem before this discussion continues.

For example, suppose you have 5 points consisting of the
vertices of a square, plus it's center.

[0 0]
[1 0]
[1 1]
[0 1]
[0.5 0.5]

Notice that I've ordered the square's vertices counter-
clockwise. However, I can now insert [0.5 0.5] anywhere in
the list and still get an counter-clockwise ordering.

Why? because I can build a non-convex polyhedron by
connecting any two adjacent corners of the square to the
center.

[Z]

If you only want them to be counter-clock wise, why not convert the [x,y] point to polar coordinate and sort them by angle?

"Ahmad " <ahmad...@gmail.com> wrote in message <g6h4un$rs6$1...@fred.mathworks.com>...

[Bogdan Dzyubak]

Thanks, Z. Simple and elegant.

[MrWong]

"Bogdan Dzyubak" <ill...@gmail.com> wrote in message <jfs0ui$s62$1...@newscl01ah.mathworks.com>...

> Thanks, Z. Simple and elegant.

Hi,

great idea but didn't work for my data. Found a work-around using pdist2

dist = pdist2(data,data);
N = size(data,1);
result = NaN(1,N);
% first point is first row in data matrix
result(1) = 1;
for ii=2:N
dist(:,result(ii-1)) = Inf;
[~, closest_idx] = min(dist(result(ii-1),:));
result(ii) = closest_idx;
end
data=data(result,:);

"data" should be a nx2 vector containing x,y values.

[Pepe Mandioca]

Wong, this is a great idea, but it fails on ocassion when you have a bifurcation in your contour, generally because of some noise in its estimation.

To solve this, you can add a max_distance parameter to the algorithm, so whenever the minimum distance from the current point to other is above that threshold, you stop the algorithm.

The modified code is:

function [poligon,indices]=poligon_from_set_of_points(points,max_distance)
%
% Note that a subset of the points may be selected if the distance between
% two points exceeds max_distance

dist = pdist2(points,points);

N = size(points,1);
indices = NaN(1,N);
indices(1) = 1; % first point is first row in x matrix

for i=2:N
dist(:,indices(i-1)) = Inf;
[distance, closest_idx] = min(dist(indices(i-1),:));
if (distance<max_distance)
indices(i) = closest_idx;
else
indices(i:end)=[];
break;
end
end

poligon=points(indices,:);

"MrWong" wrote in message <kh9gtb$lao$1...@newscl01ah.mathworks.com>...