4. Schneidet eine Strecke eine Kugel?

Schneidet eine Strecke eine Kugel?

  • B

    Hi Leute!
    Gegeben sei eine Strecke durch 2 Punkte A und B und eine Kugel mit dem Mittelpunkt im Koordinatenursprung und dem Radius r.
    Wie kann ich bestimmen, ob die Strecke die Kugel schneidet. Also, ob sie irgendwo gemeinsame Punkte besitzen. Dabei kann die Strecke komplett in der Kugel liegen.
    Das ganze will ich programmiertechnisch mit einer Mathe-Lib umsetzen.

    Ich dachte erst an einen variablen Geradenpunkt g = A + s * (B - A). Dessen Norm ist abhängig von s. Also das Minimum suchen. Die s-Koordinate des Minimumpunktes im Bereich [0 bis 1] clampen, da es eine Strecke und keine Gerade ist. Die geclampte s-Koordinate in den variablen Geradenpunkt einsetzen und die Norm des entstehenden Punktes ist dann der kleinste Abstand.
    Allerdings komme ich an einer Stelle nicht weiter: Minimumpunkt finden. Klar, die erste Ableitung der Funktion Norm(s) habe ich, kann sie aber nicht nach s umstellen.

    Geht das mit Vektoren (ohne Analysis) auch einfacher und schneller?

    0
  • S

    Hilft dir http://www.matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=86998 ?

    MfG SideWinder

    0
  • B

    Nicht wirklich, da geht es um Kreise, nicht umm Kugeln.

    0
  • ?

    kleiner Tipp: sqrt(f(x)) hat ein Mini/Maximum bei x_0 <=> f(x) hat ein Mini/Maximum bei x_0.

    0
  • B

    Ich glaube, ich habe eine Möglichkeit gefunden:
    Liegt einer der beiden Punkte in der Kugel -> "Schnitt"
    Dann das Kreuzprodukt aus A und B berechnen: C = A x B
    Wenn der Betrag von C null ist, dann liegen A, B und der Koordinatenursprung auf einer Geraden. Dann gibt es 2 Möglichkeiten:
    1. 1 Punkt vor der Kugel, einer dahinter.
    2. Beide Punkte vor oder hinter der Kugel
    Das finde ich mit dem Punktprodukt heraus. Wenn A o B < 0 ist, dann ist es Fall 1. Also "Schnitt"
    Wenn A o B > 0 ist, liegen beider vor / hinter der Kugel. Also "Kein Schnitt"
    Jetzt ist ausgeschlossen, dass C = (0|0|0) ist.
    Man berechnet eine Hilfsebene. Also die Normale n = (A-B)xC. Diese wird noch normalisiert. n0= n / |n|
    Der kürzeste Abstand ist jetzt d = n0 o A. Wenn jetzt d < r ist, also der Abstand kleiner als der Radius der Kugel ist, gibt es einen "Schnitt", wenn d > r gibt es "keinen Schnitt".

    😡 Verdammt!!! Das geht doch garnicht! Ich betrachte doch hier die Strecke als eine Gerade. Wenn der kürzeste Abstand außerhalb von A-B liegt und kleiner als der Radius ist, zählt er ja trotzdem als Schnitt.

    Bitte helft!

    0
  • M

    Berechne den kürzesten Abstand zwischen der Gerade, die durch A und B definiert wird, und dem Mittelpunkt P der Kugel wie z. B. beim ersten Google-Treffer. Wenn λ > 1, prüfe den Abstand von B zu P. Wenn λ < 0, prüfe den Abstand von A zu P.

    0
  • B

    Danke. Wenn ich die Formel richtig umstelle und als Mittelpunkt den Koordinatenurpsrung benutze, komme ich so auf eine relativ einfache Formel:

    A=(XaYaZa);B=(XbYbZb)g=A+λ⋅(B−A)n=B−A∣B−A∣n∘g=0⇒λ=Xa2+Ya2+Za2−Xa⋅Xb−Ya⋅Yb−Za⋅ZbXa2+Ya2+Za2+Xb2+Yb2+Zb2−2⋅Xa⋅Xb−2⋅Ya⋅Yb−2⋅Za⋅Zbλ=∣A∣2−A∘B∣A∣2+∣B∣2−2⋅A∘B\begin{matrix} A=\begin{pmatrix}Xa\\ Ya\\ Za\end{pmatrix}; B=\begin{pmatrix}Xb\\ Yb\\ Zb\end{pmatrix}\\ g=A+\lambda \cdot \left ( B - A \right )\\ n=\frac{B-A}{\left | B-A \right |}\\ \\ n \circ g = 0 \Rightarrow \lambda = \frac{Xa^2 + Ya^2 + Za^2 - Xa\cdot Xb - Ya\cdot Yb - Za\cdot Zb } {Xa^2 + Ya^2 + Za^2 + Xb^2 + Yb^2 + Zb^2 - 2\cdot Xa\cdot Xb - 2\cdot Ya\cdot Yb - 2\cdot Za\cdot Zb }\\ \\ \mathbf{\lambda = \frac{\left | A \right |^2 - A\circ B}{\left | A \right |^2 + \left | B \right |^2 - 2\cdot A\circ B}} \end{matrix}

    Wenn Latex nicht geht, hier als Bild:
    http://www.bilder-hochladen.net/files/9bfc-27.png

    λAlso nur noch clampen und in die Gerade einsetzen und schon hab ich den kürzesten Punkt. Wenn der dann noch innerhalb des Radius ist, schneidet die Strecke die Kugel. Ich probiers gleich mal aus.

    0
  • B

    Ich habe es überprüft, die Rechnung stimmt!
    Aber warum wird Latex nicht richtig angezeigt?

    0
  • M

    In $-Zeichen setzen:

    $\begin{matrix} A=\begin{pmatrix}Xa\\ Ya\\ Za\end{pmatrix}; B=\begin{pmatrix}Xb\\ Yb\\ Zb\end{pmatrix}\\ g=A+\lambda \cdot \left ( B - A \right )\\ n=\frac{B-A}{\left | B-A \right |}\\ \\ n \circ g = 0 \Rightarrow \lambda = \frac{Xa^2 + Ya^2 + Za^2 - Xa\cdot Xb - Ya\cdot Yb - Za\cdot Zb } {Xa^2 + Ya^2 + Za^2 + Xb^2 + Yb^2 + Zb^2 - 2\cdot Xa\cdot Xb - 2\cdot Ya\cdot Yb - 2\cdot Za\cdot Zb }\\ \\ \mathbf{\lambda = \frac{\left | A \right |^2 - A\circ B}{\left | A \right |^2 + \left | B \right |^2 - 2\cdot A\circ B}} \end{matrix}$
    0
  • O

    kleine Schönheitskorrektur, da die Lösung noch nicht ganz minimal ist:

    λ=−A∘(B−A)∣B−A∣2\lambda = -\frac{A\circ (B-A)}{\left | B-A \right |^2}

    Übrigens solltest du dir die Elementschreibweise wenn möglich abgewöhnen, das geht in diesem Fall wunderbar ohne die Vektoren zwischenzeitlich aufzubröseln :). Macht man auch weniger Fehler.

    0
Anmelden zum Antworten