Coding algorithm needed for orienting lines of a polygon as counter clockwise

Question

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

Answer 1

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.

Answer 2

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