维护中心点周围的点列表，保留CCW顺序

Question

我有以下类：

 public class Vertex() {
    private double xCoord;
    private double yCoord;
    private ArrayList<Vertex> neighborList();
 }

我想要支持向neighborList添加/删除顶点，这样这些点就会按CCW顺序排列在这个顶点周围(列表中的第一个点无关紧要)。如果点是共线的，则离此较近的点应该是第一个。我已经尝试了几种方法，但到目前为止，我总是能够找到一个对给定方法无效的反例。

有没有人知道如何以一种简单有效的方式做到这一点？

Answer 1

以极坐标形式表示点坐标

t = atan2(Y-Yo, X-Xo)
r = sqrt((X-Xo)^2 + (Y-Yo)^2)

并在角度上使用字典序排序，然后对半径进行排序。