如何对坐标对象数组进行顺时针或逆时针排序？

Question

演示：https://codesandbox.io/s/new-bird-rx8zxd

---

我有一个坐标对象数组，我需要实现一种排序机制，将它们按顺时针或逆时针方向排列。起点可以是任意的。在此示例中，图块大小为 54。相邻顶点具有相同的坐标。

这个数组：

    [
      { x: 0, y: 108 },
      { x: 0, y: 54 },
      { x: 108, y: 108 },
      { x: 54, y: 54 },
      { x: 108, y: 0 },
      { x: 54, y: 0 }
    ]

应该分类为：

    [
      { x: 54, y: 0 },
      { x: 108, y: 0 },
      { x: 108, y: 108 },
      { x: 0, y: 108 },
      { x: 0, y: 54 },
      { x: 54, y: 54 }      
    ]

示例1：

示例2：

这个解决方案到按顺时针顺序排序点对我没有帮助。
特别是，它不适用于我描述的示例。

Answer 1

不要将其视为“排序”问题，而是将其视为“寻找邻居”问题；我们想要找到列表中每个点旁边的点。

一些观察：

• 所有点都是不同的；也就是说，永远不存在具有相同 x 坐标和相同 y 坐标的两个点。
• 每个点都有两个邻居：一个具有相同的 x 坐标，一个具有相同的 y 坐标。
• 对于任何给定的 x 坐标，对于某些 k 来说，正好有 2k 点；对于任何给定的 y 坐标也是如此。
• 如果两个点是邻居，那么它们之间的直线上没有其他点。更正式地说：如果 (x₁, y) 和 (x₂, y) 是邻居，则不存在 (x₃, y) 与 x ₁ < x₃ < x₂；同样对于 (x, y₁) 和 (x, y₂)。
• 因此，对于任何给定的 x 坐标，具有最小和第二小的 y 坐标的点是邻居，具有第三最小和第四最小 y 坐标的点是邻居，等等。 ;对于任何给定的 y 坐标也是如此。

因此，我们可以按如下方式对列表进行“排序”：

1. 首先，找到共享 x 坐标的所有邻居对。为此，请创建一个列表

   sortedByXThenY

   ，其中包含按 x 坐标排序的点，并回退到按 y 坐标排序。那么

   sortedByXThenY[0]

   和

   sortedByXThenY[1]

   是邻居，

   sortedByXThenY[2]

   和

   sortedByXThenY[3]

   是邻居，等等
2. 接下来，通过相同的方法找到共享 y 坐标的所有邻居对。
3. 选择某个点作为第一个点。选择第一个点的邻居之一（例如，具有相同 x 坐标的点）作为第二个点。选择第二个点的另一个邻居（具有相同 y 坐标的点）作为第三个点。继续，直到您选择了所有点。