hey hat sich einer von euch schonmal die mühe gemacht und ne function überlegt die einem den kürzesten abstand zwischen zwei linien berechnet.

gegeben seien zwei linien die nicht parallel sind und sich nicht schneiden.
gesucht ist der kürzeste abstand.

_________________
www.extrawurst.org

Es ist unmöglich, den abstand zweier nichtparalleler Linien zu berechnen. Man kann maximal den Abstand zweier Punkte berechnen, denn der wäre ja bei Parallelen überall der selbe.

Auf anhieb wäre meine Idee, einfach jeden Punkt durchtesten und abstand ueber den dreidimensionalen Pythagoras ausrechnen.
Das wär aber sicher mega rechenintensiv.
Nächste Idee:
Anfang und Endpunkte auf Abstände prüfen. => weniger rechenintensiv, aber windschiefe geraden werden nicht erfasst.

vllt optional noch einige zwischenpunkte einbeziehen

doch das funktioniert. die frage ist nur: sind linien geraden oder strecken? für geraden kann man es prima machen, aber dieser abstand ist ggf. kürzer als der zwischen 2 linien. über den abstand von 2 strecken habe ich mir bislang noch keine gedanken gemacht - leider sind hier die bedingungen weniger schön zu verbraten, lässt sich aber auch machen. also die variante für geraden:

http://mupad.zum.de/schule/material/not ... im-R3.html

Die Streckenvariante ist etwas anders, aber nicht unlösbar - um den Einsatz von etwas Papier und Bleistift wird man aber nicht umhinkommen.

ja es geht um den abstand von 2 strecken.
strecke1(A nach B) und strecke2(C nach D).
Wohlgemerkt nur im R2 also 2D.
Klar muss es gehen, aber als ich mit zettel und stift dran gegangen bin hab ich gemerkt wieviele sonderfälle beachtet werden müssen, deshalb dachte ich ich frag ma ob da schon jemand erfahrung hat.

_________________
www.extrawurst.org

Meine idee wäre, dass man sich ein paar Anregung aus dem Quicksortalgorythmus besorgt

Man teilt die Strecke in der Mitte und nimmt dann noch je einen Punkt etwas weiter links und einen etwas weiter rechts, davon. Jeweils wird der Abstand berechnet. Ist der Abstand des Linken Punktes zum Mittelpunkt kleiner als der des anderen Punktes zum Mittelpunkt, dann muss der kürzeste Abstand irgendwo auf der linken Seite sein, andernfalls auf der Rechten. Ist er auf der Linken wird die Linke wieder halbiert und berechnet, ist er auf der Rechten, dann eben auf der Rechten. Das kann man zb über eine Rekursive Funktion machen, die die Rekursionstiefe soweit aufbaut, bis man den letzten Punkt hat, der den kürzesten Abstand verkörpert und voila

Hier meine Idee.

Fakt ist die Linien bestehen nicht aus unendlich vielen Punkten(wie normalerweise), da sie auf dem display aus pixel bestehen.
Also kann man mit dem guten altem Bresenham jeden Pixel, der Strecken, ermitteln.
Nun kann man den Aktuellen Pixel mit den Pixeln der anderen Strecke vergleichen.
Sehr aufwendig aber da kann man denke noch ein Algo finden, um es zu verkürzen.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Es wurde nichr "Der Abstand" sondern "Der kürzesten Abstand" zwischen zwei belibig im Raum liegenden geraden gefordert. Diese Strecke muss zu beiden Geraden senkrecht stehen. Nun das Dumme an der Sache: Egal wie man es dreht kommt ein gleichungsystem mit 6 unbekannten raus.
Etwas einfacher ist es den Abstand eines Punktes zu einer geraden zu berechnen. Mit hilfe eines Kreutzproduktes von einem beliebiegem Punkt auf der Geraden und dem gegebenem Punkt lässt sich der Punkt auf der geraden finden, der dem gegebenem Punkt am nächstem ist.

Um den Abstand zweier geraden zu berechnen müsste man das in ein gleichungsystem zusammensetzten und auflösen. Dann hätte man die chance es mit relativ wenig aufwand die beiden Punkte zu finden, die die endpunkte der kürzesten Strecke sind

nein oc2k1, wir sind in 2D. Mein Beitrag war daher acuh verkehrt, aber der Abstand von 2 Geraden lässt sich prima berechnen.

Aber wie gefordert sind die Geraden nicht parallel, und schneiden sich nicht... verlängert man sei zu Geraden haben sie aber einen Schnittpunkt. Also kann ich ein Dreieck zecihen, so daß beide Strecken auf den Schnekeln liegen und der Schnittpunkt der Geraden zu einer der Ecken. Nun kann ich von jedem Punkt der einen Gerade die Abstandsfunktion definieren, die mir beschreibt, wie groß der Abstand dieses Punktes zu einem parametrisierten Punkt der anderen Gerade ist, also:

Seien die Strecken: S1 := [P1, P2]; S2 := [P3, P4]
Seien V1 := P2 - P1; V2 := P4-P3; die Richtungsvektoren.
Den Schnittpunkt der Geraden wollen wir M nennen und P1 liege näher an M als P2, sowie P3 näher an M als P4. Siehe Bild.

Betrachten wir dann folgende Abstandsfunktion:
f1(lambda, x) := || P1 + V1 * lambda - x||^2
Für festes x misst diese also den Abstand von x zu einem Punkt auf der Geraden durch S1. Es handelst sich dabei offensichtlich um eine nach oben geöffnete Parabel. Diese ist leicht abzuleiten und das Minimum zu bestimmen. Für jeden Punkt können wir also sehr leicht den Minimumabstand bestimmen (Wurzelziehen am Ende nicht vergessen.)

O.B.d.A. sei ||P1-M||<=||P2-M|| wie im Bild. Dann ist der nächste Punkt von G2 zu P1 gerade die Orthoproj. von P1 auf G2, also K1. Gehe ich auf G2 nach rechts, so wird die Verbindungsstrecke nur länger (Parabel). Zur Strecke ist also die Kürzeste Verbindung die [P1,P3]. Das gilt jedoch genauso für jeden Punkt von P1 bis L1. Offensichtlich liegt dann auf [L1,P2] keiner der Randpunkte der gesuchten Strecke, weil das Dreieck sich von L1 ja nur weiter öffnet.

Selbes spiel lässt sich genauso für die andere Seite machen udn man stellt fest, daß die Kürzeste Verbindung zwsichen den Strecken S1, S2 irgendwo in [P1,L1] und [K1,P3] liegt. Weil aber [K1,P3] geschnitten mit S2 gerade der Punkt P3 ist, weiß ich, daß der Randpunkt P3 einer der Randpunkte der Gesuchten Verbindung ist.
Die einzige Voraussetzung die wir gemacht hatten war, daß ||P1-M||<=||P2-M||. Anders herum ||P1-M||>||P2-M|| trifft dies analog auf P1 zu - also immer einer der Randpunkte die näher an M sind, sind bestandteil der Kürzesten Verbindung. Und voila.
Man bestimme jeweils den Punkt eines Randpunktes auf der anderen Gerade, der den kürzesten ABstand hat (z.B. durch ableiten der obigen Abstandsfkt.). Liegt dieser Punkt in der anderen Strecke, so merke ich mir die entfernung, ansonsten nicht. Das mache ich 4 mal, bis ich alle Entfernungen bestimmt habe. Ich suche mir die kürzeste dieser Entfernungen heraus und fertig bin ich.

Wenns wirklich nur 2D sein soll dann mußt du eigentlich nur die folgenden Strecken berechnen:
- Abstand der Endpunkte zueinander
- Länge der Strecken die Senkrecht auf die Geraden stehen und durch die Endpunkte gehen (falls die Strecke existiert)
Das was davon minimal ist sollte dein kleinster Abstand sein.

Das habe ich da oben beschrieben.

Betrachte es als kurze Zusammenfassung
Wenn man sich erstmal nen Überblick verschaffen will was eigentlich gemacht werden muß.
Man muß ja nicht gleich nen halben Mathematisch Beweis liefern das es so richtig ist.