Sortowanie punktów według ich kąta biegunowego w Javie

Question

Używam algorytmu skanowania Grahama do znalezienia wypukłego kadłuba zestawu punktów Próbuję posortować punkty według ich kąta biegunowego, ale nie mam pojęcia, jak to zrobić (Posortowałem już zbiór punktów według ich współrzędnych Y).

Co ja już napisałem jest tak:

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

gdzie Coord jest klasa gdzie mam współrzędne X i Y jako double.

Przyjrzałem się także jednemu z podobnych stanowisk w Stack Overflow, w którym ktoś próbował zaimplementować ten kąt w C++, ale nie rozumiem qsqrt. Czy mamy coś takiego w Javie?

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())); 
} 

Będę zadowolony, jeśli ktoś może mi pomóc.

Answer 1

Nie trzeba obliczyć kąta biegunowego, aby go posortować. Ponieważ funkcje trygonometryczne są monotoniczne (zawsze rosnące lub zawsze maleją) w kwadrancie, wystarczy posortować według samej funkcji, np. opalenizna w twoim przypadku. Jeśli wdrażasz skanowanie Grahama zaczynając od najniższego punktu, wystarczy spojrzeć na pierwsze dwa kwadraty, aby najłatwiej było posortować je według cotana, ponieważ jest monotoniczny względem obu ćwiartek.

Innymi słowy, możesz sortować według - (x - x1)/(y - y1) (gdzie (x1, y1) są współrzędnymi punktu początkowego), które będą szybsze do obliczenia. Najpierw musisz oddzielić punkty, gdzie y == y1, oczywiście, i dodać je na górze lub na dole listy w zależności od znaku (x - x1) `, ale są łatwe do zidentyfikowania, ponieważ już masz posortowane według y, aby znaleźć punkt początkowy.

Answer 2

Math.atan() zwraca kąt między -pi/2 do pi/2. Będziesz musiał dostosować wyniki dla dwóch pozostałych współrzędnych.

Jeśli chcesz uzyskać kąt ze środka wypukłego kadłuba, musisz najpierw przetłumaczyć współrzędne, tak aby pochodziło centroid.

Answer 3

Jak wspomniano powyżej, obliczanie kąta biegunowego jako takiego jest dość niedbałym sposobem postępowania. Możesz zdefiniować prosty komparator i używać produktów krzyżowych do sortowania według kąta biegunowego. Oto kod w C++ (którego używam na moim Algorytm Grahama):

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 
} 

można zaimplementować samo w Javie, definiując klasę Point. Zasadniczo przeciąłem operatora ^, aby zwrócić produkt krzyżowy. Reszta jest oczywista, mam nadzieję, że to pomoże!