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.

Hooked
  • 84,485
  • 43
  • 192
  • 261
user2687153
  • 427
  • 5
  • 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). – varocarbas Oct 30 '13 at 15:52
  • 2
    http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order – Matthew Watson Oct 30 '13 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. – varocarbas Oct 30 '13 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. – Matthew Watson Oct 30 '13 at 15:57
  • @MatthewWatson as said, perhaps I misunderstood the question; but from this sentence "These vertices are adjacent but can be clockwise, or anti-clockwiwe", I understood that he was looking for 1-against-1 comparison to check if the are CW or CCW. But I guess that your interpretation (and the link your provided) makes much more sense :) – varocarbas Oct 30 '13 at 16:00
  • @MatthewWatson sorry to correct you but I can give you 3 points (or 4 or 5), and the corresponding variations might be calculated CW or CCW (e.g., leftwards or rightwards) – varocarbas Oct 30 '13 at 16:01
  • Hi guys, thank you for your answers. To clarify my question, yes I have 3 or more points defined by latitude / longitude, but the polygon can be drawn clockwise or counter-clockwise ; and I need to transform (if necessary) the list of vertices so that to have a list with vertices sorted clockwise. Can the link given by Matthew answer my problem ? I think yes but I'm not 100% sure ? – user2687153 Oct 30 '13 at 16:04
  • If you already have a spatial representation/organisation of the vertices, look up the two upper-most (or left-/right-/bottom-most) vertices - if your polygon is closed and not self-intersecting, those two verices will always be on a 'convex' segment of your polygon (if not, they would not be top-most). Compare the relative postition of those two vertices, and you will know if your polygon is CW or CCW. This approach does not work, if you have to deal with self-intersecting polys, though... –  Oct 30 '13 at 16:05
  • elgonzo : My polygon is closed, but it can be self-intersecting, so I guess your method doesn't work ? – user2687153 Oct 30 '13 at 16:10
  • 1
    If you know that the vertices are arranged in CCW order, just reverse the vertex list to make it CW... –  Oct 30 '13 at 16:10
  • @User, if your polys can be self-interesecting, then unfortunately the approach i suggested does not work reliably. –  Oct 30 '13 at 16:11
  • elgonzo : Anyway, my list of vertices is clockwise OR counter-clockwise, I just need a reliable method to determine if they are CW or CCW – user2687153 Oct 30 '13 at 16:14
  • @User, actually, if you deal with self-intersecting polys, parts of the polygon can be CW, while other parts can be CCW. How would you deal with that? –  Oct 30 '13 at 16:15
  • @User: An example: Take an ellipsoid (like a rubber band) and twist it so that it creates a "figure of 8". One side is now in CW order, whereas the other side is in CCW order. In such and similar cases it is not possible to sort the whole complete vertex list either in CW/CCW order without destroying the polygon. –  Oct 30 '13 at 16:16
  • You're right, for self-intersecting polygon, I will face a problem... Hmm.. Let's say it is not self-intersecting, I'll keep this intersection problem for later. Are the link given by Matthew and PMF ok ? I think yes but I need your advice. – user2687153 Oct 30 '13 at 16:21
  • If the vertices are on a great circle, then they are either CW or CCW, depending on where you look at them from. Or are your vertices defined by latitudes and longitudes all within less than a hemisphere? – Andrew Morton Oct 30 '13 at 16:21
  • @User: I have not looked at the other suggested approaches, but i assume they will work. (Otherwise somebody would already have complained, i guess ;) ) Basically, choose the approach that promises fastest execution depending on how you organize and store the vertices, or is the easiest to understand for you. –  Oct 30 '13 at 16:23
  • Ok, I'll do some test and come back. Thank you very much :-) – user2687153 Oct 30 '13 at 16:25
  • @varocarbas: I think you confused something. An arrangement of vertices forming a non-intersecting polygon can be either CCW or CW (or nothing of them if they share identical coordinates). Whether it is CCW or CW entirely depends on the conventions of the used coordinate system (left-hand rule, right-hand rule, or something like that), not necessarily on how you calculate things. But perhaps, that is what you actually meant to say... :) –  Oct 30 '13 at 16:32
  • @elgonzo As said above, the orientation (CW or CCW) is not one of the defining features of a point (and thus there is no absolute CW/CCW definition). You can bring angles into account while defining the given point with respect to the given system of reference (although this is not required). Some of the angle-based definitions of a point (but, again, not all), bring some rules into account (right-hand one you mention) where the orientation taken into consideration might be relevant; even in this case (a sub-method, within a method, etc.) you have to bring various points... – varocarbas Oct 30 '13 at 16:48
  • @elgonzo ... into account in order to deliver definitive results on account of the orientations. But all this, by bearing in mind the reality: angles/orientations are just a convention for the definition of points (nothing absolutely defining the points), you would have to explain the exact convention you are referring to and make sure that the minimum requirements are fulfiled (e.g., if you have 3 or 4 or even more... points in a 3D space without any further constraint, even by applying a clearly defined rule (right-hand one), there might not be an undoubted answer). So... – varocarbas Oct 30 '13 at 16:52
  • @elgonzo the whole point of my comment was: don't think that CW/CCW has an absolute/objective meaning when coming to defining points, because it does not have it. Define your exact conditions, expectations, etc. and we might be able to help you out a bit. This is what I meant :) – varocarbas Oct 30 '13 at 16:54
  • @MatthewWatson I finally use your link, using Sean the Bean's answer. You can post it as an answer if you want I accept it. Thanks everyone for your help, I really appreciate it :-) – user2687153 Nov 02 '13 at 22:50
  • @user2687153 Me just giving a link isn't worthy of a correct answer - just upvote Sean's answer. :) – Matthew Watson Nov 04 '13 at 09:23

1 Answers1

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

PMF
  • 14,535
  • 3
  • 23
  • 49
  • Don't know who voted down, but the given link seems reliable... I'll test and come back – user2687153 Oct 30 '13 at 16:25
  • A co-worker just implemented it and it seems to work. – PMF Oct 30 '13 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 Oct 30 '13 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: https://en.wikipedia.org/w/index.php?title=Curve_orientation&oldid=571714181 – PMF Oct 30 '13 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 Jul 17 '15 at 10:38
  • @GeoGecco: That is a different problem. I have code that tells you whether a given polygon is in clockwise or counterclockwise direction. Getting a concave polygon from a random set of points is not defined, because there are many solutions. You might want to get the convex hull of a set of points, or compute a polygon so that no lines cross each other or... – PMF Jul 17 '15 at 11:57
  • thank you for the fast answer. I already found half a solution which I posted here: http://stackoverflow.com/questions/31429874/ – GeoGecco Jul 17 '15 at 12:07