Hypercell ein ] Hypercell aus ] Zeige Navigation ] Verstecke Navigation ]
c++.net  
   

Die mobilen Seiten von c++.net:
https://m.c-plusplus.net

  
C++ Forum :: Mathematik und Physik ::  Kreis auf einer Ebene  
Gehen Sie zu Seite 1, 2  Weiter
  Zeige alle Beiträge auf einer Seite
Auf Beitrag antworten
Autor Nachricht
cl90
Mitglied

Benutzerprofil
Anmeldungsdatum: 15.01.2012
Beiträge: 360
Beitrag cl90 Mitglied 09:39:26 10.01.2017   Titel:   Kreis auf einer Ebene            Zitieren

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
SeppJ
Global Moderator

Benutzerprofil
Anmeldungsdatum: 10.06.2008
Beiträge: 26950
Beitrag SeppJ Global Moderator 10:28:16 10.01.2017   Titel:              Zitieren

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.

_________________
Korrekte Rechtschreibung und Grammatik sind das sprachliche Äquivalent zu einer Dusche und gepflegter Kleidung.
cl90
Mitglied

Benutzerprofil
Anmeldungsdatum: 15.01.2012
Beiträge: 360
Beitrag cl90 Mitglied 11:02:56 10.01.2017   Titel:              Zitieren

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


Zuletzt bearbeitet von cl90 am 11:03:27 10.01.2017, insgesamt 1-mal bearbeitet
dot
Mitglied

Benutzerprofil
Anmeldungsdatum: 20.05.2004
Beiträge: 6740
Beitrag dot Mitglied 11:34:00 10.01.2017   Titel:              Zitieren

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 §\mathbf u§ und §\mathbf v§ hast, kannst du beliebig weitere Punkte §\mathbf p§ auf dem Kreis konstruieren: §\mathbf p = \mathbf o + \cos\varphi \cdot \mathbf u + \sin\varphi \cdot \mathbf v§, wobei §\mathbf o§ der Kreismittelpunkt und §\varphi§ der Winkel des neuen Punktes ist... ;)

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

_________________
one point of view will never reveal the entire scene.


Zuletzt bearbeitet von dot am 11:39:04 10.01.2017, insgesamt 5-mal bearbeitet
SeppJ
Global Moderator

Benutzerprofil
Anmeldungsdatum: 10.06.2008
Beiträge: 26950
Beitrag SeppJ Global Moderator 11:35:59 10.01.2017   Titel:              Zitieren

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?

_________________
Korrekte Rechtschreibung und Grammatik sind das sprachliche Äquivalent zu einer Dusche und gepflegter Kleidung.
dot
Mitglied

Benutzerprofil
Anmeldungsdatum: 20.05.2004
Beiträge: 6740
Beitrag dot Mitglied 11:42:33 10.01.2017   Titel:              Zitieren

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!?

_________________
one point of view will never reveal the entire scene.


Zuletzt bearbeitet von dot am 11:44:13 10.01.2017, insgesamt 2-mal bearbeitet
cl90
Mitglied

Benutzerprofil
Anmeldungsdatum: 15.01.2012
Beiträge: 360
Beitrag cl90 Mitglied 12:17:13 10.01.2017   Titel:              Zitieren

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.


Zuletzt bearbeitet von cl90 am 12:17:59 10.01.2017, insgesamt 1-mal bearbeitet
dot
Mitglied

Benutzerprofil
Anmeldungsdatum: 20.05.2004
Beiträge: 6740
Beitrag dot Mitglied 12:20:51 10.01.2017   Titel:              Zitieren

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.

:confused:

_________________
one point of view will never reveal the entire scene.


Zuletzt bearbeitet von dot am 12:25:48 10.01.2017, insgesamt 2-mal bearbeitet
cl90
Mitglied

Benutzerprofil
Anmeldungsdatum: 15.01.2012
Beiträge: 360
Beitrag cl90 Mitglied 12:23:19 10.01.2017   Titel:              Zitieren

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?


Zuletzt bearbeitet von cl90 am 12:26:27 10.01.2017, insgesamt 1-mal bearbeitet
dot
Mitglied

Benutzerprofil
Anmeldungsdatum: 20.05.2004
Beiträge: 6740
Beitrag dot Mitglied 12:26:24 10.01.2017   Titel:              Zitieren

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...

_________________
one point of view will never reveal the entire scene.


Zuletzt bearbeitet von dot am 12:27:31 10.01.2017, insgesamt 1-mal bearbeitet
C++ Forum :: Mathematik und Physik ::  Kreis auf einer Ebene  
Gehen Sie zu Seite 1, 2  Weiter
Auf Beitrag antworten

Zeige alle Beiträge auf einer Seite




Nächstes Thema anzeigen
Vorheriges Thema anzeigen
Sie können Beiträge in dieses Forum schreiben.
Sie können auf Beiträge in diesem Forum antworten.
Sie können Ihre Beiträge in diesem Forum nicht bearbeiten.
Sie können Ihre Beiträge in diesem Forum nicht löschen.
Sie können an Umfragen in diesem Forum nicht mitmachen.

Powered by phpBB © 2001, 2002 phpBB Group :: FI Theme

c++.net ist Teilnehmer des Partnerprogramms von Amazon Europe S.à.r.l. und Partner des Werbeprogramms, das zur Bereitstellung eines Mediums für Websites konzipiert wurde, mittels dessen durch die Platzierung von Werbeanzeigen und Links zu amazon.de Werbekostenerstattung verdient werden kann.

Die Vervielfältigung der auf den Seiten www.c-plusplus.de, www.c-plusplus.info und www.c-plusplus.net enthaltenen Informationen ohne eine schriftliche Genehmigung des Seitenbetreibers ist untersagt (vgl. §4 Urheberrechtsgesetz). Die Nutzung und Änderung der vorgestellten Strukturen und Verfahren in privaten und kommerziellen Softwareanwendungen ist ausdrücklich erlaubt, soweit keine Rechte Dritter verletzt werden. Der Seitenbetreiber übernimmt keine Gewähr für die Funktion einzelner Beiträge oder Programmfragmente, insbesondere übernimmt er keine Haftung für eventuelle aus dem Gebrauch entstehenden Folgeschäden.