4. Kreis auf einer Ebene

Kreis auf einer Ebene

  • C

    Moin 🙂

    Ich glaube das Problem das ich Lösen möchte ist ziemlich simpel, dennoch suche ich einen möglichst leichten (Anzahl/Komplexität der Berechnungen) bzw schnellen weg.

    Hier ist eine Abbildung des Problems:
    https://s27.postimg.org/mnpt8avo3/z_Forum.png

    Im 3D:
    Eine Ebene ist mit Punkt-Normalenform bekannt. Gesucht sind jetzt 4 Punkte die um den Punkt mit radius X herrumliegen und auf der Ebene sind.

    Also ganz stumpf gesagt, suche ich 4 Punkte auf einem Kreis auf der Ebene.

    Wäre die Ebene auf einer Achse wäre das ganze einfach. Dann könnte man einfach mit Sin/Cos diese Punkte bestimmen. Im 3D müsste ich dafür eine Rotationsmatrix nutzen... Das möchte ich aber vermeiden.

    Hat jemand eine Idee wie ich mit dem Normalenvektor und dem Stützpunkt der Ebene
    zumindest irgendeinenPunkt auf der Ebene berechnen kann? Vielleicht kann ich mir damit schonmal was neues überlegen.

    Gruß
    Chris

    0
  • Mod

    Normalenvektor nehmen. Irgendeinen senkrechten Vektor dazu berechnen, der die Länge des Radius hat, nennen wir ihn A. Einen Vektor B berechnen, der senkrecht sowohl auf A als auch auf dem Normalenvektor steht (Kreuzprodukt) und ebenfalls die Länge des Radius hat. Sei M der Mittelpunkt. Vier Punkte auf dem Kreis sind dann M+A, M-A, M+B und M-B.

    Das passt derart gut mit den vier Punkten, dass dies höchstwahrscheinlich doe Lösung ist, die der Lehrer sucht.

    Ansonsten für mehr Punkte: Was ist so schlimm an Drehmatrizen? Formell hinzuschreiben ist das doch auch nicht viel länger als in einer der Koordinatenebenen und wenn du tatsächlich konkrete Punkte ausrechnen musst, dann macht das doch sowieso der Computer.

    0
  • C

    Es ist kein Lehrer der die Lösung haben möchte, sondern mein Algorithmus der diese braucht 🙂

    Kurz angrissen:
    Ich muss für tausende Ebenen X Punkte bestimmen die im vorgegebenem Radius (Noise-Level) liegen. für X = 4, ergibt sich ein Polyeder aus 8 Ecken. Diese Polyeder stellen Unsicherheitsräume im reziprogem Raum dar. Dem folgt eine Autokorrelation aller Polyeder (Minkowski Sum), und eine Reduzierung durch Überschneidungsräume. Im Endeffekt sollen die Unsicherheitsräume kleiner werden.
    Zusammengeffast:
    Extrem viele Operationen die auch noch Zeitkritisch sind. Das ganze soll wenn möglich in weit weniger als 1ms laufen. Dafür habe ich zwar GPUs, und große Clustercomputer zur verfügung, aber das muss ich ja nicht umbedingt bis zum Anschlag ausnutzen.

    Wieder zum Problem mit der Ebene:
    Es gibt eine Möglichkeit z.B. an der Spitze des Normalenvektors eine Achse zu generieren welche ich für eine Rodrigues Rotation nutze. So könnte man einen Punkt mit Radius R finden. Die anderen könnte man durch Rotationen um den Normalenvektor berechnen.
    Allerdings sind das für 4 Punkte 5x Konstruktionen einer Rotationsmatrix, 1x eine Achse Berechnen und 5x Rotationen ausführen. Ich hatte gehofft es gibt einen schnelleren Weg. Es passiert ja gelegentlich, dass man einen sehr einfachen Weg übersieht.

    Gruß
    Chris

    0

  • Wenn du einen Punkt auf deinem Kreis in der Ebene kennst, kannst du dir einfach zwei Koordinatenachsen in der Ebene konstruieren. Die erste Achse ist der Radiusvektor vom Kreismittelpunkt in der Ebene zu deinem Punkt auf dem Kreis. Die zweite Achse bekommst du über das Kreuzprodukt der ersten mit der Ebenennormale. Sobald du diese beiden Richtungsvektoren, nennen wir sie u\mathbf u und v\mathbf v hast, kannst du beliebig weitere Punkte p\mathbf p auf dem Kreis konstruieren: p=o+cosφ⋅u+sinφ⋅v\mathbf p = \mathbf o + \cos\varphi \cdot \mathbf u + \sin\varphi \cdot \mathbf v, wobei o\mathbf o der Kreismittelpunkt und φ\varphi der Winkel des neuen Punktes ist... 😉

    Effektiv genau das was SeppJ schon gesagt hat, nur halt etwas verallgemeinert...

    0
  • Mod

    cl90 schrieb:

    Ich hatte gehofft es gibt einen schnelleren Weg. Es passiert ja gelegentlich, dass man einen sehr einfachen Weg übersieht.

    Meinen ersten Ansatz hast du aber schon gelesen, oder?

    0

  • Nur mal rein prinzipiell: Sollte es nicht evtl. einfacher sein, das was du da oben beschreibst direkt mit den exakten Kreisen zu machen anstatt zuerst irgendwie komplizierte Approximationen zu bestimmen? Die Minkowski Summe von zwei Kreisen sollte doch wieder ein Kreis sein!?

    0
  • C

    SeppJ schrieb:

    cl90 schrieb:

    Ich hatte gehofft es gibt einen schnelleren Weg. Es passiert ja gelegentlich, dass man einen sehr einfachen Weg übersieht.

    Meinen ersten Ansatz hast du aber schon gelesen, oder?

    Klar 🙂
    Nur weiß ich nicht wie ich das Analytische Problem Programmieren soll.
    Es gibt unendlich viele Orthogonale Vektoren, und ich möchte nicht eine Numerische Suche nach einem Starten. Das dauert alles viel zu lange.
    Wenn du eine Idee hast einen Orthogonalen Vektor zu finden, würde ich die gerne hören 🙂
    dann wäre das eine 1A Lösung.

    Das Hauptproblem ist, das ich keinen Zweiten Punkt auf der Ebene Kenne. Hätte ich einen, könnte ich diesen auf die Länge R Skallieren und mit einer Supereinfachen einmaligen Drehung und Zweimaliger Spiegelung die 4 Punkte finden. Leider habe ich keinen weiteren Punkt.
    Also Theorethisch wäre die Lösung meines Problemes einen beliebigen weiteren Punkt auf der Ebene zu finden, Und das am besten mit einer einfachen Berechnung.

    dot schrieb:

    Nur mal rein prinzipiell: Sollte es nicht evtl. einfacher sein, das was du da oben beschreibst direkt mit den exakten Kreisen zu machen anstatt zuerst irgendwie komplizierte Approximationen zu bestimmen? Die Minkowski Summe von zwei Kreisen sollte doch wieder ein Kreis sein!?

    Nicht ganz. Die MinkowskiSumme zweier Kreise ist je nach Kreis eine Fläche/ Donut oder ein 3D Konstrukt wenn beide Kreise nicht Paralell sind.
    Und die Summe wird nicht zwischen zwei Kreisen, sondern zwischen zwei Polyedern mit 8 Ecken ausgeführt.
    Außerdem wird die Minkowski Summe nicht ausgeführt weil Sie zu teuer ist. Faktisch betracht werden die Punktwolken aufaddiert und die Convexe Hülle gesucht, womit dann alle anderen Punkte die nicht Teil der Hülle Sind verworfen werden.

    0

  • cl90 schrieb:

    Das Hauptproblem ist, das ich keinen Zweiten Punkt auf der Ebene Kenne.

    Und was war das dann mit

    cl90 schrieb:

    Es gibt eine Möglichkeit z.B. an der Spitze des Normalenvektors eine Achse zu generieren welche ich für eine Rodrigues Rotation nutze. So könnte man einen Punkt mit Radius R finden.

    😕

    0
  • C

    Mir ist entfallen, dass ich für diese Rotation ebenfalls ein Ähnliches Problem lösen muss.
    An der Spitze des Normalenvektors brauche ich auch einen Orthogonalen Vektor für die RotationsAchse.
    Also habe ich das selbe Problem.

    Edit:
    Stumpf, dass es so lange gedauert hat bis der Groschen gefallen ist, aber ist das hier eine lösung:
    n = normalenvektor
    e = irgendein random Vektor (z.b. 1 0 0)
    b = cross(n,e) -> Orthogonaler Vektor der mir einen zweiten Punkt auf der Ebene Gibt?

    0

  • Ok, nun, einfache Möglichkeit: Berechne einen neuen Punkt durch verschieben deines Kreismittelpunktes in Richtung der Hauptachse, entlang der dein Normalvektor die geringste Ausdehnung hat, berechne den Vektor vom neuen Punkt zum Ausgangspunkt, bestimme das Kreuzprodukt dessen mit der Ebenennormale, addiere das zum Ausgangspunkt und voilà hast du einen weiteren Punkt in der Ebene...

    0

  • cl90 schrieb:

    Stumpf, dass es so lange gedauert hat bis der Groschen gefallen ist, aber ist das hier eine lösung:
    n = normalenvektor
    e = irgendein random Vektor (z.b. 1 0 0)
    b = cross(n,e) -> Orthogonaler Vektor der mir einen zweiten Punkt auf der Ebene Gibt?

    Ja, das ist der triviale Ansatz. Der scheitert aber wenn dein n zufälligerweise gleich e ist (Kreuzprodukt kollabiert dann). Du musst nur irgendwie sicherstellen, dass das nicht passieren kann...

    0
  • C

    dot schrieb:

    Ja, das ist der triviale Ansatz. Der scheitert aber wenn dein n zufälligerweise gleich e ist (Kreuzprodukt kollabiert dann). Du musst nur irgendwie sicherstellen, dass das nicht passieren kann...

    Das ist glücklicherweise sehr einfach, da die Normelenvektoren von -45° bis +45° auf einer beschnittenen Halbsphäre liegen. Ich kann einfach den 90° einheitsvektor neben. Sprich [0, 0, R] und ich erhalte immer einen Vektor != Normalenvektor.

    Zu deiner Mathematik habe ich aber nochmal eine Frage. War in deinem Ansatz etwas drin, so dass der resultierende orthogonale Vektor genau die richtige Länge (R) erhällt? Eine Faktorisierung auf Länge R ist jetzt nicht so teuer, aber es wäre schon ziemlich praktisch wenn die Lösung des Kreutzproduktes bereits auf Länge R wäre.

    Soweit schonmal ein Danke an euch alle 🙂
    Hat etwas länger gedauert bis ich es begriffen habe, aber das Hauptproblem ist gelöst.

    0

  • cl90 schrieb:

    Zu deiner Mathematik habe ich aber nochmal eine Frage. War in deinem Ansatz etwas drin, so dass der resultierende orthogonale Vektor genau die richtige Länge (R) erhällt?

    Nein, das geht im Allgemeinen leider nicht. Die Länge des Kreuzproduktes skaliert mit dem Sinus des Winkels zwischen den beiden Ausgangsvektoren. Wenn die beiden Ausgangsvektoren also nicht normal aufeinander stehen, wirst du dein Kreuzprodukt noch normalisieren müssen...

    0
  • C

    Danke 🙂

    0
  • C

    Zur Ergänzung falls jemand anderes eine Lösung gebrauchen könnte:

    Wenn die Ebenengleichung in: Stützpunkt und NormalenVektor gebeben ist, kann ein Beliebiger Punkt auf der Ebene auch ohne Kreutzprodukt generiert werden:

    n = (a, b, c)
    v = (-b, a, 0) // ist ein Orthogonaler Vektor

    <n, v> = 0; // Skalarprodukt

    Da spaart man sich glatt nochmal das Kreutzprodukt 🙂

    0
Anmelden zum Antworten