Schnittpunkt Grade-Körper

Übersicht

Sonstiges

Smalltalk

	US-Blitz ehemals "SimssmiS" Betreff: Schnittpunkt Grade-Körper	Do, Mai 08, 2014 0:44 Antworten mit Zitat
Mir will einfach nicht einfallen wie ich das berechnen Soll: Ich habe eine Grade die von einem Punkt außerhalb des Quaders ausgeht und diesen treffen wird. Nun will ich den Punkt berechnen, an dem die Grade den Quader trifft. Ich freue mich auf eure Ideen. US-Blitz

US-Blitz

ehemals "SimssmiS"

Betreff: Schnittpunkt Grade-Körper

Do, Mai 08, 2014 0:44
Antworten mit Zitat

Mir will einfach nicht einfallen wie ich das berechnen Soll:

Ich habe eine Grade die von einem Punkt außerhalb des Quaders ausgeht und diesen treffen wird.
Nun will ich den Punkt berechnen, an dem die Grade den Quader trifft.

Ich freue mich auf eure Ideen.

US-Blitz

	Jolinah	Do, Mai 08, 2014 1:50 Antworten mit Zitat
Im Prinzip kannst du jede Seite des Quaders auf einen Schnittpunkt mit der Geraden überprüfen. Wenn mehrere Seiten einen Schnittpunkt mit der Geraden haben, kannst du den Schnittpunkt nehmen, der am nächsten am Ausgangspunkt der Geraden liegt. Um den Schnittpunkt zu berechnen gibt es im Internet viele Beispiele. Im wesentlichen brauchst du pro Linie zwei Punkte die auf der Linie liegen. Oder bei einem Liniensegment (also keine Endloslinie) z.B. den Start und Endpunkt. (x1,y1) und (x2,y2) Dann kannst du pro Linie 3 Werte berechnen: A = y2 - y1 B = x1 - x2 C = A * x1 + B * y1 Bei der zweiten Linie das gleiche. Dann hast du A1, B1, C1 und A2, B2, C2. Danach: Pseudocode: Code: [AUSKLAPPEN] [EINKLAPPEN] Local det:Float = A1 * B2 - A2 * B1 If det = 0 Then 'Linien sind parallel Else Local x:Float = (B2 * C1 - B1 * C2) / det Local y:Float = (A1 * C2 - A2 * C1) / det EndIf Das gibt den Schnittpunkt (x,y) bei unendlichen Linien. Nun muss man noch prüfen ob sich der Schnittpunkt auf beiden Liniensegmenten befindet: Code: [AUSKLAPPEN] [EINKLAPPEN] If x > Min(x1,x2) And x <= Max(x1, x2) And y > Min(y1, y2) And y <= Max(y1,y2) Then 'Schnittpunkt befindet sich zwischen Start und Ende beider Liniensegmente Else 'Die Endloslinien schneiden sich zwar irgendwann bei (x,y), aber nicht innerhalb von Start- und Endpunkt des Liniensegments EndIf Es gibt vielleicht auch elegantere Lösungen. Das fiel mir nur gerade dazu ein. Die Formeln habe ich von einer Englischen Seite: http://community.topcoder.com/...=geometry2

Jolinah

Do, Mai 08, 2014 1:50
Antworten mit Zitat

Im Prinzip kannst du jede Seite des Quaders auf einen Schnittpunkt mit der Geraden überprüfen. Wenn mehrere Seiten einen Schnittpunkt mit der Geraden haben, kannst du den Schnittpunkt nehmen, der am nächsten am Ausgangspunkt der Geraden liegt.

Um den Schnittpunkt zu berechnen gibt es im Internet viele Beispiele. Im wesentlichen brauchst du pro Linie zwei Punkte die auf der Linie liegen. Oder bei einem Liniensegment (also keine Endloslinie) z.B. den Start und Endpunkt.

(x1,y1) und (x2,y2)

Dann kannst du pro Linie 3 Werte berechnen:

A = y2 - y1
B = x1 - x2
C = A * x1 + B * y1

Bei der zweiten Linie das gleiche. Dann hast du A1, B1, C1 und A2, B2, C2. Danach:

Pseudocode:
Code: [AUSKLAPPEN]

Local det:Float = A1 * B2 - A2 * B1
If det = 0 Then
'Linien sind parallel
Else
Local x:Float = (B2 * C1 - B1 * C2) / det
Local y:Float = (A1 * C2 - A2 * C1) / det
EndIf

Das gibt den Schnittpunkt (x,y) bei unendlichen Linien. Nun muss man noch prüfen ob sich der Schnittpunkt auf beiden Liniensegmenten befindet:

Code: [AUSKLAPPEN]

If x > Min(x1,x2) And x <= Max(x1, x2) And y > Min(y1, y2) And y <= Max(y1,y2) Then
'Schnittpunkt befindet sich zwischen Start und Ende beider Liniensegmente
Else
'Die Endloslinien schneiden sich zwar irgendwann bei (x,y), aber nicht innerhalb von Start- und Endpunkt des Liniensegments
EndIf

Es gibt vielleicht auch elegantere Lösungen. Das fiel mir nur gerade dazu ein. Die Formeln habe ich von einer Englischen Seite: http://community.topcoder.com/...=geometry2

	US-Blitz ehemals "SimssmiS"	Do, Mai 08, 2014 13:12 Antworten mit Zitat
Vielen Dank erstmal für die Mühe. Aber wenn ich das richtig verstanden habe ist dies hier doch die Berechnung für den Schnittpunkt von zwei graden. In meinem Fall brauche ich aber den Schnittpunkt einer Graden (Vorliegend aus Ausgangspunkt + Richtungsvektor) und einem Quader (bekannt sind dort: der vordere untere linke Punkt und der hintere obere rechte Punkt aus denen sich der Quader aufspannen lässt.)

US-Blitz

ehemals "SimssmiS"

Do, Mai 08, 2014 13:12
Antworten mit Zitat

Vielen Dank erstmal für die Mühe.
Aber wenn ich das richtig verstanden habe ist dies hier doch die Berechnung für den Schnittpunkt von zwei graden.
In meinem Fall brauche ich aber den Schnittpunkt einer Graden (Vorliegend aus Ausgangspunkt + Richtungsvektor) und einem Quader (bekannt sind dort: der vordere untere linke Punkt und der hintere obere rechte Punkt aus denen sich der Quader aufspannen lässt.)

	Tornado11	Do, Mai 08, 2014 13:17 Antworten mit Zitat
Du weisst schon, dass sich ein Quader mit 4 'begrenzten' Geraden beschreiben lässt? Edit: Ups, hab wohl geometrische Begriffe verwechselt. Du musst natürlich die Gerade mit den Ebenen des Quaders schneiden. Mir fällt momentan nichts besseres ein, als die jeweiligen Ebenengleichungen aufzustellen und dann das Gleichungssytem 3ter Ordnung mit einem Algorithmus zu lösen (wie z.B. Gauss Eliminationsverfahren oder mit QR Zerlegung). d.h. Du hast die Gerade gegeben durch P = Richtungsvektort+Ortsvektor und E = A + u(B-A)+v*(C-A) wobei A,B,C drei Punkte in der Ebene sind. Dann musst du das Gleichungssystem P=E lösen und erhälst einen Punkt (t,u,v) und musst noch prüfen ober der sich in der begrenzten Ebene befindet. Spezialfälle: Gerade liegt in der Ebene, Gerade parallel zur Ebene muss man sich noch überlegen. Wenn sich die Gerade fast parallel zur Ebene befindet, dann ist der Schnittpunkt eventuell sehr, sehr weit weg. Da muss man sich überlegen wie man das sauber angeht. Edit2: hab noch was gefunden. http://users.informatik.uni-ha...-C/cg1.pdf Unter "Mathematische Hilfsmittel" wird das Problem "Schnitt Ebene-Gerade" gelöst. <a,b> ist das Skalarprodukt von a und b. Und ich glaube deine Quader wird nicht eindeutig mit zwei Punkten aufgespannt. Man weiss ja nicht, was "vorne" oder "hinten" ist im dreidimensionalen Raum

Tornado11

Do, Mai 08, 2014 13:17
Antworten mit Zitat

Du weisst schon, dass sich ein Quader mit 4 'begrenzten' Geraden beschreiben lässt?
Edit:
Ups, hab wohl geometrische Begriffe verwechselt. Du musst natürlich die Gerade mit den Ebenen des Quaders schneiden.

Mir fällt momentan nichts besseres ein, als die jeweiligen Ebenengleichungen aufzustellen und dann das Gleichungssytem 3ter Ordnung mit einem Algorithmus zu lösen (wie z.B. Gauss Eliminationsverfahren oder mit QR Zerlegung).
d.h. Du hast die Gerade gegeben durch P = Richtungsvektor*t+Ortsvektor
und E = A + u*(B-A)+v*(C-A) wobei A,B,C drei Punkte in der Ebene sind.
Dann musst du das Gleichungssystem P=E lösen und erhälst einen Punkt (t,u,v) und musst noch prüfen ober der sich in der begrenzten Ebene befindet.
Spezialfälle: Gerade liegt in der Ebene, Gerade parallel zur Ebene muss man sich noch überlegen.
Wenn sich die Gerade fast parallel zur Ebene befindet, dann ist der Schnittpunkt eventuell sehr, sehr weit weg. Da muss man sich überlegen wie man das sauber angeht.

Edit2: hab noch was gefunden.
http://users.informatik.uni-ha...-C/cg1.pdf

Unter "Mathematische Hilfsmittel" wird das Problem "Schnitt Ebene-Gerade" gelöst. <a,b> ist das Skalarprodukt von a und b.

Und ich glaube deine Quader wird nicht eindeutig mit zwei Punkten aufgespannt. Man weiss ja nicht, was "vorne" oder "hinten" ist im dreidimensionalen Raum

	Jolinah	Do, Mai 08, 2014 20:26 Antworten mit Zitat
Achso, hab da was verwechselt.. bin irgendwie von 2D ausgegangen, also von einem Quadrat Bei 3D muss man das eher über die Ebenen/Flächen lösen. Eventuell muss auch eine Seite in 2 Dreiecke aufgeteilt werden, damit lassen sich dann vielleicht andere Formeln anwenden. Ist mir aber gerade auch zu hoch.. ^^

Jolinah

Do, Mai 08, 2014 20:26
Antworten mit Zitat

Achso, hab da was verwechselt.. bin irgendwie von 2D ausgegangen, also von einem Quadrat Wink

Bei 3D muss man das eher über die Ebenen/Flächen lösen. Eventuell muss auch eine Seite in 2 Dreiecke aufgeteilt werden, damit lassen sich dann vielleicht andere Formeln anwenden. Ist mir aber gerade auch zu hoch.. ^^

	DAK	Fr, Mai 09, 2014 8:10 Antworten mit Zitat
Ich gehe davon aus, dass es möglich ist, aus der Angabe alle Eckpunkte des Quaders zu berechnen. Das Folgende tust du für jede Seite: -Ebene, die durch alle Eckpunkte (z.B. ABCD) der Seite geht, aufstellen (Parameterform) -In Ebenengleichung / Normalvektorform umwandeln -Ebene mit der Geraden schneiden (ergibt Schnittpunkt S). -Gibt es einen Schnittpunkt, musst du herausfinden, ob der Schnittpunkt innerhalb des Vierecks liegt, da die Ebene ja auch aus dem Viereck heraus gehet. Dazu stellst du zwei Dreiecke auf: ABS und CDS (Reihenfolge ist wichtig!) und erstellst für beide Normalvektoren und normalisierst sie (dividierst sie durch ihre Länge). Sind diese beiden Normalvektoren identisch, dann hast du einen Schnittpunkt. Dann musst du nur von allen gefundenen Schnittpunkten den suchen, der sich am Nächsten zu dem Startpunkt der Geraden befindet. Solltest du mit irgendeinem der Schritte Probleme haben, frag noch mal nach
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Fr, Mai 09, 2014 8:10
Antworten mit Zitat

Ich gehe davon aus, dass es möglich ist, aus der Angabe alle Eckpunkte des Quaders zu berechnen.
Das Folgende tust du für jede Seite:
-Ebene, die durch alle Eckpunkte (z.B. ABCD) der Seite geht, aufstellen (Parameterform)
-In Ebenengleichung / Normalvektorform umwandeln
-Ebene mit der Geraden schneiden (ergibt Schnittpunkt S).
-Gibt es einen Schnittpunkt, musst du herausfinden, ob der Schnittpunkt innerhalb des Vierecks liegt, da die Ebene ja auch aus dem Viereck heraus gehet. Dazu stellst du zwei Dreiecke auf: ABS und CDS (Reihenfolge ist wichtig!) und erstellst für beide Normalvektoren und normalisierst sie (dividierst sie durch ihre Länge). Sind diese beiden Normalvektoren identisch, dann hast du einen Schnittpunkt.

Dann musst du nur von allen gefundenen Schnittpunkten den suchen, der sich am Nächsten zu dem Startpunkt der Geraden befindet.

Solltest du mit irgendeinem der Schritte Probleme haben, frag noch mal nach

Gewinner der 6. und der 68. BlitzCodeCompo