Seil entlang von Geraden

Computer: Software & Programmierung Programmierung allgemein
#1

Hi,
ich habe folgendes Problem in 3D:
Geben sei eine Raumkonstellation aus n Geraden, die Jeweils durch Start und Endpunkt definiert sind. Nun soll zwischen zwei Punkten A und B ein elastisches Seil gespannt werden, dass ALLE Geraden so berührt, dass das Seil die kürzest möglichste Länge hat.
Klar suche ich nicht den Ausgereifen Algorithmus, aber vielleicht Ideen, wie man daran gehen könnte. Vielleicht kennt jemand ein vergleichbares Problem, wo ich mir Tipps holen könnte.

Danke für alle Tipps

#2

Hallo Aldaris,

ich habe folgendes Problem in 3D:
Geben sei eine Raumkonstellation aus n Geraden, die Jeweils
durch Start und Endpunkt definiert sind. Nun soll zwischen
zwei Punkten A und B ein elastisches Seil gespannt werden,
dass ALLE Geraden so berührt, dass das Seil die kürzest
möglichste Länge hat.

Mein Ansatz:

  1. Die kürzeste Verbindung zwischen einem Punkt und einer Geraden ist das Lot von diesem Punkt auf die Gerade (gilt wohl auch im Raum).
    Also fällst Du vom Punkt A aus das Lot auf alle n Geraden, oder, mit anderen Worten, Du berechnest den Abstand des Punktes A zu allen n Geraden. Von diesen wählst Du die kürzeste Entfernung. Wenn wir die so ausgezeichnete Gerade n1 nennen und den Schnittpunkt des Lotes mit der Geraden A1, dann ist die Strecke A-A1 der erste Abschnitt deines Seiles.
    Dann nimmst Du diesen gefunden Punkt als neuen Ausgangspunkt, d.h. Du berechnest wieder die Entfernungen (das Lot) des Punktes A1 von allen n-1 restlichen Geraden. Davon wählst Du wieder die kürzeste Entfernung aus, erhälst dami die Gerade n2 mit dem Schnittpunkt A2. Somit läuft dein Seil jetzt von A-A1-A2. Und so weiter und so weiter, bis Du zum Schluß das Seil über alle kürzesten Entfernungen läuft: A-A1-A2…A(n-1)-An-B. Die Summe aller kürzesten Entfernungen ist dann auch die kürzeste Entfernung überhaupt und das Seil berührt, wie gefordert, alle Geraden.
    Mathematisch noch nicht so sauber bewiesen, aber es sollte richtig sein. Ob dieser Ansatz programmtechnisch der eleganteste ist, sei auf jeden Fall dahingestellt. Er ist aber auf jeden Fall lösbar, mit ein wenig Analytischer Geometrie des Raumes und einer einzigen Formel, nämlich der Formel über den Abstand eines Punktes von einer Geraden im Raum
    http://sites.inka.de/picasso/Cappel/abstand.html#PG
    http://www.schoenbuch-gymnasium.de/oberstufe/mathema…
    http://www.mathe-cd.de/6_Vektoren/63-67_Vektorgeomet…

und noch öfters…

Viele Grüße
Marvin

#3

Hallo Aldaris,

hab zwar den Tipp von Marvin nicjt verstanden, aber hatte mal ne ähnliche Diskussion in 2D. Was noch zu bedenken ist: Sollen wirklich alle Greaden berührt werden? Es ging damals um Schallwellen. Also hohe Wand direkt daneben, dann kann ich den kleine Baum dahinter ignorieren sofern danach ein größerer Baum kommt. Ein Gummiband würde nämlich nicht in das Tal fallen sondern müßte sozusagen „runtergezogen“ werden. Der tiefe Punkt kann also entfallen, was die Gesamlänge reduziert.

mfg

Dirk.Pegasus

#4

Hallo Aldaris

hab zwar den Tipp von Marvin nicjt verstanden…

wenn es dir genauso geht, ruhig melden. Ich versuche es gern, nochmal anders zu erklären.

Viele Grüße
Marvin

#5

Hallo Marvin,

danke für das Angebot, aber der Bedarf besteht zum Glück nicht mehr.

Wir hatten damals eine iterative Lösung überlegt. Also sukzessive einen Punkt mehr nehmen, alle alten, wegen des „Durchhangs“ kontrollieren, nächster Punkt. Aber ob mein Freund das dann so realisiert hat kann ich nicht mehr sagen.

biba

Dirk.Pegasus

#6

Hallo Marvin,

das hört sich nach einem Minimalgerüst an. Aber ich glaube, daß nicht die optimale Lösung gefunden wird.

Stelle Dir folgende Konstellation vor: Du sitzt mit dem Rücken zur Wand in einem Raum. Eine Gerade läuft von der hinteren, oberen, linken Ecke in die vordere, rechte, untere Ecke (blöd zu beschreiben :wink:). In der vorderen, rechten, unteren Ecke sind noch zwei, drei sehr kurze Geraden.

Startpunkt bist Du und Endpunkt die vordere, rechte, untere Ecke. Bei entsprechenden Raumdimensionen und Geradenverläufen kann ich mir vorstellen, daß das kürzeste Lot, dasjenige ist, das zur raumdurchspannenden Geraden läuft. Der Schnittpunkt liegt aber mitten im Raum und erfordert für den weiteren Verlauf den Weg zu den weiteren kleinen Geraden. Würde gleich das Seil gleich zu einer kurzen Geraden laufen, ist der Weg kürzer, da die große Gerade ja auch irgendwo in der Ecke berührt werden kann.

Trotzdem stellt Dein Algorithmus eine gute Näherung dar.

Gruß
Newlukai

#7

Hallo,

ich habe folgendes Problem in 3D:
Geben sei eine Raumkonstellation aus n Geraden, die Jeweils
durch Start und Endpunkt definiert sind. Nun soll zwischen
zwei Punkten A und B ein elastisches Seil gespannt werden,
dass ALLE Geraden so berührt, dass das Seil die kürzest
möglichste Länge hat.
Klar suche ich nicht den Ausgereifen Algorithmus, aber
vielleicht Ideen, wie man daran gehen könnte. Vielleicht kennt
jemand ein vergleichbares Problem, wo ich mir Tipps holen
könnte.

Entweder habe ich das Problem nicht verstanden - oder
ich stelle mir das zu einfach vor :wink:

  • Zwischen allen Strecken: (minimal-)Abstände bestimmen und speichern.
  • Alle (minimal-)Abstände v. Startpunkt zu Strecken bestimmen.
  • Eine Sequenz dieser gefundenen Abstandsstrecken aufschreiben,
      die alle benötigten Strecken ein mal enthalten und
      die Randbedingungen (Start/Endpunkt) beachten.
  • So lange solche Sequenzen aufsuchen, bis die kürzeste gefunden ist.

Grüße

CMБ

#8

Hallo und schonmal Danke für alle Tipps.

Ich habe vergessen zu sagen, dass die Geraden sortiert sind, das heißt ich habe z.B. 5 Geraden, weis aber bereits, in welcher Reihenfolge diese durchlaufen werden müssen[Randbedingung].

Rein Mathematisch müsste man etwas in der Art Machen:

Man definiert die 5 Geraden jeweils als Punkt mit einer Variablen [Start +a*(End-Start)]. Dann bestimmt man die Abstände zwischen der Elementen:

r1 = Quelle - [[Start1 +a*(End1-Start1)]]
r2 = [Start2 +b*(End2-Start2)] - [Start1 +a*(End1-Start1)]
r3 = [Start3 +c*(End3-Start3)] - [Start2 +b*(End2-Start2)]
r4 = [Start4 +d*(End4-Start4)] - [Start3 +c*(End3-Start3)]
r5 = [Start5 +e*(End5-Start5)] - [Start4 +d*(End4-Start4)]
r6 = Senke - [Start5 +e*(End5-Start5)]

Die Summe über diese r_i
r = r1 + r2 +r3 +r4 +r5 +r6 ist nun eine funktion von 5 veränderlichen, die es entsprechend zu minimieren gilt. [a…e=0…1]

Aber das kann ja kein Rechner ZÜGIG rechen.

Hoffe habe das Problem jetzt korrekt beschrieben.

Danke für weiter Hilfe

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#9

Hallo Newlukai,

das hört sich nach einem Minimalgerüst an. Aber ich glaube,
daß nicht die optimale Lösung gefunden wird.

Ja, ich hatte auch die ganze Zeit das Gefühl, daß nach meinem Algorithmus eine optimale Lösung nicht garantiert ist. Deshalb hatte ich auch geschrieben, daß das mathematisch wohl nicht ganz sauber ist. Aber erstens haben sich die Randbedingungen etwas verändert (geordnete bzw. nummerierte Geraden) und zweitens ist suboptimal auch ganz schön :wink:
Aber eine andere Frage: Die ganze Zeit habe ich den Gedanken im Hinterkopf, daß die Aufgabenstellung dem Traveling Salesman Problem (Problem des Handlungsreisenden) entspricht, nur eben im Raum und ohne Rückkehr zum Ausgangsort. Liege ich da falsch?

Viele Grüße
Marvin

#10

Hallo Marvin,

Aber eine andere Frage: Die ganze Zeit habe ich den Gedanken
im Hinterkopf, daß die Aufgabenstellung dem Traveling Salesman
Problem (Problem des Handlungsreisenden) entspricht, nur eben
im Raum und ohne Rückkehr zum Ausgangsort. Liege ich da
falsch?

Das ist mal eine gute Frage. Ich würde Dir erst mal zustimmen. Hört sich tatsächlich so an. Allerdings frage ich mich dann, warum der Travelling Salesman eigentlich nicht mit der Suche nach dem Minimalgerüst lösbar ist. Ich habe n Orte, die Entfernungen zu den Orten, lassen wir den Graphen mal ungerichtet sein … Das muß ich mal noch rausfinden.

Gruß
Newlukai