Вести список точек вокруг центральной точки, сохраняя порядок CCW

Question

У меня есть следующий класс:

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

И я хочу поддержать добавление / удаление вершин в соседний список, чтобы точки были перечислены в порядке CCW вокруг этой вершины (какая точка является первой в списке, не имеет значения). Если точки коллинеарны, ближе к этому должны быть первые точки. Я пробовал несколько методов, но до сих пор всегда был в состоянии найти контрпример, который не работает для данного метода.

Кто-нибудь имеет хорошее представление о том, как сделать это простым и эффективным способом?

Answer 1

Выразите координаты точки в полярной форме

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

и используйте лексикографическое упорядочение по углу, а затем по радиусу.