Hallo, ich stehe vor einer Aufgabe um die kürzeste Strecke zwischen Punkt 1 und Punkt 10 zu berechnen. Gegeben eine Startkoordinate x,y. Weitere 10 Koordinaten. Da die Punkte mit einer Toleranz von nur z.B. 4 cm genau getroffen werden müssen suche ich eine Berechnung der kürzesten Strecke. Also ist um jeden Punkt ein Kreis mit 8cm Durchmesser und gesucht wird jeweils die Koordinate die am Kreis tangiert. Hat jemand Tipps bzw. Quellen so einer Berechnung? Viele Grüße
Josef schrieb: > Da die Punkte mit einer Toleranz von nur z.B. 4 cm genau getroffen > werden müssen suche ich eine Berechnung der kürzesten Strecke. > Also ist um jeden Punkt ein Kreis mit 8cm Durchmesser und gesucht wird > jeweils die Koordinate die am Kreis tangiert. wieso tangiert. Die kürzeste Strecke zwischen 2 Punkten ist eine Gerade. Und wenn du um die Punkte einen Kreis hast, dann ändert das nicht viel. Denn die Gerade ist innerhalb des Kreises ja ein Radiusvektor und der steht immer senkrecht zum Umfang. D.h. die Distanz zu diesem Punkt kann maximal um +- Radius von der rechnerischen Distanz zu diesem Punkt abweichen, wenn der korrekte Punkt innerhalb eines Fehlerkreises rund um den idealen Punkt liegt. Einfach mal aufzeichnen, dann wirds klarer. Ausser natürlich, ich habe deine Aufgabe missverstanden.
Hey, da würde ich mit Vektoren rechnen. Der Abstand von Punkten ist ja relativ simpel. Um die Toleranz zu berücksichtigen kannst du mit 9.3.2 auf der Seite http://www.dieter-heidorn.de/Mathematik/RP_LA_AG2/Kap09_Kreis_und_Kugel/Kreis_und_Kugel.html berechnen. MfG Walleby
Das Problem klingt irgendwie sehr KOMPLEX. Wenn ich das richig verstanden habe sind es ja neun Wegstrecken. Ist die Reihenfolge zwischen den Punkten festgelegt oder soll diese auch in Hinblick auf die kürzeste Strecke optimiert werden? Könntest Du mal eine kleine Graphik beifügen, die Dein Problem etwas näher verdeutlicht. Derzeit würde es meiner Meinung nach auf das Problem des Handlungsreisenden (gerne mal den Wiki-Artikel lesen) hinauslaufen. Wenn Du da wirklich die kürzeste Entfernung berechnen willst, wirst Du nicht um das berechnen fast aller Möglichkeiten herumkommen. Gruß Magelan
Karl Heinz Buchegger schrieb: > Ausser natürlich, ich habe deine Aufgabe missverstanden. das hast Du, er will die Punkte nicht exakt anfahren, es reicht wenn er in 4cm Abstand vorbeifährt
Bernd schrieb: > Karl Heinz Buchegger schrieb: >> Ausser natürlich, ich habe deine Aufgabe missverstanden. > > das hast Du, er will die Punkte nicht exakt anfahren, es reicht wenn er > in 4cm Abstand vorbeifährt Ah. Jetzt hab ichs. Er will eine Sequenz von 10 Punkten nacheinander abfahren und sucht die Distanz, wenn er nicht genau den Punkt anfahrten muss sondern auch zb 4 cm vorher schon umdrehen und zum nächsten Punkt fahren kann. Jau. Das ist wirklich komplex.
Walleby schrieb: > da würde ich mit Vektoren rechnen. Der Abstand von Punkten ist ja > relativ simpel. das schon, aber das klingt nach verschärftem Travelling salesman Problem
Karl Heinz Buchegger schrieb: > Die kürzeste Strecke zwischen 2 Punkten ist eine Gerade. ...aber ich kenn da ne Abkürzung... :-) SCNR Harald
Hausaufgabe Handlungsreisender ? Hat man eine exakte Route, kann man ja nochmal eine 4cm am Innenknick liegende Route ausrechnen.
Bernd schrieb: > Karl Heinz Buchegger schrieb: >> Ausser natürlich, ich habe deine Aufgabe missverstanden. > > das hast Du, er will die Punkte nicht exakt anfahren, es reicht wenn er > in 4cm Abstand vorbeifährt Er sucht also im Grunde genommen folgenden Algorithmus: 1) Die Kreismittelpunkte werden miteinander verbunden und zwar so, dass die Verbindung der Mittelpunkte Kreis1->Kreis2, Kreis2->Kreis3, Kreis3->Kreis4... die optimale kürzeste Distanz bilden. Unter dem Begriff des "Handelsreisenden" wird das Problem über den Ameisenalgorithmus (MMAS = Min Max Ant System) gelöst. 2) Nun ist die Reihenfolge der Kreise bekannt. Es werden die Geraden zwischen den Mittelpunkten gebildet. 3) Es werden die Schnittpunkte der Sekanten gebildet. 4) Die Reihenfolge der Kreise bestimmt die Reihenfolge, mit welcher die Sekantenschnittpunkte abgefahren werden müssen. Et voilàt: Du hast die kürzeste Strecke.
Martin Schwaikert schrieb: > Er sucht also im Grunde genommen folgenden Algorithmus: > > 2) Nun ist die Reihenfolge der Kreise bekannt. Es werden die Geraden > zwischen den Mittelpunkten gebildet. Nur dass sich durch die Möglichkeit auf nur 4cm genau treffen zu müssen unter umständen eine andere Route als die beim klassischen TSP als ideal erweisen kann. Damit ist dein Algorithmus maximal zum Auffinden einer Startlösung für irgendeine Heuristik zu gebrauchen.
Martin Schwaikert schrieb: > 1) ... 4) Das funktioniert natürlich bestenfalls, wenn alle Kreise jeweils mindestens 8cm voneinander entfernt liegen.
Ergänzung: die Kreise schneiden sich nicht und die Reihenfolge ist bekannt.
Josef schrieb: > anbei eine Skizze, gesucht die rote Strecke. Die Strecken durch Punkt 6 (hin und wieder weg) sind hier definitiv falsch. Das geht kürzer, wenn man nicht durch den Mittelpunkt fährt, sondern eine Gerade zieht, die dann irgendwo durch den Kreis des Punktes 6 führt.
Wenn ich mir die Zeichnung ansehe, glaube ich, dass auch schon die ersten beiden Geraden vom Startpunkt aus suboptimal sind. Ich würde folgenden Algorithmus verwenden: 1. Ziehe Geraden von Mittelpunkt zu Mittelpunkt 2. Berechne die Winkelhalbierenden der Geraden Der Punkt für die minimale Wegstrecke liegt dann auf dieser Winkelhalbierenden. Im allgemeinen ist das der Schnittpunkt der Winkelhalbierenden mit dem Kreis. Aber nicht immer, wie man an Punkt 6 sieht. Hier liegt der gesuchte Punkt irgendwo auf der Winkelhalbierenden, da der Öffnungswinkel der beiden Geraden sehr groß ist. Aber das ist nur noch ein simples Minimax-Problem und leicht mit Trigonometrie zu lösen. Wie ich auf Winkelhalbierende komme? Einfach aus Symmetrieüberlegungen. Die gezeichnete rote Linie ist garantiert nicht optimal. Da sind viel zu viele Asymmetrien drin.
Ich würde es so lösen: - Gerade von P1 zu P3 - Abstand der Geraden zu P2 ermitteln (Senkrechte auf der Geraden durch P2) - Wenn der Abstand <4cm, dann diesen Punkt als neuen P2 speichern - Wenn der Abstand >4cm ist, dann ist P2 der Schnittpunkt vom Kreis (P2) und der Senkrechten. Und dann das selbe mit P2 zu P4 usw. Ist zwar noch nicht perfekt, aber nahe am Maximum. Gerade wenn mehr als 3 Punkte in reihe sitzen (wie bei P6 im Beispiel) kann es zu Abweichungen kommen.
@Josef Ist die Skizze, die Du hier eingestellt hast nur ein Beispiel? Ändern sich die Positionen der Punkte von Lauf zu Lauf oder sind diese im Vorfeld festgelegt? Wie auch immer... die kürzeste Strecke zu berechnen ist ein NP-vollständiges Problem (Stichwort "Problem des Handlungsreisenden" o. englisch "Traveling Salesman Problem"). D. h. die Laufzeit des Algorithums ist min. exponentiell, wenn Du die optimale Strecke mit Sicherheit finden willst. Das gilt bereits schon dafür in welcher Reihenfolge Du die Puntke anfahren sollst um am Ende die kürzeste Strecke zu erhalten. Die Sache mit dem Radius um alle Punkte macht die Sache dann noch ein Stück komplexer. Gruß Christoph
@Josef Sehe gerade, dass Du geschrieben hast, dass die Reihenfolge bekannt ist. Dann sieht das Problem schon etwas anders aus... sehr interessant :) Gruß Christoph
> die Reihenfolge ist bekannt Lösung also kindereinfach und schon beschrieben. > Wie ich auf Winkelhalbierende komme Aus völlig richtigen Überlegungen. > dass auch schon die ersten beiden Geraden vom Startpunkt > aus suboptimal sind. Unsauber gezeichnet. Insgesamt klingt das aber sehr nach primitiver Hausaufgabe, bei der er seine eigenen Gehirnwindungen aktivieren soll, wenn er welche hat.
Meine Idee um den optimalen Weg zu finden: Gedanklich steckt in jedem Kreis ein Pinn, der innerhalb des Kreises ohne Widerstand bewegt werden kann. Start und Ziel erhalten auch je einen Pinn, die aber fest sind. Die Pinne werden in der vorgegebenen Reihenfolge mit einem "Gummi" (unter Spannung) miteinander verbunden. Das Gummi zieht sich nun zusammen und die Pinne sollten dann innerhalb der Kreise die Position einnehmen, die optimal für die kürzeste Strecke ist. Das Gummi zeigt unter der geringsten Spannung die kürzeste Strecke an. Jetzt muss man das nur in Code giessen ;) Gruß Christoph
Der Kreis kann durch eine Funktion beschrieben werden... wenn man jetzt davon ausgeht dass man jeden Punkt im Kreis durch eine Funktion berechnen kann mit 2 Variablen(Winkel+Länge) kann man die gesamt Strecke mit 10*2 also 20 Variablen ausdrücken, und diese Funktion muss man dann einfach möglichst klein kriegen
MaWin schrieb: > Handlungsreisender Travelling actor's problem ;) Was tu ich nur, wo fahr ich hin! Die Idee mit den Pins ist schon mal nicht schlecht und entspricht doch Franks Idee... Frank M. schrieb: > Ich würde folgenden Algorithmus verwenden: > > 1. Ziehe Geraden von Mittelpunkt zu Mittelpunkt > 2. Berechne die Winkelhalbierenden der Geraden ...wobei der 5. Kreis entfernt werden muss, da der Weg über die Mittelpunkte der Kreise den Kreis 5 derart schneidet, dass die gesamte Entfernung größer würde, würde man ihn nur am Rand anfahren. mfg mf
Hat das irgendwas mit Mikrocontrollern zu tun? Warum wird sowas nicht unter "Offtopic" gepostet?
ICFP Programming Contest 2003 (da sollten sich noch einige Ansätze finden lassen)
Angehängte Dateien:
-
optimaler-weg.png
6,8 KB
Frank M. schrieb: > 1. Ziehe Geraden von Mittelpunkt zu Mittelpunkt > 2. Berechne die Winkelhalbierenden der Geraden > Wie ich auf Winkelhalbierende komme? Einfach aus Symmetrieüberlegungen. > Die gezeichnete rote Linie ist garantiert nicht optimal. Die Überlegung mit den Winkelhalbierenden und den Symmetrien ist prinzi- piell richtig. Allerdings darfst du dabei nicht die Winkelhalbierenden der Verbindungslinien zwischen den Kreismittelpunkten betrachten, son- dern diejenigen der Liniensegemente des Lösungwegs. Das macht die Sache komplizierter, weil man die Winkelhalbierenden erst dann bestimmen kann, wenn man die Lösung bereits kennt. Der optimale Weg ist also ein Polygonzug, bei dem für jeden der zu passierenden Kreise bis auf den letzten eine der beiden folgenden beiden Aussagen gilt: 1. Er geht geradlinig durch den Kreis hindurch. 2. Er führt auf einer Geraden a zu einem Punkt P auf dem Kreisumfang und biegt dort in eine Gerade b ab, so dass der Kreisradius durch P den Winkel zwischen a und b halbiert. Der letzte Kreis wird in Richtung seines Mittelpunkts angefahren, wobei der Weg an seinem Umfang endet. Ich habe mal mit Kig ein Beispiel konstruiert (s. Anhang), dabei aller- dings ein wenig geschummelt, da ich den letzten Kreis so platziert habe, dass sein Mittelpunkt auf dem zuvor konstruierten Weg liegt und nicht umgekehrt, wie es eigentlich der Aufgabenstellung entspricht (Hätte ich es ohne Schummeln geschafft, wäre aus der Konstruktion ein direktes Lösungscerfahren abgefallen). Mit den genannten Kriterien kann zwar ein gegebener Weg auf Optimalität geprüft werden, sie liefern aber leider kein Verfahren, diesen Weg di- rekt zu berechnen oder zu konstruieren (zumindest ist mir diesbezüglich nichts eingefallen). Ich vermute, dass es bei zwei oder mehr Knicken im Weg keine geschlossene Lösungsformel für das Problem gibt. Es führt also wohl kein Weg an einer numerischen Lösung mittels eines Iterationsverfahrens vorbei. Man könnte bspw. die Startrichtung des Wegs so lange variieren, bis nacheinander alle Kreise in der richtigen Rei- henfolge getroffen werden. Dabei wird vom Startpunkt aus immer so viel des Wegs berechnet, bis er einen der Kreise verfehlt. Je nachdem, ob der Weg links oder rechts an dem Kreis vorbeiläuft, und ob die Anzahl der bisherigen Richtungsänderungen gerade oder ungerade ist, muss der Start- winkel für die nächste Berechnung um einen geeigneten Betrag vergrößert oder verkleinert werden. Wenn der Weg schließlich auch den letzten Kreis passiert, wird noch so lange weiteroptimiert, bis der Weg exakt durch seinen Mittelpunkt verläuft. Von dem so gefundenen Weg wird dann noch der Radius des letzten Kreises weggelassen, weil es ja genügt, dessen Umfang zu erreichen. Der gefundene Weg entspricht übrigens dem eines Lichtstrahls, der vom Startpunkt ausgesandt wird, an mehreren halbdurchlässig verspiegelten Zylindern (die Kreise) reflektiert wird oder diese brechungsfrei durch- dringt und schließlich durch den Mittelpunkt des letzten Kreises ver- läuft. Man könnte also das oben beschriebene rechnerische Verfahren auch physi- kalisch realisieren, in dem man am Startpunkt einen Laserpointer drehbar moniert, alle Kreise bis auf den letzten durch halbdurchlässig verspie- gelte Zylinder ersetzt und den Laserpointer so lange dreht, bis der Strahl genau ins Ziel fällt. Der gesuchte Weg ist dann der Weg des Strahls, den man mit etwas Nebel oder Rauch sichtbar machen kann. Alternativ könnte man statt des Laserpointers eine punktförmige, aber nicht bündelnde Lichtquelle (kleine LED o.ä.) nehmen und am Zielpunkt eine kleine Kamera platzieren. Der Punkt, an dem die Lichtquelle im letzten Zylinder erscheint, wird auf diesem markiert und die Kamera anschließend an diese Position gestellt. Dann wird der Punkt markiert, an dem die Lichtquelle im vorletzten Zylinder erscheint. So wird fort- gefahren, bis alle Zylinder markiert sind. Der gesuchte Weg führt dann vom Startpunkt über die markierten Punkte zum Ziel. Es muss allerdings in beiden Varianten dafür gesorgt werden, dass der Strahl die einzelnen Zylinder tatsächlich nur in der vorgesehenen Rei- henfolge durchläuft, sonst gelangt das Licht u.U. auf mehreren Wegen zum Ziel. Da man den optimalen Weg aber ungefähr vorhersehen kann, hilft es evtl., zwischen den Zylindern geeignete Blenden aufzustellen, die die Reflexion in "falsche" Richtungen unterbinden. Nur aus Interesse noch ein paar Fragen an Josef: - Wozu dient das Ganze überhaupt? - Soll die Berechnung tatsächlich auf einem Mikrocontroller stattfinden? - Wie sind die zeitlichen Anforderungen? MaWin schrieb: > Lösung also kindereinfach und schon beschrieben. Ich habe doch schon immer gewusst, dass du als Wunderkind geboren bist ;-)
Karl Heinz Buchegger schrieb: > wieso tangiert. Weil er die Punkte nicht reffen muss, sondern nur, ihnen nahekommen muss. WelchenPunkt er dabei durchfahren muss ist aber nicht direkt berechenbar, sondern muss aus der Umgebung abgeleitet werden. Die Lösung ist einfach: Man bestimmt die Gerade der Nachbarpunkte allgemein, hat daraus die Steigung und somit die Tangente für den Fall verschiederer Kreispunkte. Diese Distanz muss so ermittelt werden, dass sie minimal ist (Ableitung = null). > Die kürzeste Strecke zwischen 2 Punkten ist eine Gerade. Dies gilt dann, wenn diese Gerade den Kreis von oben schneidet. Man muss davon ausgehen, dass das zuminstes in jedem zweiten Punkt der Fall sein muss, da sich sonst keine Geradenstäcke finden lassen, die bei allen Zwischenpunkten zu einer Lösung führen.
Yalu X. schrieb: > Man könnte also das oben beschriebene rechnerische Verfahren auch physi- > kalisch realisieren Wow, ich hab bis jetzt an einen amerikanischen Zeitungsjungen auf einem Fahrrad gedacht, der nur begrenzt weit werfen kann, aber möglichst schnell seine Runde durch den noch nicht/nicht mehr so dicht besiedelten Trailerpark nehmen will. :) mfg mf
Joachim минифлоть schrieb: > Die Idee mit den Pins ist schon mal nicht schlecht und entspricht doch > Franks Idee... Ich fürchte, dass die beiden Ideen sich nicht entsprechen. Die Idee mit den Winkelhalbierenden funktioniert eigentlich nur für drei Punkte. Jeder weitere Punkt bzw. dessen Position hat nämlich nicht nur eine direkte Auswirkung auf die Winkelhalbierenden, an denen er beteiligt ist, sondern indirekt auch auf alle Winkelgeraden im System. D. h. bei Verschiebung des sechsten Punktes/Kreises in der Skizze gebe es eine direkt Auswirkungen auf die Winkelhalbierende zw. den Punkten [4, 5, 6], [5, 6, 7] und [6, 7, 8]. Aber auch indirekte Auswirkungen zw. den Punkten [3, 4, 5], [7, 8, 9] usw. Wobei der Effekt (die Größe der notwendigen Korrektur von bestimmten Geraden) mit zunehmender Entfernung abnimmt. Die Folge ist, dass wir hier bei einem iterativen Vorgehen landen, bei dem nach Zunahme eines neuen Punktes (bzw. der Verschiebung eines Punktes) alle bisherigen Geraden neu berechnet werden müssen. Und zwar solange iterativ bis eine vorher festgelegte Genauigkeit erreicht ist. D. h. die Längenverbesserung der gesamten Strecke bei zwei aufeinanderfolgenden Iterationen liegt unterhalb eines festgelegten Schwellwertes. Damit kriegt man eine Annährung an die optimale Strecke hin. Ist auf jeden Fall eine schöne Aufgabe und ich hoffe, dass meine Erklärung verständlich ist;) PS.: Der Thread gehört wirklich nicht in diesen Bereich.
> Man bestimmt die Gerade der Nachbarpunkte allgemein, hat daraus die > Steigung und somit die Tangente für den Fall verschiederer Kreispunkte. > Diese Distanz muss so ermittelt werden, dass sie minimal ist (Ableitung > = null). Wobei die Knickpunkte (x_i, y_i) ja alle jeweils innerhalb einer der abgeschlossenen Kreisscheiben liegen. Wenn Punkt i jetzt um weniger als den doppelten Kreisradius von der Verbidungsgerade zwischen Punkt i-1 und Punkt i+1 entfernt liegt, kommen sowohl Punkte im Innern als auch Punkte auf der Kreislinie in Frage. Mathematisch gesehen lässt sich das nicht in einen Ausdruck pressen, der mittels Ableitung minimiert wird, es geht also nicht ohne Fallunterscheidung. Und zwar für jeden einzelnen Punkt. Damit haben wir bei n Punkten, wobei Punkt 1 und Punkt n genau getroffen werden sollte, 2^(n-2) Fälle zu unterscheiden (wir reden noch von einer festgelegten Reihenfolge!) Wenn n nicht ganz klein ist, geht es damit also schon mal nicht "ganz einfach", zumindest nicht wenn eine endliche ;-) Laufzeit des Programms gewünscht wird. Evtl. kann man aber einige Fälle von vornherein eliminieren (wo es mit dem lotrechten Abstand nicht hinhaut). Mein Ansatz wäre folgender, der zu einer Näherungslösung führt: 1. Linie als Knickgerade initialisieren, die alle Punkte genau trifft 2. Nacheinander für jeden Punkt von 2. bis zum n-1-ten den Eckpunkt innerhalb des Spielraums so versetzen, dass die Länge der beiden angrenzenden Abschnitte minimiert wird. 3. Nachdem in (2) über alle Eckpunkte iteriert wurde, selbiges noch k-mal wiederholen. Je höher k, desto besser die Lösung.
Angehängte Dateien:
-
optimier.gif
11 KB
Ich früchte man muss da alle Punkte gleichzeitg reinnehmen. Es ist ein nterschied, ob es mit einem nächsten Punkt in die eine, oder andere Richtung knickt. Am Besten man versucht zunächst, durch alle Punkte mit einer Gerade durchzugehen und bricht diese Kette dort, wo der grösste Abstand ist. Von dort aus untersucht man das in zwei Teilproblemen, u.s.w Es wird jeweils der Punkt neu bestimmt, der das grösste Problem darstellt.
Angehängte Dateien:
-
optimiert.gif
9,3 KB
Orange ist die erste lösung türkis die beiden zweiten und gruen die letzte es kann natürlich sein, das es bei komplexeren Aufrüchen mehrere Lösungswege gibt, die dann zu unterschiedlichen Teillösungen führen. dann müsste man am Ende die kürzeste suchen
Josef schrieb: > anbei eine Skizze, gesucht die rote Strecke. Lässt sich die Strecke folgendermassen charakterisieren? - Der jeilige Kreisradius ist Winkelhalbierende den an diesen Kreis ankommenden / wegführenden beiden Teilstrecken. Oder ist meine mathematische Ituition falsch...? Lässt sich zB anhand eines optimalen Weges zeigen, daß obige Bedingung nicht erfüllt ist?
Hallo, die optimierten Punkte habe ich über Winkelhalbierende berechnet. Der Sonderfall dass eine Linie durch einen Kreis geht wie bei Punkt6 vom Beispiel soll durch die Prüfung geht die Gerade durch Kreis geprüft werden.
1 | U8 circleLineIntersect(float x1, float y1, float x2, float y2, float cx, float cy, float cr ) |
2 | {
|
3 | float dx = x2 - x1; |
4 | float dy = y2 - y1; |
5 | float a = (dx * dx) + (dy * dy); |
6 | float b = 2 * ((dx * (x1 - cx) + dy * (y1 - cy))); |
7 | float c = (cx * cx) + (cy * cy); |
8 | c += (x1 * x1) + (y1 * y1); |
9 | c -= 2 * ((cx * x1) + (cy * y1)); |
10 | c -= cr * cr; |
11 | float bb4ac = (b * b) - (4 * a * c); |
12 | |
13 | if (bb4ac < 0) |
14 | {
|
15 | return FALSE;// Not intersecting |
16 | }
|
17 | else
|
18 | {
|
19 | return TRUE;//intersecting |
20 | }
|
21 | }
|
das Ergebnis stimmt aus dieser Funktion nicht immer. Habe ich da einen Denkfehler?
Thread beobachten
Seitenaufteilung abschalten
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.