Thread Subject:

sort 2D points in counter- clockwise way

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

"Ahmad " <ahmad.humyn@gmail.com> wrote in message
<g6h4un$rs6$1@fred.mathworks.com>...
> 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

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

> 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

> 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.

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.humyn@gmail.com> wrote in message <g6h4un$rs6$1@fred.mathworks.com>...
> 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

Thanks, Z. Simple and elegant.

"Bogdan Dzyubak" <illan7@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.