Winkel berechnen bzw. Geraden sortieren

[riso]

Hallo,
ich habe ein Problem, für das ich bisher bei Google auch keine Lösung finden konnte. Ich habe einen Punkt, von dem mehrere Geraden in verschiedene Richtungen ausgehen. Als Daten habe ich die jeweils die x- und y-Koordinate von dem Punkt und die Koordinaten von den Endpunkten der ausgehenden Geraden. Wenn ich mir nun eine der ausgehenden Geraden auswähle, benötige ich die Info, welche Gerade als nächstes im Uhrzeigersinn davon liegt. Ich dachte, das könnte man vielleicht irgendwie machen, indem man jeweils den im Uhrzeigersinn gesehenen Winkel zwischen der ausgewählten Geraden und allen anderen berechnet und dann den kleinsten auswählt. Wie könnte man das in Java realisieren oder gibt es vielleicht schon etwas, das genau das leistet?
VG

 

[JCODA]

Berechne zu jeder Geraden den Winkel zur X-Achse, siehe etwa: https://docs.oracle.com/javase/7/docs/api/java/lang/Math.html#atan2(double, double)
Subtrahiere den Winkel der ausgewählten Gerade. (Entferne sie vorher aus der Liste der möglichen Geraden)
Normiere alle Winkel, sodass sie im Intervall 0,2pi liegen.
Finde das Minimum dieser Winkel, die zugehörige Gerade ist die, die du suchst.

Anschaulich ist das eine Rotation, sodass deine ausgewählte Gerade in der X-Achse liegt und dann wird der kleinste Winkel davon ausgehend gesucht.

 

[riso]

Hm, wenn ich das jetzt richtig verstehe, dann liefert mit atan2 den Winkel der Polarkoordinaten zurück. Da streikt mein mathematischer Horizont allerdings bei dem Rest. Je nach Lage der Geraden kommen dann doch Werte heraus, die ich nicht unbedingt direkt vergleichen kann, da die betrachte Gerade doch zum Beispiel von links unten nach rechts oben, aber auch von rechts unten nach links oben führen kann usw. Ich hab da sicherlich nen Denk- und/oder Verständnisfehler

 

[JStein52]

Hilft dir das ? http://massmatics.de/merkzettel/index.php#!714:Winkel_zwischen_Geraden_&_x-Achse

 

[riso]

Ok, danke. Das was als Winkel rauskommt wird so klar. Und als Eingabe übergebe ich artan2 dann lediglich den Endpunkt der Geraden, so wie ich das verstehe. Aber ein einzelner Punkt definiert doch keine Gerade und sagt nix über die Steigung aus. Irgendwo hängt es da noch in meinem Hirn...

 

[JCODA]

Ok, danke. Das was als Winkel rauskommt wird so klar. Und als Eingabe übergebe ich artan2 dann lediglich den Endpunkt der Geraden, so wie ich das verstehe. Aber ein einzelner Punkt definiert doch keine Gerade und sagt nix über die Steigung aus. Irgendwo hängt es da noch in meinem Hirn...

Du musst zunächst von jedem "Endpunkt" deiner Geraden den Startpunkt abziehen, sodass sich der Vektor auf den Ursprung bezieht.

 

[JStein52]

Unter meinem Link findest du ganz vorne (Punkt 1.) oder 2.)) wie du vorgehst wenn du zwei Punkte der Geraden hast.

Edit: das Stichwort heisst Steigung

 

[riso]

Ah, ok, so langsam wird's... Und die Sache mit der Normierung ist dann, damit man keine negativen Winkel mehr hat, oder?

 

[JStein52]

Und die Sache mit der Normierung ist dann

Das habe ich auch nicht verstanden was der Autor da sagen wollte

Edit: aber du kannst mal hier gucken: http://www.mathematik-oberstufe.de/analysis/lin/gerade2d-steigungswinkel.html
Da ist oben eine Gerade die du interaktiv verändern kannst und dann siehst du die Winkelverhältnisse

 

[AndiE]

Ich würde anders vorgehen. Zuerst würde ich eine Objekt der Klasse "Stern anlegen", die als Attribut "Urspungspunkt" und einem Array aus Objekten der Klasse "Gerade" besitzt. Die Klasse "Gerade" erhält dann die Attribute "Zielpunkt" und "Winkel". Nun kannst du für alle Objekte des Arrays die Endpunkte eintragen, den Winkel berechnen und dann die Objekte aufsteigend nach dem Winkel sortieren. Dann kannst du auch einfach die danebenliegenden Geraden feststellen.

 

[JStein52]

Ich würde anders vorgehen.

Ich würde noch anders vorgehen und gar keinen Winkel ausrechnen. Denn die Steigung ist ja ein Mass für den Winkel, also genügt es diese zu bestimmen und nach Steigung zu sortieren ...

 

[JCODA]

Ich würde noch anders vorgehen und gar keinen Winkel ausrechnen. Denn die Steigung ist ja ein Mass für den Winkel, also genügt es diese zu bestimmen und nach Steigung zu sortieren ...

Steigung sollte man nicht berechnen. Was passiert bei einer vertikalen Geraden? Division durch 0? Bzw speziell bei zwei Geraden, die hohe Steigung und sehr starkes Gefälle haben, sind nah beieinander, wobei deren Steigung sich sehr unterscheidet.

 

[JStein52]

Was passiert bei einer vertikalen Geraden? Division durch 0?

Der Winkel ist aber der ArcusTangens der Steigung. Also berechnest du sie auf jeden Fall. Denn der Tangens von 90° ist genau so wenig definiert !

 

[JCODA]

Der Winkel ist aber der ArcusTangens der Steigung. Also berechnest du sie auf jeden Fall. Denn der Tangens von 90° ist genau so wenig definiert !

Deswegen hab ich speziell die atan2-Methode genannt, die macht alle notwendigen Fallunterscheidungen, man übergibt nämlich nicht die Steigung, sondern die Vektorkoordinaten.

Spoiler: atan2-Doc

Returns the angle theta from the conversion of rectangular coordinates (x, y) to polar coordinates (r, theta). This method computes the phase theta by computing an arc tangent of y/x in the range of -pi to pi. Special cases:

• If either argument is NaN, then the result is NaN.
• If the first argument is positive zero and the second argument is positive, or the first argument is positive and finite and the second argument is positive infinity, then the result is positive zero.
• If the first argument is negative zero and the second argument is positive, or the first argument is negative and finite and the second argument is positive infinity, then the result is negative zero.
• If the first argument is positive zero and the second argument is negative, or the first argument is positive and finite and the second argument is negative infinity, then the result is the double value closest to pi.
• If the first argument is negative zero and the second argument is negative, or the first argument is negative and finite and the second argument is negative infinity, then the result is the double value closest to -pi.
• If the first argument is positive and the second argument is positive zero or negative zero, or the first argument is positive infinity and the second argument is finite, then the result is the double value closest to pi/2.
• If the first argument is negative and the second argument is positive zero or negative zero, or the first argument is negative infinity and the second argument is finite, then the result is the double value closest to -pi/2.
• If both arguments are positive infinity, then the result is the double value closest to pi/4.
• If the first argument is positive infinity and the second argument is negative infinity, then the result is the double value closest to 3*pi/4.
• If the first argument is negative infinity and the second argument is positive infinity, then the result is the double value closest to -pi/4.
• If both arguments are negative infinity, then the result is the double value closest to -3*pi/4.

 

[JStein52]

Deswegen hab ich speziell die atan2-Methode genannt, die macht alle notwendigen Fallunterscheidungen

Das weiss ich schon und das war ja durchaus richtig. Ich dachte nur man könnte sich die Winkelberechnungen sparen. Das war aber ein Trugschluss da arctan(x) ja keine lineare Funktion ist.

 

[riso]

Also, da die mathematischen Grundlagen von dem Teil hier nicht so meins sind nochmal die Frage, ob ich das richtig verstanden habe: Ich habe meinen einen Punkt (xu, yu), von dem diverse Geraden mit den Endpunkten (x1,y1),...(xn,yn) ausgehen. Dann ziehe ich zunächst von jedem (xn,yn) die Koordinaten (xu,yu) ab und übergebe das Ergebnis an artan2, um den Winkel rauszubekommen. Dann ziehe ich von allen anderen den berechneten Winkel für die ausgewählte Gerade ab. Den Teil mit dem normalisieren hab ich nicht so ganz verstanden. Was mache ich da wie? Ist der kleinste Winkel am Ende dann der nächste im oder gegen den Uhrzeigersinn von der gewählten Geraden aus gesehen?

 

[JCODA]

Den Teil mit dem normalisieren hab ich nicht so ganz verstanden. Was mache ich da wie?

Du addierst 2*pi an deine Winkel, und rechnest modulo 2*pi, so ändert sich der Winkel nicht (Addition von 2*pi ist ja keine Veränderung der Geometrie. ) aber danach ist er positiv.

Ist der kleinste Winkel am Ende dann der nächste im oder gegen den Uhrzeigersinn von der gewählten Geraden aus gesehen?

Der sollte gegen den Uhrzeigersinn sein, d.h. für den "im Uhrzeigersinn" musst du wohl nach dem Maximum suchen. (Bin ich mir aber gerade nicht 100% sicher... )

Achja, vergiss nicht, die ausgewählte Gerade aus den x1...xn raus zu nehmen.

 

[riso]

Ok, super, dann mache ich mich mal an die Umsetzung. Vielen Dank für die Hilfe und die geduldige Schritt-für-Schritt-Erklärung. Ihr habt mir extrem geholfen .

 

[JStein52]

benötige ich die Info, welche Gerade als nächstes im Uhrzeigersinn

Übrigens, wenn genau das da die Aufgabenstellung ist dann geht es doch mit dem Vergleich der Steigungen und ohne den arctan zu bemühen

 

[AndiE]

Das mit der Steigung hat meiner Meinung nach einen Haken. Der Zeiger auf der Uhr, der auf 1 zeigt hat die gleiche Steigung wie der, der auf 7 zeigt. Trotzdem sind beide 180 Grad versetzt.

 

[JStein52]

Das kommt darauf an. Reden wir von Geraden oder von "Zeigern" ? Ich weiss ja nicht genau was der TE @riso da will ? Aber deine beiden Zeiger liegen auf der gleichen Geraden

 

[riso]

Hört sich so an, als sei ich mit der Winkelvariante auf der sicheren Seite, also werde ich als mathematisch nicht so prall Begabter diese Variante mal umsetzen

 

[JStein52]

diese Variante mal umsetzen

Dann lass mal hören ob es das tut was du möchtest. Aber trotzdem die Frage: wäre der Zeiger auf 1 Uhr und auf 7 Uhr für deinen Anwendungsfall die gleiche Gerade ?

 

[JStein52]

Ich habe mal eine Geradenklasse angelegt mit einer main in der sechs verschiedene Geraden erzeugt werden die alle durch den Ursprung gehen. Und dann habe ich sie nach Steigung sortiert. Was im übrigen gleiche Reihenfolge ergibt wie beim Winkel den ich zur Kontrolle mit ausgebe. (Sonderfall senkrechte Gerade mal nicht berücksichtigt)
Und die Geraden die der n.ten Gerade im Uhrzeigersinn am nächsten ist, ist die (n-1).te
Kontrolliere mal ob das so stimmt. Oder teste mit eigenen Geraden

package gerade;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

/**
 *
 * @author Juergen
 */
public class Gerade  implements Comparator<Gerade> {

    public final double m, b, alpha;

    public Gerade() {
        this.m = 0;
        this.b = 0;
        this.alpha = 0;
    }
    public Gerade(double m, double b) {
        this.m = m;
        this.b = b;
        this.alpha = Math.atan(m);
    }
    public Gerade(double x1, double y1, double x2, double y2) {
        this.m = (y2-y1)/(x2-x1);
        this.b = y2-m*x2;
        this.alpha = Math.atan(m);
    }

   public String toString() {
        return "f(x) = "+m+" * x + "+b+"(Steigungswinkel: "+alpha+")";
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Gerade gerade1 = new Gerade(0.0, 0.0, 10.0, 10.0);
        System.out.println("Gerade 1  "+gerade1);
        Gerade gerade2 = new Gerade(0.0, 0.0, 10.0, 5.0);
        System.out.println("Gerade 2  "+gerade2);
        Gerade gerade3 = new Gerade(0.0, 0.0, -10.0, -10.0);
        System.out.println("Gerade 3  "+gerade3);
        Gerade gerade4 = new Gerade(0.0, 0.0, -10.0, -6.0);
        System.out.println("Gerade 4  "+gerade4);
        Gerade gerade5 = new Gerade(0.0, 0.0, -10.0, 10.0);
        System.out.println("Gerade 5  "+gerade5);
        Gerade gerade6 = new Gerade(0.0, 0.0, 10.0, 8.0);
        System.out.println("Gerade 6  "+gerade6);

        ArrayList<Gerade> geradenListe = new ArrayList<>();
        geradenListe.add(gerade1);
        geradenListe.add(gerade3);
        geradenListe.add(gerade2);
        geradenListe.add(gerade4);
        geradenListe.add(gerade5);
        geradenListe.add(gerade6);
       
        // sortieren nach Steigung
        Collections.sort(geradenListe, new Gerade());
        for(Gerade gerade:geradenListe) {
            System.out.println("Gerade "+gerade);
        }
    }

    @Override
    public int compare(Gerade o1, Gerade o2) {
        return Double.compare(o1.m, o2.m);
    }
   
}

 

[Flown]

public class Gerade  implements Comparator<Gerade> {

Bitte verwende doch Comparable

 

[JStein52]

Ja, der Teil und die Main sind nur mal so schnell dahin geschrieben. Und Comparable oder Comparator gehört eigentlich überhaupt nicht in diese Klasse. Ist nur um schnell mal das Ergebnis hier zu posten.

 

[Flown]

Naja Comparable schon. Ist ja die natürliche Ordnung einer Klasse. Comparator geb ich dir recht.

 

[JStein52]

Naja Comparable schon.

Jaaa. Aber eigentlich interessiert mich ja nur ob der TE das so beabsichtigt hat oder ob er die "Zeiger"-Lösung meint ?

 

[riso]

Also, ich habe das jetzt mal mit den Winkel getestet und es scheint zu funktionieren, dass der kleinste Wert die nächste Gerade im Uhrzeigersinn liefert .
Wegen der Frage zu den Zeigern: Für meine Aufgabe wären das 2 verschiedene Geraden. Angenommen ich habe eine Uhr mit n>=1 Zeigern und betrachte einen Zeiger, der z.B. auf die 1 zeigt. Dann möchte ich von denen, die sonst noch da sind, als Ergebnis den nächsten, der im Uhrzeigersinn angetroffen wird...

 

[JStein52]

als Ergebnis den nächsten, der im Uhrzeigersinn angetroffen wird...

Ok. Also du meinst nicht "Gerade" sondern "Vektor" d.h. die Richtung ist zu berücksichtigen

 

[riso]

Öhm, vermutlich ja. Für mich waren das alles Geraden, die quasi in der Mitte der Uhr beginnen

 

[JStein52]

Eine Gerade im mathematischen Sinn beginnt nicht irgendwo und endet auch nicht irgendwo ... ein Vektor schon.

 

[riso]

Danke, wieder was gelernt. Ich werde versuchen, bei meinem nächsten Problem direkt die richtigen Bezeichnungen zu nutzen

 

[JStein52]

War ja nicht schlimm. Ist geklärt und gut ist.