顺时针排序 2D 点

Question

我找到了一种在 Unity 中对 2D 点顺时针排序的方法，但由于某种我不明白的原因，有时有些点的顺序仍然错误。

在第一张图片中，红色球体是中心，其他球体按顺序着色。

第二张图显示了那些顺序错误的球体的位置。

  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();
  }

编辑：

左上角（红色：当前指数，蓝线：期望）

我现在理解了凹问题，根据我的理解，我可以假设所有凸多边形都处于正确的顺序，但凹多边形将是错误的？

如果我以图 2 为例，检查凹多边形并交换位置（如果它是凹多边形）（取决于我知道要交换哪些位置）？或者更复杂的形式会出现更多问题吗？

Answer 1

我找到的解决方案是：

• 创建凸包
• 对于每个缺失的顶点，找到凹壳上每条线的最小角度
• 将该顶点添加到凹壳中，索引位于找到的其他两个点之间

为了提高效率，可以在检查凹壳上每条线的角度之前找到 K 最近邻。对我来说，我没有实现它，因为在某些情况下，最近的邻居如果距离很远，就会丢失正确的邻居。

C# 代码：

 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);
  }

来源参考：

凸包

快速高效的凹壳算法的实现