如何确定二维空间数据中点的方向并按顺时针方式排列[for corner cases]？
How to determine orientation of points in 2D spatial data and arrange in clockwise manner [for corner cases]?
基本上我有空间数据，我在其中遍历每个点并找出某个半径的圆内的周围点是什么。然后我想按顺时针方向排列这些点，我设法在“大多数”情况下做到了这一点。这个数据的独特之处在于，只有 6 个最大可能位置可以围绕我定义圆半径的任何中心点[top-left, top-right, right, bottom-right, bottom-left, left]
所以作为样本数据
Center Point: 161.3861 368.8119
col row
1 164.5365 363.4114
2 155.2205 368.7669
3 167.5968 368.8569
4 158.2358 374.1674
5 164.4465 374.2124
6 158.3258 363.3663
函数会输出[4, 5 ,3, 1, 6, 2]，这是顺时针顺序。数据的这个子样本 [以红色突出显示，中心保持黑色] 看起来像这样。 [需要说明的是，我有这个案例]
但您可以想象，对于各种极端情况，它并不完全简单。例如下面的例子，它没有指向它右边的点，所以在最终输出数组中，我之前描述的数组的“右，右上，左上”索引应该有一个零。
我正在苦苦挣扎的是一种系统的方法来检查极端情况并为缺失点分配标签。我尝试使用点积方法来量化点之间的距离（使用直线向上的法向量），但这会导致区分右上角的问题。我想象检查一条线是否穿过该点，我们可以了解该点存在于哪个轴上，但我还没有设法让它工作。总结两个主要的极端情况是
- 边缘点数
- 岛屿点数
你可以写一个函数来告诉你一个点在哪个方向，给定点和 center-point:
Pseudo-code:
direction_vector = point - center_point
angle = atan2(direction_vector.y, direction_vector.x)
direction_index = ((angle * 12 / TWO_TIMES_PI) + 12) % 12
这将为您提供一个从 0 到 11 的索引（想象一下奇异钟面上的小时数从 0 开始 anti-clockwise，右边是 0，而正常时钟的 3 点钟位置）。
现在将其映射到您的路线上，1 代表 top-left，2 代表 top-right，3 代表正确等等：
direction_index = (((16 - x) // 2) % 6) + 1
其中 // 是整数除法，% 是模数。
现在您有了方向，从 1 迭代到 6 并输出具有相应方向索引的点的数组索引，如果没有则输出 0（假设基于 1 的数组索引）。
如何添加虚拟点以便每个点都有六个邻居？然后，当您按所需顺序枚举邻居时，您只需跳过虚拟邻居即可。
根据数据结构的组织方式，您可以真正将点添加到点集中，或者在处理给定点时“虚拟”添加它们。
您的点排列在六边形网格中。当你考虑直接邻居时，你可以通过将中心坐标与三条直线进行比较，以绝对方式轻松地将它们分类。
然后按索引排序。
基本上我有空间数据，我在其中遍历每个点并找出某个半径的圆内的周围点是什么。然后我想按顺时针方向排列这些点，我设法在“大多数”情况下做到了这一点。这个数据的独特之处在于，只有 6 个最大可能位置可以围绕我定义圆半径的任何中心点[top-left, top-right, right, bottom-right, bottom-left, left]
所以作为样本数据
Center Point: 161.3861 368.8119
col row
1 164.5365 363.4114
2 155.2205 368.7669
3 167.5968 368.8569
4 158.2358 374.1674
5 164.4465 374.2124
6 158.3258 363.3663
函数会输出[4, 5 ,3, 1, 6, 2]，这是顺时针顺序。数据的这个子样本 [以红色突出显示，中心保持黑色] 看起来像这样。 [需要说明的是，我有这个案例]
但您可以想象，对于各种极端情况，它并不完全简单。例如下面的例子，它没有指向它右边的点，所以在最终输出数组中，我之前描述的数组的“右，右上，左上”索引应该有一个零。
我正在苦苦挣扎的是一种系统的方法来检查极端情况并为缺失点分配标签。我尝试使用点积方法来量化点之间的距离（使用直线向上的法向量），但这会导致区分右上角的问题。我想象检查一条线是否穿过该点，我们可以了解该点存在于哪个轴上，但我还没有设法让它工作。总结两个主要的极端情况是
- 边缘点数
- 岛屿点数
你可以写一个函数来告诉你一个点在哪个方向，给定点和 center-point:
Pseudo-code:
direction_vector = point - center_point
angle = atan2(direction_vector.y, direction_vector.x)
direction_index = ((angle * 12 / TWO_TIMES_PI) + 12) % 12
这将为您提供一个从 0 到 11 的索引（想象一下奇异钟面上的小时数从 0 开始 anti-clockwise，右边是 0，而正常时钟的 3 点钟位置）。
现在将其映射到您的路线上，1 代表 top-left，2 代表 top-right，3 代表正确等等：
direction_index = (((16 - x) // 2) % 6) + 1
其中 // 是整数除法，% 是模数。
现在您有了方向，从 1 迭代到 6 并输出具有相应方向索引的点的数组索引，如果没有则输出 0（假设基于 1 的数组索引）。
如何添加虚拟点以便每个点都有六个邻居？然后，当您按所需顺序枚举邻居时，您只需跳过虚拟邻居即可。
根据数据结构的组织方式，您可以真正将点添加到点集中，或者在处理给定点时“虚拟”添加它们。
您的点排列在六边形网格中。当你考虑直接邻居时，你可以通过将中心坐标与三条直线进行比较，以绝对方式轻松地将它们分类。
然后按索引排序。