1

I am running into another problem. I have an algorithm that implements the winding number algorithm to detect if a point lies within a polygon. This algorithm requires that the edges of the polygon are oriented in a counter clockwise fashion. I am currently doing this by checking if the center of the polygon is to the left of the edge. If not, then the line is fashioned clockwise and the sign of the result of the winding number algorithm is changed.

For most cases, this method works great. However, I am running into a case where the center is outside of the polygon. At this point, my algorithm breaks because some edges are being recorded as counter clockwise when they are in fact clockwise.

I have been looking at some resources to gain some inspiration:

How to determine if a list of polygon points are in clockwise order?

Ordering CONCAVE polygon vertices in (counter)clockwise?

https://math.stackexchange.com/questions/340830/clockwise-or-anticlockwise-edges-in-a-polygon

http://jeffe.cs.illinois.edu/teaching/373/notes/x05-convexhull.pdf

However, these resources deal mainly with convex polygons. I would need to develop a generic algorithm that can handle both convex and concave polygons. Although, if this doesn't exist (or can't be done), then I will settle with creating two separate algorithms and detecting if the polygon is concave/convex.

The ideal algorithm would simply detect if a particular edge is oriented clockwise or counter clockwise for a choosen polygon. but I am open to algorithms that will resort the edges and vertices in a counter clockwise flow for the polygon.

I have been considering an algorithm that not need to use the center point of the polygon as the result will be dependent on whether the center is inside/outside the polygon.

If you have any questions, please feel free to as in the comments and I will answer them as quickly as possible. Thank you!

Edit:

I should note that the orientation of the lines are random. Some will be counter clockwise. Others will be clockwise

philm
  • 797
  • 1
  • 8
  • 29
  • If you know that the edges are either in clockwise or anticlockwise order, and your polygon is simple (ie the edges don't cross) and all you want the winding number for is detecting whether a point is in the polygon or not, then since a point is outside iff the winding number is zero, why do you care about the order? – dmuir Feb 15 '18 at 12:40
  • The order of the lines isn't so much of a big issue. I thought of that if it would make the problem simpler to think about. The main point is that the lines are oriented in a counter clockwise direction. IE, the order of the start and end node is in the direction of the "flow" of the polygon being clockwise/counter clockwise – philm Feb 15 '18 at 20:24

2 Answers2

2

Assuming that you have an unordered list of lines, and each one has a start vertex and an end vertex:

  • Create an empty list for your ordered lines.
  • Choose a line from the unordered list at random, move it from the unordered to the ordered list and make it your current line.
  • While there are lines remaining in the unordered list:
    • Find a line in the unordered list that has a start or end vertex equal to the end vertex of the current line and remove it from the list. Call this the next line.
    • If the start vertex of the next line is equal to the end vertex of the current line, add it to the end of the ordered list as is
    • Else if the end vertex of the next line is equal to the end vertex of the current line, swap the start and end vertices of the next line and add it to the end of the ordered list
    • Make the next line the new current line
  • Once complete, check the ordering of the entire list using the shoelace formula as described in Yves Daoust's answer, if it's negative then swap the start and end vertices of all the lines

You could use a hash table (using the vertex values as keys) to make finding the matching lines faster. If the lines are already in order (but some are around the wrong way) then it's just a matter of checking each line in turn against the previous line and swapping start and end if the start vertex of the current is not equal to the end vertex of the previous.

If you have more than one line sharing a single vertex then this algorithm won't work.

samgak
  • 23,944
  • 4
  • 60
  • 82
  • Great, using your suggestion and Yves answer, I was able to come up with an idea of a prelim algorithm that I would like to test. Not the most ideal since there are a few extra steps but I guess that the algorithm would go faster if there was some sort of order to the lines and then checking if the end node of the current line is equal to the start node of the next line and swapping if not. – philm Feb 14 '18 at 18:23
  • Thanks for your answer! I had been looking and most answers assume you know your winding direction already. My data is bad. This is helping me fix it! – powerc9000 Dec 23 '21 at 20:11
1

It suffices to compute the polygon area using the shoelace formula (without the absolute value). If the area is negative, reverse the order.

  • Hello, thank you for your reply! The shoelace formula, I have not heard this before. I will take a look at it! – philm Feb 12 '18 at 17:34
  • Quick question, how does the algorithm handle the case for the center being outside the polygon and the edge is oriented as clockwise in reference to the polygon? – philm Feb 12 '18 at 18:11
  • @philm: orientation of a polygon has nothing to do with a "center". (In fact, there is not even a definition for *the* center of a polygon.) –  Feb 12 '18 at 20:12
  • For some algorithms that check the orientation of a line, you can compute that area of the triangle that encompasses the 2 nodes of the edge and the center of the polygon. If the result is negative, then the edge is CCW. I have found that if the center is outside the polygon, then this method can indicate that the edge is CW orientation in relation to the polygon but the result indicates that the edge should be CCW (Refer to page 2 of the pdf that I posted in my question). I was wondering if there might be a similiar situation with the method you posted here – philm Feb 12 '18 at 21:38
  • @philm: forget about the "center", it is of no use. –  Feb 12 '18 at 22:05
  • Sure thing. Another question, it looks like the algorithm will determine if the entire polygon is oriented CCW or CW. Unless I am missing something, would this algorithm determine if a particular line is CW/CCW in reference to the polygon? – philm Feb 12 '18 at 22:30
  • @philm: it doesn't make sense to speak of the orientation of individual edges. –  Feb 13 '18 at 07:00
  • I am commenting on the orientation of the individual edges because the winding number algorithm assumes that the edge moves from the first node to the second node in a counter clockwise direction. This direction will be in reference to the counter clockwise direction of the whole polygon. – philm Feb 14 '18 at 17:42
  • @philm: in a polygon, all edges have the same orientation. –  Feb 14 '18 at 18:33