Sorting 2D points clockwise

Question

I found a way to sort clockwise 2D points in Unity, but for some reason that i don't understand there are sometimes points still in the wrong order.

On the first picture the red sphere is the center and the other spheres are colored by order.

The second picture shown the position of those spheres with wrong order.

  private static Vector2[] SortClockwise(List<Vector2> vertices)
  {
      // calculate center
      Vector2 center = Vector2.zero;
      for (int i = 0; i < vertices.Count; i++)
      {
          center += vertices[i];
      }
      center /= vertices.Count;

      // order by the angle to center
      return vertices.OrderBy(point => Math.Atan2(point.x - center.x, point.y - center.y)).ToArray();
  }

Edit:

Top left corner (red: current index, blue lines: expectation)

I understand the concave problem now and from my understanding i can assume that all convex polygons are in the right order but concave will be false?

If i take picture 2 for example and check for concave polygons and swap position if it is concave (depending i know which positions to swap)? or will there be more problems for more complex forms?

Answer 1

The solution i found is:

• create convex hull
• for every missing vertex find the smallest angle for each line on the concave hull
• add that vertex to the concave hull with index between the two other points of the found

For efficiency it is possible to find K-Nearest Neighbor before checking the angles for each line on the concave hull. For me i didn't implemented it because in some cases the nearest neighbor are missing the right one if its far away.

C# Code:

 public static List<Vector2> ConcaveHull(List<Vector2> vertices)
 {
     List<Vector2> result = new List<Vector2>(GetConvexHull(vertices));
     List<Vector2> missingVertices = new List<Vector2>(vertices);

     //remove dupes
     missingVertices = missingVertices.Distinct().ToList();
     foreach (Vector2 v in result)
     {
         missingVertices.RemoveAll(x => x == v);
     }

     //find widest angle for 
     for (int i = 0; i < missingVertices.Count; i++)
     {
         //get widest angle
         int index = GetSmallestAngle(missingVertices[i], result);
         //insert on position index + 1 because it is middle position
         result.Insert((index + 1) % result.Count, missingVertices[i]);
     }

     return result;
 }

  private static int GetSmallestAngle(Vector2 checkingVertex, List<Vector2> vertices)
  {
      Dictionary<int, float> distance = new Dictionary<int, float>();

      //set every cos
      for (int i = 0; i < vertices.Count; i++)
      {
          distance.Add(i, GetCos(vertices[i], vertices[(i + 1) % vertices.Count], checkingVertex));
      }

      return distance.OrderBy(x => x.Value).FirstOrDefault().Key;
  }

  private static float GetCos(Vector2 a, Vector2 b, Vector2 c)
  {
      /* Law of cosines */
      float aPow2 = Mathf.Pow(a.x - c.x, 2) + Mathf.Pow(a.y - c.y, 2);
      float bPow2 = Mathf.Pow(b.x - c.x, 2) + Mathf.Pow(b.y - c.y, 2);
      float cPow2 = Mathf.Pow(a.x - b.x, 2) + Mathf.Pow(a.y - b.y, 2);
      float cos = (aPow2 + bPow2 - cPow2) / (2 * Mathf.Sqrt(aPow2 * bPow2));
      return (float)System.Math.Round(cos, 4);
  }

Source reference:

Convex Hull

Implementation of a fast and efficient concave hull algorithm