Sortieren von Punkten nach ihrem Polarwinkel in Java

Question

Ich benutze Graham Scan-Algorithmus, um die konvexe Hülle der Menge von Punkten zu finden Ich versuche, die Punkte nach ihrem Polarwinkel zu sortieren, aber ich habe keine Ahnung, wie es geht (Ich habe die Punkte bereits nach ihren Y-Koordinaten sortiert).

Was ich schon geschrieben habe, ist wie folgt:

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

wo Coord die Klasse, wo ich X und Y wie double koordiniert.

Ich schaute auch auf einen der ähnlichen Beiträge in Stack Overflow, wo jemand versucht hatte, diesen Winkel mit C++ zu implementieren, aber ich verstehe qsqrt nicht. Haben wir so etwas in 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())); 
} 

Ich werde mich freuen, wenn mir jemand helfen kann.

Answer 1

Sie müssen den Polarwinkel nicht berechnen, um nach ihm zu sortieren. Da trigonometrische Funktionen innerhalb eines Quadranten monoton (immer steigend oder immer abnehmend) sind, sortieren Sie einfach nach der Funktion selbst, z. die Bräune in deinem Fall. Wenn Sie den Graham-Scan verwenden, indem Sie mit dem untersten Punkt beginnen, müssen Sie nur die ersten beiden Quadranten betrachten. Daher ist es am einfachsten, nach Kotan zu sortieren, da es in beiden Quadranten monoton ist.

Mit anderen Worten, Sie können einfach nach - (x - x1)/(y - y1) sortieren (wobei (x1, y1) die Koordinaten Ihres Startpunkts sind), die schneller berechnet werden können. Zuerst müssen Sie die Punkte, in denen y == y1 ist, natürlich trennen und sie am oberen oder unteren Ende der Liste hinzufügen, abhängig vom Vorzeichen von (x - x1) `, aber sie sind leicht zu identifizieren, da Sie es bereits getan haben sortiert nach y, um deinen Startpunkt zu finden.

Answer 2

Math.atan() gibt einen Winkel zwischen -pi/2 und pi/2 zurück. Sie müssen die Ergebnisse für die anderen zwei Koordinaten anpassen.

Wenn Sie den Winkel von der Mitte der konvexen Hülse wollen, müssen Sie zuerst die Koordinaten so übersetzen, dass die centroid der Ursprung ist.

Answer 3

Wie bereits erwähnt, ist die Berechnung des Polarwinkels selbst eine ziemlich schlampige Art, Dinge zu tun. Sie können einen einfachen Vergleicher definieren und Kreuzprodukte verwenden, um nach Polarwinkel zu sortieren. Hier ist der Code in C++ (was ich für meine eigenen Graham verwenden Scan):

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 
} 

Sie können die gleiche Sache in Java implementieren, indem eine Point Klasse definieren. Grundsätzlich habe ich den Operator ^ überladen, um das Kreuzprodukt zurückzugeben. Der Rest ist offensichtlich, hoffe das hilft!