Сортировка точек по их полярному углу в Java

Question

Я использую алгоритм сканирования Грэма для поиска выпуклой оболочки множества точек Я пытаюсь сортировать точки по их полярному углу, но я понятия не имею, как это сделать (Я уже отсортировал набор точек по их координатам Y).

То, что я уже писал, как это:

public double angle(Coord o, Coord a) 
{ 
    return Math.atan((double)(a.y - o.y)/(double)(a.x - o.x)); 
} 

где Coord класс, где у меня есть X и Y координаты в double.

Я также посмотрел на одну из подобных записей в Stack Overflow, где кто-то пытался реализовать этот угол с C++, но я не понимаю qsqrt. У нас есть что-то подобное на Java?

qreal Interpolation::dp(QPointF pt1, QPointF pt2) 
{ 
    return (pt2.x()-pt1.x())/qSqrt((pt2.x()-pt1.x())*(pt2.x()-pt1.x()) + (pt2.y()-pt1.y())*(pt2.y()-pt1.y())); 
} 

Буду рад, если кто-нибудь сможет мне помочь.

Answer 1

Вам не нужно рассчитать полярный угол для сортировки по нему. Поскольку триг-функции монотонны (всегда увеличиваются или всегда уменьшаются) внутри квадранта, просто сортируйте по самой функции, например. загар в вашем случае. Если вы выполняете сканирование Graham, начиная с самой нижней точки, вам нужно всего лишь посмотреть на первые два квадранта, поэтому было бы проще отсортировать по котану, так как он монотонен для обоих квадрантов.

Другими словами, вы можете просто сортировать по - (x - x1)/(y - y1) (где (x1, y1) - координаты начальной точки), которые будут быстрее вычисляться. Сначала вам нужно будет выделить точки, где y == y1, конечно, и добавить их в верхнюю или нижнюю часть списка в зависимости от знака (x - x1) `, но их легко идентифицировать, поскольку вы уже отсортировано по y, чтобы найти отправную точку.

Answer 2

Math.atan() возвращает угол между -pi/2 до pi/2. Вам нужно будет скорректировать результаты для двух других координат.

Если вам нужен угол от центра выпуклого корпуса, вам нужно сначала перевести координаты так, чтобы centroid был источником.

Answer 3

Как уже упоминалось выше, вычисление самого полярного угла является довольно неряшливым способом перемещения вещей. Вы можете определить простой компаратор и использовать кросс-продукты для сортировки по полярному углу. Вот код в C++ (который я использую для моего Graham сканирования):

struct Point { 
    int x, y; 
} 

int operator^(Point p1, Point p2) { 
    return p1.x * p2.y - p1.y * p2.x; 
} 

bool operator<(Point p1, Point p2) 
{ 
    if(p1.y == 0 && p1.x > 0) 
     return true; //angle of p1 is 0, thus p2 > p1 

    if(p2.y == 0 && p2.x > 0) 
     return false; //angle of p2 is 0 , thus p1 > p2 

    if(p1.y > 0 && p2.y < 0) 
     return true; //p1 is between 0 and 180, p2 between 180 and 360 

    if(p1.y <0 && p2.y > 0) 
     return false; 

    return (p1^p2) > 0; //return true if p1 is clockwise from p2 
} 

Вы можете реализовать то же самое в Java, определив Point класс. В основном я перегрузил оператора ^, чтобы вернуть крест продукта. Остальное очевидно, надеюсь, что это поможет!