提问人：ivovchoc 提问时间：11/16/2023 最后编辑：ivovchoc 更新时间：11/19/2023 访问量：222
如何顺时针或逆时针对坐标对象数组进行排序？
How to sort an array of coordinate objects clockwise or counterclockwise?
问：
演示：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：
这种按顺时针顺序对点进行排序的解决方案对我没有帮助。
特别是，它不适用于我描述的示例。
答：
0赞
ruakh
11/19/2023
#1
与其把它看作是一个“排序”问题，不如把它看作是一个“找邻居”的问题;对于每个点，我们希望在列表中找到它旁边的点。
一些观察：
- 所有点都是不同的;也就是说，永远不会有两个点具有相同的 X 坐标和相同的 Y 坐标。
- 每个点都有两个相邻点：一个具有相同的 x 坐标，一个具有相同的 y 坐标。
- 对于任何给定的 x 坐标，对于某些 k，将正好有 2个 k 点;同样，对于任何给定的 y 坐标。
- 如果两个点是相邻点，则它们之间的线上没有其他点。更正式地说：如果 （x 1， y） 和 （x 2， y） 是邻居，那么没有 （x 3， y） 和 x 1 < x 3 < x2;（x， y 1） 和 （x， y2） 也是如此。
- 因此，对于任何给定的 x 坐标，具有最小和第二少 y 坐标的点是相邻点，具有第三少和第四少 y 坐标的点是相邻点，依此类推;同样，对于任何给定的 y 坐标。
因此，我们可以按如下方式对列表进行“排序”：
- 首先，找到所有共享 x 坐标的邻居对。为此，请创建一个列表，其中包含按 x 坐标排序的点，并回退到按 y 坐标排序。然后是邻居，是邻居，等等。
sortedByXThenYsortedByXThenY[0]sortedByXThenY[1]sortedByXThenY[2]sortedByXThenY[3] - 接下来，通过执行相同的方法查找共享 y 坐标的所有相邻对象对。
- 选择某个点作为第一个点。选择第一个点的相邻点之一（例如，具有相同 x 坐标的相邻点）作为第二个点。选择第二个点的另一个相邻点（具有相同 y 坐标的相邻点）作为第三个点。继续，直到您选择了所有点。
评论
0赞
ivovchoc
11/19/2023
如果我理解正确的话，我尝试实现此功能。我添加了 rearrangePoints 函数，您可以在 DEMO 中查看它。这适用于简单的形状。但是，例如，如果我从瓷砖创建一个十字形，这是一个 12 边形，那么坐标就不再有序了。
0赞
ruakh
11/19/2023
@ivovchoc：对不起，我不会试图弄清楚你的演示。请在此处的问题中输入所有必要的信息。但是 FWIW，这种方法适用于像 . ➕
0赞
ivovchoc
11/19/2023
在确定形状的所有边缘点后，是否需要添加此功能？
0赞
ruakh
11/19/2023
@ivovchoc：“边缘点”是什么意思？输入应该是顶点列表（其中 n 表示 n 个顶点），输出将是（可能）不同顺序的相同 n 个顶点的列表。
0赞
ivovchoc
11/19/2023
是的，这就是我的意思。我所说的边缘点是指形状的所有角。好的，我会尝试更多地使用这种方法。
评论
{ x: 0, y: 54 }{ x: 108, y: 108 }{ x: 54, y: 54 }