Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
sort 2D points in counter- clockwise way

Subject: sort 2D points in counter- clockwise way

From: Ahmad

Date: 27 Jul, 2008 06:35:03

Message: 1 of 7

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

Subject: sort 2D points in counter- clockwise way

From: Bruno Luong

Date: 27 Jul, 2008 07:31:02

Message: 2 of 7

"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

Subject: sort 2D points in counter- clockwise way

From: Bruno Luong

Date: 27 Jul, 2008 07:44:02

Message: 3 of 7


> 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

Subject: sort 2D points in counter- clockwise way

From: Matt

Date: 27 Jul, 2008 16:43:05

Message: 4 of 7

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

Subject: sort 2D points in counter- clockwise way

From: Z

Date: 26 Jun, 2009 22:22:01

Message: 5 of 7

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

Subject: sort 2D points in counter- clockwise way

From: Bogdan Dzyubak

Date: 26 Jan, 2012 17:02:10

Message: 6 of 7

Thanks, Z. Simple and elegant.

Subject: sort 2D points in counter- clockwise way

From: MrWong

Date: 7 Mar, 2013 07:51:07

Message: 7 of 7

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

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us