找出同一条线上的相邻点

Question

给定同一条直线上的点列表，我需要找出每个点的相邻点。 See the image for illustration

我知道所有点的坐标。这些点在我的输入列表中随机排序。

我的做法：

1. 选择列表中的第一个点。求从这个点到所有点的向量。
2. 对于每个向量，找到逆时针角度。
3. 只有两个角度(a1, a2)可能。形成一个包含角度为 a1 的所有点的列表，以及一个包含角度为 a2 的点的列表。
4. 现在对于每个列表，找出欧氏 distance/vector 长度。
5. 将此列表按升序排序，可用于建立相对排序。

例：如果p2恰好是列表中的第一个点，那么，假设较小的角度为30，顺时针方向较大的角度为210。 因此，p1 将位于一个列表中。 p3,p4,p2 将位于另一个列表中。现在我可以获得点的相对顺序。

有没有更好的解决方案？

Answer 1

1. 比较前两点的Y轴，看直线是否垂直。 (O(1))
2. 如果垂直，则按 Y 轴排序 (O(nlogn))
3. 如果不是垂直的，按X轴排序(O(nlogn))
4. 为了找到相邻的点，通过二进制搜索（O（logn））在排序列表中找到点并取前一个点和下一个点。