1

Please note that I'm a beginner with polygons and spatial representation.

This is what I have:

I'm working on a C# project, and I have list of vertices (defined by a latitude / longitude), representing a closed polygon. The polygon can be convex or concave, and it can't have any "holes". These vertices are adjacent but can be clockwise, or anti-clockwise.

This is what I'd like:

I'd like to know how to determine if this list is clockwise or counter-clockwise, then sort the vertices in order to they were clockwise. I'm able to do the sort algorithm by myself, but I have no idea how to determine it the given list of vertices are CW or CCW.

24
  • 2
    Points are not objectively located clockwisely or counter-clockwisely. Angles (between points) CAN be calculated clockwisely or counter-clockwisely; example, the angle between two points can be 90 or 270; having one or the other value (CW or CCW) depends upon your current calculating system, not upon an immutable reality (it has to be CCW or CCW).
    – user2480047
    Commented Oct 30, 2013 at 15:52
  • 2
    stackoverflow.com/questions/1165647/… Commented Oct 30, 2013 at 15:53
  • @MatthewWatson I am not sure if I have misunderstood the question; but there is no way to tell if two points are CW or CCW. Other thing (what this link seems to be referring) is that you have a set of points, all of them following the same rules for their variations (CW or CCW) and you have to find out which option they belong to.
    – user2480047
    Commented Oct 30, 2013 at 15:56
  • 2
    @varocarbas The OP said he has a list of vertices, not that he only has two vertices. Those vertices define a polygon. You only need a minimum of 3 (i.e. a triangle) to be able to determine if the points are given in clockwise or anticlockwise order. Commented Oct 30, 2013 at 15:57
  • 1
    If you know that the vertices are arranged in CCW order, just reverse the vertex list to make it CW...
    – user2819245
    Commented Oct 30, 2013 at 16:10

1 Answer 1

2

Here's the solution: https://en.wikipedia.org/wiki/Curve_orientation#Orientation_of_a_simple_polygon

Works also for concave polygons, as pointed out in the "practical considerations" section (basically the middle point for the test needs to be the topmost and leftmost point).

7
  • Don't know who voted down, but the given link seems reliable... I'll test and come back Commented Oct 30, 2013 at 16:25
  • A co-worker just implemented it and it seems to work.
    – PMF
    Commented Oct 30, 2013 at 16:26
  • 1
    @user2687153 The downvote is probably related to the fact that a link-only answer is not the highest quality. This answer becomes useless once the linked page gets deleted or changed.
    – Hooked
    Commented Oct 30, 2013 at 16:27
  • @Hooked: In general, I would agree, and therefore I generally also avoid that, but in this case, that's rather improbable. Here's the permanent link to the current version: en.wikipedia.org/w/…
    – PMF
    Commented Oct 30, 2013 at 16:34
  • could you give us your implementation? I'm currently working on a project where I need to get a concave polygon from a set of points which are not sorted
    – GeoGecco
    Commented Jul 17, 2015 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.