Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

CCW or CW ordering of the points of a generic polygon

  1. Feb 23, 2016 #1
    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?
     

    Attached Files:

  2. jcsd
  3. Feb 23, 2016 #2

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    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.
     
  4. Feb 23, 2016 #3

    phyzguy

    User Avatar
    Science Advisor

    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.
     
  5. Feb 23, 2016 #4

    Svein

    User Avatar
    Science Advisor

    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.
     
  6. Feb 23, 2016 #5

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: CCW or CW ordering of the points of a generic polygon
  1. Order of operations (Replies: 8)

Loading...