CCW or CW ordering of the points of a generic polygon

[Estanho]

Hi,
Suppose I have a data structure that models a polygon, by storing all the nodes of the given polygon, and their connections (i.e. edges).
I understand that sorting a set of nodes that may form a concave hull is ill-defined, as there could be many polygons that can be formed with those. But I'm asking about the case where the polygon is already defined by the edges. I'm attaching a drawing of such a polygon.
Is there an efficient and generic way to order the nodes of any such polygon, which may be concave, in ccw or cw?

 

[SteamKing]

Hi,
Suppose I have a data structure that models a polygon, by storing all the nodes of the given polygon, and their connections (i.e. edges).
I understand that sorting a set of nodes that may form a concave hull is ill-defined, as there could be many polygons that can be formed with those. But I'm asking about the case where the polygon is already defined by the edges. I'm attaching a drawing of such a polygon.
Is there an efficient and generic way to order the nodes of any such polygon, which may be concave, in ccw or cw?

It depends on what you want to do with these points after they're ordered.

If the points are ordered CCW with respect to the origin, it becomes much easier to calculate the area of the closed polygon, for instance.

 

[phyzguy]

The algorithm I use is the following:
(1) Find the centroid of the polygon - just the arithmetic mean of the points.
(2) Calculate the angle from the centroid to each point. I use the c++ atan2 function: angle = atan2(pointlist->y - cy, pointlist->x - cx).
(3) Order the points in increasing order by angle.

This works if the polygon is not too pathological, although it will probably fail if the centroid is outside the polygon.

 

[Svein]

The algorithm I use is the following:
(1) Find the centroid of the polygon - just the arithmetic mean of the points.
(2) Calculate the angle from the centroid to each point. I use the c++ atan2 function: angle = atan2(pointlist->y - cy, pointlist->x - cx).
(3) Order the points in increasing order by angle.

This works if the polygon is not too pathological, although it will probably fail if the centroid is outside the polygon.

You have stumbled upon the concept of winding numbers - an important concept in complex analysis. It is explained in Ahlfors (https://editorialdinosaurio.files.wordpress.com/2012/03/ahlfors_-_complex_analysis.pdf) page 114 ff.

 

[SteamKing]

The algorithm I use is the following:
(1) Find the centroid of the polygon - just the arithmetic mean of the points.
(2) Calculate the angle from the centroid to each point. I use the c++ atan2 function: angle = atan2(pointlist->y - cy, pointlist->x - cx).
(3) Order the points in increasing order by angle.

This works if the polygon is not too pathological, although it will probably fail if the centroid is outside the polygon.

The centroid location for a triangle is the arithmetic mean of the coordinates of the vertices, but I don't think this can be extended to a general polygon where n > 3.

This article contains formulas for calculating the area and the location of the centroid of a closed polygon of an arbitrary number of sides, n ≥ 3:

https://en.wikipedia.org/wiki/Polygon

The article doesn't mention that the centroid location in general is the arithmetic mean of the vertex coordinates.

These formulas and more can be derived by applying Green's Theorem in the plane to the integrals which define the area and first moment of area of a polygonal region. By careful description of the region under consideration, polygons with "holes" or similar non-convex regions can be evaluated, so long as there are no overlapping sides to the region.