想象一下，我有一个有序的点列表，围绕一个中心点排列。
我有一个新点，我想将其包含在列表中，但保持围绕中心点的顺时针顺序。
最明显的解决方案是找到中心和新点之间的角度，遍历列表，计算每个点和中心之间的角度以找到插入点，但我相信有一种更好的方法不需要使用三角函数(Math.atan2)。
我遇到了一种有用的排序算法，它设法使用交叉乘积对中心点周围的点数组进行完美排序，但我不知道如何为我的问题重新设计：
public class Vector2ClockwiseComparer : IComparer<Vector2>
{
public Vector2 center;
public Vector2ClockwiseComparer(Vector2 center)
{
this.center = center;
}
public int Compare(Vector2 v0, Vector2 v1)
{
if (v0.x - center.x >= 0 && v1.x - center.x < 0)
return 1;
if (v0.x - center.x < 0 && v1.x - center.x >= 0)
return -1;
if (v0.x - center.x == 0 && v1.x - center.x == 0) {
if (v0.y - center.y >= 0 || v1.y - center.y >= 0)
if (v0.y > v1.y)
return 1;
else return -1;
if (v1.y > v0.y)
return 1;
else return -1;
}
// compute the cross product of vectors (CenterPoint -> a) x (CenterPoint -> b)
var det = (v0.x - center.x) * (v1.y - center.y) -
(v1.x - center.x) * (v0.y - center.y);
if (det < 0)
return 1;
if (det > 0)
return -1;
// points a and b are on the same line from the CenterPoint
// check which point is closer to the CenterPoint
var d1 = (v0.x - center.x) * (v0.x - center.x) +
(v0.y - center.y) * (v0.y - center.y);
var d2 = (v1.x - center.x) * (v1.x - center.x) +
(v1.y - center.y) * (v1.y - center.y);
if (d1 > d2)
return 1;
else return -1;
}
}
可视化问题的另一种方法是将列表循环播放为连续的点对，并询问新点是否位于由这两个点和中心点(眼睛)形成的无限视锥的眼线中，但是在没有三角函数的情况下可以做到这一点吗？
您可以使用基于叉积的 CCW(逆时针/顺时针方向)函数(您已经有det)并实现一种二叉搜索。
我看到的避免循环问题的最简单方法是引入两个虚构点 P[M] - P[0] 对中心的镜像和 P[N+1] - 列表末尾第一个点的副本。插入一次，并在需要时更正 M 索引。
找到 CCW 作为第一个和新点。如果为 True，则在范围0..M中进行二叉搜索，并在插入后递增 M。如果为 False，则在范围M..N+1中进行二进制搜索