Jump to content

Frage an die "Mathe-Genies"


 Share

Recommended Posts

  • Developer

Hallo,

ich wende mich heute mal mit dieser Frage an alle "Mathe-Genies", die vielleicht helfen können, folgende Herleitung zu beantworten:

Es geht um die Berechnung des Fahrweges eines Fahrzeuges zwischen zwei bekannten Punkten A nach B.

Für die spätere Berechnung der Bewegung ist es am einfachsten, den Fahrweg in Kreissegmenten zu beschreiben, dh. folge einem Kreisbogen mit Radius r für s Meter (also s ist der Länge des Kreisbogens vom Radius r)

Eine Bewegung zwischen zwei Punkten ist dann in der Regel über zwei Kreisbögen beschreibbar. Ein paar Sonderfälle gibt es, zum Beispiel wenn der Punkt B auf der direkten Richtungsachse des Punkte A liegt, dann sind die Radien der zwei Kreisbögen unendlich groß, es wird also eine Gerade draus. Die kann

aber durch eine Prüfung vorher ausgeschlossen werden.

Mein Problem besteht nun darin, die Radien der beiden Kreise zu ermitteln, so das die Bewegung durchgeführt werden kann. Folgende Ausgangssituation ist bekannt:

Der Ausgangspunkt A wird der einfachheithaber in den Koordinaten Ursprung (0,0) gelegt und die Richtung des Fahrzeugs ist 0 (also nach Norden entlang der Y-Achse). Der Zielpunkt B ist mit einem X/Y Offset zum Punkt A bekannt, sowie die Richtung des Fahrzeugs am Zielpunkt, also der Winkel in B.

post-77-124887042758_thumb.jpg

Werden nun zwei Kreise so gelegt, dass der Punkt A ein Tagentenpunkt am Kreis 1 ist und der Punkt B ein Tangentenpunkt am Kreis 2, so müssen nun die Radien r1 und r2 so bestimmt werden, dass es genau einen "Berührungspunkt" beider Kreise gibt. Dieser Berührungspunkt ist also Tangentenpunkt beider Kreise mit gleicher Steigung. Damit kann dass Fahrzeug dann dem Kreisbogen s1 bis zu diesem Berührungspunkt folgen und dann dem Kreisbogen s2 bis zum Zielpunkt.

Mein Problem besteht nun darin, eine Formel zu erstellen, die die Errechnung von r1 und r2 ermöglicht. Hier reichen meine eingerosteten Mathekenntnisse nicht aus.

Noch ein Punkt ist wichtig: Die Berechnungsformel sollte (wenn das möglich ist), neben den Grundrechenarten nur trigonometrische Funktionen (Sin,Cos,Tan, arcSin, arcCos, sowie x hoch y oder Wurzel enthalten, da diese zur Berechnung zur Verfügung stehen. Martixberechnung etc. sind etwas schwierig umzusetzen in den Programmcode.

Vielleicht hat ja demand einen Ansatz hier. Vielen Dank im Voraus.

Link to comment
Share on other sites

Hallo Oliver,

die Zeichnung ist aber schon maßstabsgetreu? Also r1 != r2? Oder soll Kreis B (oben)gleich groß wie Kreis A (unten) sein? Besitzen die Mittelpunkte der Kreise die gleiche x Koordinate?

Gruß Arne

Link to comment
Share on other sites

Hallo Oliver,

die Zeichnung ist aber schon maßstabsgetreu? Also r1 != r2? Oder soll Kreis B (oben)gleich groß wie Kreis A (unten) sein? Besitzen die Mittelpunkte der Kreise die gleiche x Koordinate?

Gruß Arne

Genauer lesen hilft. Oliver würde ja wohl kaum nach r1 und r2 suchen wenn beide identisch wären...

Link to comment
Share on other sites

Genauer lesen hilft. Oliver würde ja wohl kaum nach r1 und r2 suchen wenn beide identisch wären...

Hi,

ein weiterer Konfliktpunkt. Naja. Ich kenne einen Mathematikprofessor, der kann hier vielleicht weiterhelfen. Ich frag ihn mal.

Link to comment
Share on other sites

  • Developer

Hallo Oliver,

die Zeichnung ist aber schon maßstabsgetreu? Also r1 != r2? Oder soll Kreis B (oben)gleich groß wie Kreis A (unten) sein? Besitzen die Mittelpunkte der Kreise die gleiche x Koordinate?

Gruß Arne

Der Punkt B (also Ziel) kann ja beliebig im Raum liegen, dass ist ja nur ein Beispiel.

Die Kreise können daher ggf. auch ineinander liegen.

Es kann natürlich sein, das die Radien von Kreis 1 und Kreis 2 viele Kombinationen als Ergebnis haben,

man also kein eindeutigen r1 und r2 hat. Eine Definition sollte man daher sicher ergänzen, das das Zeil ein möglichst ausgeglichenes Verhältnis von r1 und r2 ist. Je nähe die Radien beieinander liegen, um so besser.

Link to comment
Share on other sites

Ich glaube ich war erfolgreicher :-)

Habe die Sachlage mal erklärt und habe auch eine mögliche Lösung erhalten, dennoch müsste meine Quelle die Zeichnung und die "genaue Textaufgabe von Oli" vor sich haben und lesen.

Habe jetzt den Text und das Bild mal ausgedruckt und werde es morgen mal abgeben.

Oli, wenn ich sie mit einem Eis bestechen muss, dann ist ja klar, das da ein halber Serial rausspringen muss;-) *DuckundWeg*

Frank

Link to comment
Share on other sites

Es kann natürlich sein, das die Radien von Kreis 1 und Kreis 2 viele Kombinationen als Ergebnis haben,

man also kein eindeutigen r1 und r2 hat.

Fühle mich zwar nicht als Mathe-Genie, aber das scheint mir nach ein paar Lösungsversuchen zutreffend zu sein.

Viel Erfolg bei der weiteren Suche

Remark

Link to comment
Share on other sites

Hallo,

eine Problemlöseaufgabe für ein Matheforum :rolleyes: . Ein Kreis wird festgelegt durch drei Punkte bzw. 2 Punkte. Der Kreis durch A hat die Bedingungen MP Teil der x-Achse,Teil von Punkt A und Berührungspunkt Kreis B (noch unbekannt). Für Kreis B ist die Tangente in B (Umkehrung zur Tangentenkonstruktion) bekannt und die Bedingung Berührungspunkt mit A. Sollten die Bedingungen unendlich viele Lösungen erlauben, setze r1=r2. Mit der Bedingung würde ich auch anfangen, mit Start in B.

Edit: Über das Lot zur Tangente in B ist natürlich auch der MP des Kreises B (bzw. 2 MP) gegeben.

Gruß Thomas

Link to comment
Share on other sites

Über das Lot zur Tangente in B ist natürlich auch der MP des Kreises B (bzw. 2 MP) gegeben.

Irgendwo auf dem Lot zur Tangente muss der Mittelpunkt des Kreises B sicher liegen,

aber da gibt's doch zunächst mal unendlich viele Möglichkeiten!?

Oder steh' ich da auf dem Schlauch?

Link to comment
Share on other sites

Die Gleichung hat zunächst zu viele Unbekannte. Das ist aber kein Problem, da Du r1 z.B. einfach aussuchen kannst, da es jeder beliebige Radius sein kann, der kleiner ist als der Abstand A-B. Naheliegenderweise sollte er sicherlich ungefähr die Hälfte von A-B sein, aber im Prinzip ist das egal.

Es sei denn die Vektoren sind wichtig! Ist es relevant in welcher Richtung das Fahrzeug an B ankommt oder ist es nur wichtig, dass es an B ankommt? Ersteres hat nur (maximal) eine sinnvolle Lösung, Letzteres wäre einfacher umzusetzen, da man wie gesagt r1 einfach selbst auswählen kann.

Link to comment
Share on other sites

Das ist aber kein Problem, da Du r1 z.B. einfach aussuchen kannst, da es jeder beliebige Radius sein kann, der kleiner ist als der Abstand A-B.

Stimmt nicht! :lol:

Da Oliver den Winkel in B vorgegeben hat (Kreis B hat in Punkt B die Richtunstangente) ist die Summe der Radien auf jeden Fall kleiner als Die Entfernung A-B (auch dann, wenn ein Radius gleich Null ist)!

Hallo Oliver,

wieviele Credits krieg ich, wenn ich eine mathematisch-geometrisch einwandfreie Lösung vorlege? :wub:

Mit erwartungsvollen Grüßen

Remark

PS Dauert aber bis Montag, falls morgen schönes Wetter ist :)

Link to comment
Share on other sites

Der Winkel (Vektor) ist also vorgegeben? Dann ist es ja nicht ganz so einfach. Ich versteh nicht ganz, warum das Fahrzeug nicht einmal pro Sekunde seine Position relativ zu B berechnen kann und daraufhin die ideale Richtung einschlägt. Auf diese Weise könnte sich B sogar bewegen und das Fahrzeug würde keine statischen Kreisbögen abfahren sondern schön geschwungene Linien fahren. Ein anderer Vorteil wäre, dass man nicht so viele Fallunterschiede machen muss. In dem skizzierten Fall ist das ja relativ ideal, aber es gibt eine Menge Fälle, in denen die Kreisradien ziemlich extrem werden oder das Fahrzeug am Ende in die falsche Richtung fahren könnte.

Wie wäre es z.B. mit dieser Methode:

Man denke sich einen Punkt B1, der von B aus gesehen in der Entfernung r2 hinter B liegt (also sozusagen auf der Kreistangente).

Nun findet man heraus ob dieser Punkt links oder rechts des Fahrzeugvektors (Vektor A) liegt. Je nachdem muss das Fahrzeug dann eine normale Rechts- oder Linkskurve fahren. Sobald der Fahrzeugvektor exakt in Richtung B1 weist, soll das Fahrzeug geradeaus fahren, und zwar so lange bis es r2 von B1 entfernt ist. Nun fährt es eine Rechtskurve mit Radius r2 und landet exakt auf B, mit der korrekten Richtung.

Scheint mir einfacher zu programmieren und weitaus realistischer vom Verhalten des Fahrzeugs als zwei Kreisbögen.

Link to comment
Share on other sites

Hallo Remark,

auf deine Lösung bin ich ja mal gespannt. Ich habe mir mal ein Beispiel ausgedacht. A,B mit vorgebenen Tangenten für A und B und r1 gleich bekannt und dies mit Geometriesoftware ausprobiert. Der Schnittpunkte der Normalen zu den Tangenten ergibt zwar den Mittelpunkt des zweiten Kreises. Die Gleichung der zweiten Tangente ist aber noch unbekannt. Mit Gleichsetzen von den Kreisgleichungen und Einsetzen von Bedingungen für den zweiten Kreis kann man das lösen, aber leicht ist das glaube ich nicht :) . Mit Geogebra bin ich da nicht weitergekommen.

Gruß Thomas

Link to comment
Share on other sites

  • Developer

Hallo zusammen,

zunächst möchte ich mich bei allen Beteiligten gedanken, dass sie sich Gedanken machen über das Thema.

Zum Zweiten bin ich froh, dass keiner nach 5 Minuten eine funktionierende Lösung auf den Tisch gelegt hat, denn so bin ich beruhigt, dass ich nicht gänzlich versagt habe :D

@Thorsten: Klar gibt es andere Varianten wie man ein Fahrzeug von A nach B bekommt und deine Variante ist so ähnlich auch heute bereits implementiert.

Wenn ich in AES bespielsweise ein Fahrzeug an die Tür fahren muss, sind mir auch A und B mit ihren Richtungen bekannt. In dem Fall errechne ich dann mit einem vorgegebenen Kurvenradius an Kreis 1 und 2 die Kurven und die dazwischen geradeaus gefahren Strecke. Das ist dort auch ein einigermaßen gangbarer Weg, da man hohehin nur mit kleine Radien um das Flugzeug aggieren kann.

Es spricht noch anderes gegen eine Implementierung eine KI Lösung, bei der die Fahrzeuge ihren Weg "selbst" finden: Die Bewegung muss ja bei jedem Framedurchlauf berechnet werden, da

sonst keine flüssige Animation entsteht. Bei AESlite (darum geht es hier primär) wird das heute dadurch erreicht, dass ich weiß, wieviele Millisekunden vergangen sind, seit der letzten Berechnung (also dem letzten Framedurchlauf) und auf dieser Basis eine Liste von Bewegungskommandos (also fahre Kreisbogen mit vorgegben Radius für x Meter) abgearbeitet werden, indem zunächst mit der Geschwindigkeit des Fahrzeugs die zurückgelegte Entfernung in den Millisekunden berechnet wird und daraus dann die neue LAT/LON Position des Fahrzeugs errechnet wird.

Diese Vorgang ist mit der prozessornahen Programmierung schnell möglich, selbst wenn wir hier von mehreren 1000 Berechnungen (Fahrzeugen) je Framedurchlauf sprechen.

Meine Frage hier ist daher auch eher für ein Erfassungstool gedacht, dass die Fahrwege vorab festlegt. Derzeit mache ich das schon so, dass mittels Abschnitten, die auch grafisch im FS darstellbar sind, die Kreisbögen und Gerade über die Straße gelegt werden und daraus dann die Befehlsliste entsteht, die dann im FS abgearbeitet wird.

Das funktioniert auch in soweit ganz gut, solange du von einem Ausgangspunkt (gegebener Position und Richtung) den Verlauf Abschnitt für Abschnitt erfasst. Da kann man dann den Weg zwischen

dem vorherigen und dem neuen Punkt klar berechnen und grafisch in Form eine Linie darstellen und man muss dann nur die Richtungsänderungen der Straße erkennen und die Punkte dort platzieren, wo der Verlauf der Straße sich ändert. Soweit so gut.

Problematisch wird es nun nur, wenn man irgendeinen der Punkte dieser Strecke nachträglich verschieben möchte. Denn dann habe ich zwei Alternativen:

1.) Ich definiere das die anderen Punkte in x/y fix bleiben, aber die Richtung an dem Punkt sich ändern. Dass führt dann aber zu dem Effekt, dass beim Verschieben eines Punktes die Linien zwischen allen Punkten der Strecke neu berechnet werden, da ja an jedem Punkt immer gilt das ankommende Richtung = abgehende Richtung sein muss und somit entsteht dann eher eine Sinuskurve entlang der Straße, als eine passenden Abdeckung

2.) Ich kann die Richtung in den Punkten fix halten, dann muss ich aber für alle nachfolgenden Punkte hinter meinem Verschobenen alle X/Y Positionen neu errechnen, was dann natürlich dazu führt, dass die Linie nicht mehr auf der Straße liegt und man aufwendig alle nachflogenden Punkte neu platzieren muss.

Unmöglich wird des dann, wenn man zum Beispiel an die Erfassung eines vermaschten Straßen- oder Vorfeldwegnetzes denkt, wo dann fixe Kreuzungpunkte hinzu kommen.

Also war meine Idee, die Linien zuwischen zwei Punkten nicht als einen Steckenabschnitt (Radius,Bogenlänge) sondern immer als zwei Abschnitte, die bei der Ersterfassung noch klar errechnet sind mit r1 und r2 = r und s1 und s2 genau die Häfte von s des erfassten Abschnittes sind.

Will man nun einen Punkt verschieben, so werden diese "virtuellen" Teilabschnitte jeweils zu den beiden Nachbarpunkten des zu verschiebenden neu berechnet. Die Position und Richtung an den Nachbarpunkten bleibt fix (somit verändert sich am Rest der Strecke nichts) aber die beiden Teilabschnitte vor und nach dem Verschiebenpunkt erhalten dann neuen Wert für r1/2 um s1/s2 (auf beiden Abschnitten vor und nach dem Verschiebepunkt).

Damit sind wir dann aber bei der obrigen Problemstellung. Wie kann ich nun die Änderung in r1/2 uns s1/2 so errechnen, dass die Wegstrecke über die dann ggf. unterschiedlichen Teilkreisabschnitte so errechnen, dass die Punkte sauber verbunden bleiben.

Dabei ist zum Beispiel der Punkt A der verschobene und B der nachfolgende Wegpunkt. Der "virtuelle" Zwischenpunkt ist der Berührungspunkt der beiden Kreise. Bei der späteren Erstellung der Bewegungskommandos wird dann natürlich in diesem Abschnitt aus ursprünglich 2 Kommandos 4 errechnet, alle anderen Abschnitte können optimiert weiter als ein Kommandos ausgegeben werden, da

man ja immer definieren kann, wenn r1=r2 ist, optimiere daraus r=r1 und s=s1+s2.

Folgende Sonderfälle fallen mir ein, die man aber gut vor der Berechnung prüfen kann:

1) x/y von B ist = x/y von A und Richtung in B = Richtung in A -> r=0 s=0 oder B entfällt

2) das x delta zu A=0 und y delta >0, Richtung in B = Richtung in A (also B liegt auf der positiven y Achse) -> r1/r2=0 und s1/s2=y/2 (wird also eine gerade Verbindung draus)

3) B liegt auf einem Kreis an A und die Richtung in B entspricht der Tangentensteigung, dann ist wieder r1=r2 und s1/s2= die Hälfte des Bogenabschnitts zwischen A und B

ein weiterer Sonderfall führen zu einem Fehler, da es keine Lösung geben kann:

4) Position B=A, aber Richtung A ungleich B, da gibt es keinen Berührungspunkte der Kreise an A oder B mit gleicher Tangentensteigung, nur Schnittpunkt.

Bei allen anderen Varianten gibt es sicher das Problem, dass bei beliebiger Wahl von r1 und r2 viele Lösungskombinationen von r1 zu r2 entstehen. Hierbei muss man dann bei der Entscheidung über die zu wählende Lösung vorgeben dass r1 und r2 so gleich wie möglich, bzw s1+s2 so klein wie möglich sein soll. Dann wird auch genau nur eine Lösung entstehen.

Durch die Festlegung, das die Tangentensteigung im Berührungspunkt gleich ist sollte es ja ggf. möglich sein eine Formel herzuleiten, die zumindest nur noch zwei Unbekannte r1 und r2 enthält.

Und vielleicht gibt es dann einem Möglichkeit durch die Definition eines möglichst kleinen Verhältnis unterschiedes von r1 zu r2 eine Lösung für r1/r2 zu bestimmen.

@RemarkH: Wer hier eine Lösung presentiert, die funktioniert und auch programmiertechnisch umsetzbar ist, der braucht sich über AES Credits keine Gedanken mehr zu machen. B)

Schönen Sonntag noch.

Link to comment
Share on other sites

  • Developer

Ich möchte nochmal einen anderen Denkansatz in die Runde werfen:

Wir haben ja eigentlich aufgrund des oben beschriebenen Senarios eine definierte Ausgangsbasis mit

bekannten r1=r2 und s1=s2 Werten, die durch die Ersterfassung sich ergeben. Durch die Verschiebung eines der Punkte ergibts ich ja nun eigentlich nur eine Veränderung im Verhältnis von r1/r2 und daraus dann anderen s1/s2 Werte.

Vielleicht kann man ja durch die bekannten Ausgangswerte und dem veränderten x/y Delta zwischen den Punkten A und B auch auf eine klares Ergebnis in der Veränderung zwischen r1 und r2 kommen, und somit die neuen Werte ermitteln.

Man kennt ja dann die Mittelpunkt der Kreise 1 und 2 wie sie vorher lagen, kennt das Verschiebe Delta und kann dann ggf. eine Verschiebung der Mittelpunkte so vornehmen, dass der eine Berührungspunkt erhalten bleibt aber beide Mittelpunkt in einem gleichen Verhältnis zueinander verschoben werden. Ist jetzt sicher nicht x/2 und y/2 des Deltas aber vielleicht ein einfacherer Lösungsansatz?

Gehen wir mal davon aus, das A der Fixe Punkt ist und B der um ein bekanntes Delta x/y verschoben wird.

Der Mittelpunkt M1 des Kreises an A liegt immer auf der x Achse und bleibt dort auch (mit einen anderen x=r1)

Der Mittelpunkt M2 des Kreises an B liegt auf einer bekannten Gerade die senkrecht auf der Tangente im Punkt B steht.

Da B um x/y verschoben wird, die Steigung der Mittelpunktgerade aber gleich bleibt (wir setzten voraus das die Richtung in B sich nicht verändert bei der Verschiebung) ist auch die neue Geradengleichung bekannt, nur nicht der Abstand r2 zwischen M2 und B.

Desweiteren ist klar, dass der Berührungspunkt der Kreise immer auf der Geraden liegt, die M1 und M2 verbindet.

Man kann auch definieren, dass r1 und r2 ein vorzeichen haben, also r<0 heißt Drehrichtung gegen den Uhrzeiger (linksrum), r>0 mit dem Uhrzeiger (rechtsrum). Daraus ergibt sich, das die Enfernung Md von M1 zu M2 immer absolut(r1-r2) ist. Ist also r1 +5 und r2-5 dann ist Md=10. Haben beide Kreise die gleiche "Drehrichtung", sie liegen also ineinander (der eine Kreismittelpunkt liegt innerhalb des anderen Kreises) dann wäre also r1=4 und r2=5 zum Beispiel, dann ist Md=1

Ich weiß nicht, ob diese Definitionen schon ausreichen, eine eindeutige Lösung für die Änderungen in r1/r2 zu bestimmen.

Link to comment
Share on other sites

  • Developer

Nun eine Lösung auf Basis des vorher beschrieben x/y Verschiebedeltas, die aber nicht ideal ist:

Gehe ich davon aus, dass ich M2 um x/y verschieben und damit die Kreise sich nicht mehr berühren und durch Veränderung nur eines der beiden Radien wieder eine Berührung erzeuge, dann wäre diese Änderung von r1 oder r2 sicher leicht errechenbar, das bekämme selbst hin.

Allerding ist dass dann für die Verbindung zwischen A und B nicht die optimale Lösung. Diese könnte ich aber dadurch annähern, dass ich die Verschiebung x/y in kleine Teile zerlege (ggf. in Abhängigkeit von der Verschiebeentfernung) und dann bei jeder diese Teilverschiebungen immer (je nach Richtung) den kleiner oder größeren Kreis anpasse und somit das Verhältnis zwischen beide möglichst gleich halte.

Würde also die Strecke aus einem kleinen Kreis bestehen und einem größen, würde bei einer Vergrößerung der Entfernung von A und B immer zunächst der kleine Kreis einen größeren Radius erhalten, zumindest solange, bis er größer als der andere ist.

Da beim Bewegen der Maus über den Bildschirm normalerweise ohnehin viele Events der Mausbewegung mit dann recht kleinen X/Y Deltas entstehen, würde die Berechnung nach der Policy "immer den nehmen, der kleiner/größer ist als der andere" bereits ausreichen um die Kreisradien in einem idealen Verhältnis zu halten.

Link to comment
Share on other sites

  • Developer

So,

ich glaube, wir haben einen falschen Ansatz gewählt, daher nochmal ein Versuch, die Denkrichtung zu optimieren:

Auch in der Realität besteht eine Straße aus eine Abfolge von Geraden und Kurven. Hätte man die genauen Pläne, würde man die gewünschten Bewegungsabfolgen direkt dort ablesen und den exakten Verlauf bestimmen können. Haben wir aber nicht, also müssen wir es optisch annähern.

Dabei können Fehler entstehen, die man nachträglich korrigieren muss. Die Korrektur soll sich aber nur auf einen kurzen Abschnitt auswirken, da wir voher und nachher korrekt erfasst haben.

Nehmen wir also an, wir haben eine Straßenverlauf, der über die Punkte P1-P2-P3 verläuft und die Strecken vor P1 und nach P3 liegen perfekt auf dem Untergrund, nur zwischen P1 und P3 ist der Verlauf ungenau und wir wollen P2 so verschieben, dass es besser passt.

post-77-124921089768_thumb.jpg

Wenn wir aber vorgeben, das Lage und Richtung in P1 und P3 sich nicht ändern dürfen (um Auswirkungen auf vorherige und nachfolgende Abschnitte zu verhindern) gibt es KEINE Möglichkeit, den Punkt P2 irgendwie zu verändern, da die Strecken es nicht zulassen. Einzige Ausnahme: Radius vor und nach P2 ist gleich, dann könnten wir den Punkt entlang der Linie verschieben, aber das bringt ja dann nichts.

Nun gibt es aber zwei Möglichkeiten:

1.) Wir lassen es zu, dass P1 und P3 sich entlang der vorherigen oder nachfolgenden Kurve oder Gerade" bewegen darf, da dadurch ja auch nichts an den anderen Abschnitten passiert.

Nun gebe es in einem gewissen Rahmen die Möglichkeit, den Punkt P2 zu verändern. Nicht beliebig, aber in einem gewissen Umfeld.

2.) Reicht der Spielraum nicht aus, damit anschließend die Stecke zwischen P1 und P3 über P2 exakt zur Straße passt, dann haben wir einen oder mehrere Punkt zuwenig, dh. die Segmentanzahl zwischen den Punkten P1 und P3 reicht nicht aus, den Weg genau zu treffen. Also fügen wir einen Punkt auf der Strecke hinzu, und können dann wieder im Rahmen von Möglichkeit 1 die Punkte P2 und P2' so schieben, dass es hinkommt.

Ob die Berechnung nun einfacher wird, muss man noch überlegen.

Was haben wir:

Wir haben eine Kreis mit gegeben/fixen Mittelpunkt und Radius (oder eine Gerade) am Punkt P1, der das Segment vor P1 beschriebt, genauso einen an P3. Der Mittelpunkt und Radius ändert sich nicht.

P1 und P3 sind jeweils Tangentenpunkt dort.

P2 ist Berührungspunkt zwei Kreise, die die Strecke zwischen P1-P2 und P2-P3 beschreiben.

Wird P2 nun verschoben, so ändern sich zwar diese beiden Kreise um P2 herum, die anderen bleiben unverändert, nur die Lage der Tangentenpunkt P1/P3 kann sich verändern.

Nach meiner Einschätzung kann es dabei immer nur genau eine Lösung oder kein Lösung geben, wenn man P2 verschiebt.

Ist nur die Frage, kann man dafür nun eine exakte Berechnung erstellen? :blush:

Link to comment
Share on other sites

Mal ne dumme Frage, geht es darum, einen Punkt P2 zu finden, der so liegt, dass der Weg von P1 über P2 nach P3 möglichst elegant ist? Ich hab noch nicht ganz verstanden, welche Werte fix gegeben sind und welche nicht.

Ich habe einen Punkt P1 mit einem Richtungsvektor v1. Dann gibt es einen Punkt P3 mit einem Richtungsverktor v3.

Die Aufgabe besteht jetzt darin:

1. Einen Punkt P2 mit einem Richtungsvektor v2 zufinden durch den der Weg geht.

2. Einen Kreis K1 (Mittelpunkt M1 + Radius r1) zu finden, dessen Kreislinie P1 und P2 verbindet.

3. Einen Kreis K2 (Mittelpunkt M2 + Radius r2) zu finden, dessen Kreislinie P2 und P3 verbindet.

4. Es müssen M1, M2, r1 und r2 so bestimmt werden, dass P2 auf der Kreislinie K1 den selben Anstieg hat, wie P2 auf Keislinie K2.

Ist das so richtig oder hab ich das falsch verstanden? Bin irgendwie etwas verwirrt, wenn ich den ersten Post mit dem letzten vergleiche.

Oder ist der Punkt P2 gar vorgegeben? Dann ist die Lösung einfach.

Danke für deine weiteren Ausführungen.

Link to comment
Share on other sites

  • Developer

Mal ne dumme Frage, geht es darum, einen Punkt P2 zu finden, der so liegt, dass der Weg von P1 über P2 nach P3 möglichst elegant ist? Ich hab noch nicht ganz verstanden, welche Werte fix gegeben sind und welche nicht.

Ich habe einen Punkt P1 mit einem Richtungsvektor v1. Dann gibt es einen Punkt P3 mit einem Richtungsverktor v3.

Die Aufgabe besteht jetzt darin:

1. Einen Punkt P2 mit einem Richtungsvektor v2 zufinden durch den der Weg geht.

2. Einen Kreis K1 (Mittelpunkt M1 + Radius r1) zu finden, dessen Kreislinie P1 und P2 verbindet.

3. Einen Kreis K2 (Mittelpunkt M2 + Radius r2) zu finden, dessen Kreislinie P2 und P3 verbindet.

4. Es müssen M1, M2, r1 und r2 so bestimmt werden, dass P2 auf der Kreislinie K1 den selben Anstieg hat, wie P2 auf Keislinie K2.

Ist das so richtig oder hab ich das falsch verstanden? Bin irgendwie etwas verwirrt, wenn ich den ersten Post mit dem letzten vergleiche.

Oder ist der Punkt P2 gar vorgegeben? Dann ist die Lösung einfach.

Danke für deine weiteren Ausführungen.

So wie du es beschrieben hast, tifft es exakt die Ausgangsfrage von ganz oben. Also bei gegebenem Punkt P1 und P3 jeweils mit gegeben Richtungswechsel und Punkt 2 so zu finden, dass der Weg zwischen P1 und P3 über P2 "ideal" ist und sich damit R1 und R2 ergeben (woraus dann ja auch die Bogenlängen von P1 zu P2 und P2 zu P3 errechenbar wäre.

Eine "Formel" dafür wäre auf alle Fälle interessant, da man so zum Beispiel ein Fahrzeug noch besser zwischen zwei gegebenen Punkt bewegen könnte.

Die zweite Beschreibung aus Post 20 war nochmal ein Denkansatz, der die Veränderbarkeit eines erfassten Straßenverlaufens diskutiert. Hier war die Frage im Mittelpunkt,

die ich einen Punkt verschieben kann, so dass maximal die Nachbarpunkte und Nachbarteilstrecken von der Verschieben betroffen sind, nicht aber sich er gesamte Streckverlauf verändert.

Link to comment
Share on other sites

Also, vorweg, ich habe noch keine Lösung, aber den richtigen Lösungsansatz gefunden. Das Problem bei mir ist nur noch das falsche Gleichsetzen zweier Kreisgleichungen.

So, fangen wir an. Generell hat dein Problem eine quadrahtische Lösung. Von daher ist es ungeschickt, gleich alle zwei Kreise zu berechnen. Besser ist es da, einen Kreis (in unserem Fall K2 vorzugeben und K1 danach zu berechnen, weil es für diesen Fall dann auch schon zwei Lösungen gibt.

Grundlagen:

Der Mittelpunkt M2 kann sich nur irgendwo auf der ortogonalen Geraden von v3, die durch P3 geht befinen. Logisch, denn das wird ja durch die Tangenete an Punkt P3 vorgegeben.

Der Mittelpunkt von M1 kann sich ebenfalls nur auf der X-Achse befinden. (Vorausgesetzt, mann lässt Punkt P1 immer bei (0/0) starten und in Richtung (0/1) schauen. Was zur vereinfachung erstmal gemacht werden sollte)

Rechenweg:

Zunächst definieren wir einfach einen Mittelpunkt M2 irgendwo auf der ortogonalen Graden von v3. Der Punkt sollte nicht weiter als die Hälfte der Strecken P1P3 von P3 entfernt sein, sonst sieht der Weg dann ziehmlich umständlich aus. (Mathematisch aber korrekt). Haben wir M2, so haben wir den Kreis K2 vorgegeben und suchen jetzt den passenden Kreis K1 dazu. Dafür gibt es zwei Lösungen. Bei der ersten Lösung Kreis K2 außerhalb von K1. Bei der zweiten Lösung liegt K2 komplett in K1.

Die beiden Kreise lassen sich durch folgende Gleichungen beschreiben:

K1 (X - r_1)² + Y² = r_1² --> Warum, weil der Mittelpunkt von K1 nur auf der X-Achse liegen kann, im Punkt M1(-r / 0)

K2 (X - X_m2)² + (Y - Y_m2)² = r_2²

Nehmen wir mal ein konkretes Beispiel, wass deinem ersten Schaubild nahe Kommt.

P1(0 / 0), v1(0 / 1)

P3(-4 / 4), v3(1 / 1)

Wir definieren:

M2(-3 / 3) --> Liegt also auf der ortogonalen Geraden von v3, die durch (-4 / 4) verläuft.

Damit ergibt sich:

r_2 = sqrt(1² + -1²) = sqrt(2)

Somit können wir K2 bestimmen mit:

K2: (X + 3)² + (Y - 3)² = 2

Wenn wir nun die beiden Kreise gleichsetzen, dann kommt eine Lösung abhängig von r_1 heraus. Wir bestimmen also den/die gemeinsamen Punkte von K1 und K2 abhängig von r_1. Die Kunst besteht jetzt darin, r_1 zu finden, sodass die Kreisgleichung für K1 mit dem Punk P1(0 / 0) auf den selben Wert Kommt, wie die Kreisgleichung K1 mit dem Punkt P3, der ja abhängig von r_1 ist.

So, ich hoffe du hast es einigermaßen verstanden. Ich habe die letzten beiden Abende intensiv gerechnet. Aber ich bin schlichtweg zu blöd dazu. Bei mir scheitert es immer an den formalen Dingen. ;-) Vielleicht kann hier jemand die Rechnung nachvollziehen und das ganze mal zu ende rechnen. Der Weg sollte allerdings der richtige sein.

Link to comment
Share on other sites

Doch, ich glaub ich hab die Sache eben gelöst. Also, das Vorgehen ist wie oben beschrieben. Einen Mittelpunkt M2 hernehmen (das geht ja leicht) und dazu den anderen Kreis berechnen. Letzteres ist jetzt klar.

Um den Brühungspunkt zweier Kreise zu ermittelt, nimmt man die Formel r2 - r1 = sqrt( (x2 - x1)² + (y2 - y1)² ) her.

Was wir in diesem Fall suchen ist r1.

Nochmal mit den Beispieldaten von oben:

P1 (0 / 0)

P3 (-4 / 4)

v1 (0 / 1)

v3 (1 / 1)

v3' (1 / -1) --> Ortogonaler Vektor von v3 (v3 um 90° nach rechts gedreht).

M2 (-3 / 3) --> Ist ein gültiger Mittelpunkt des Kreises K2.

M1 (-r / 0) --> Mittelpunkt des Kreises K1, irgendwo auf der X-Ache.

r2 = sqrt(2) --> Radius des Kreises K2 ist wie Wurzel aus 2

Jetzt nehmen wir die Formel her und setzen die Werte ein. Also:

sqrt(2) - r1 = sqrt( (-3 + r1)² + 3² ) --> Erstmal die Binomische Formel auflösen und zusammenrechnen.

sqrt(2) - r1 = sqrt( r1² - 6r + 18 ) --> Jetzt können wir beide Seiten quadrieren (dürfen wir ja, weil das nichts an der Gleichung ändert) /² (Achtung, die Linke Seite ist dann auch ein binomischer Ausdruck)

2 - 2*sqrt(2)*r1 + r1² = r1² - 6r + 18 --> Die beiden r² kürzen sich weg, damit bleibt

-2*sqrt(2)*r1 + 2 = -6r1 + 18 --> Weiter nach r1 umstellen /-2

-2*sqrt(2)*r1 = -6r1 + 16 --> alles durch r1 teilen

-2*sqrt(2) = -6 + 16/r1 --> die 6 rüber holen /+6

-2*sqrt(2) + 6 = 16/r1 --> alles durch 16 teilen

(-2*sqrt(2) + 6)/16 = 1/r1 --> Jetzt den Kehrwert nehmen, um auf r zu kommen

16 / (-2*sqrt(2) + 6) = r1

r1 ist in unserem Fall ~ 1.8124. Damit haben wir r1 bestimmt und können den Mittelpunkt M1 definieren mit M1( -1,8124 / 0 ). Somit haben wir den Kreis K1 gefunden und können dessen Formel bestimmen.

K1: (x + 1,8124)² + y² = 1.8124²

K2 war ja: (x + 3)² + (y - 3)² = 2

Das Gleichsetzten beider Kreisformeln ist nun der nächste und letzte Schritt. 2 Gleichung mit zwei unbekannten - also lösbar. Damit bekommen wir den Berühungspunkt beider Kreise und damit den Wendepunkt unseres Objektes.

So, das wäre es dann. Hoffe, dass lässt sich umsetzten in C++. Ggf. muss man sich den Rechenweg vorher mit Variablen umstellen, sodass man nur noch einen Wert einsetzten muss, um die Lösung zu erhalten. Ist recht schwierig. Hatte mir mal eine Kollisionserkennungs-Algorithmus programmiert. Ist ne ziemlich haarige angelegen heit. Aber einmal richtig gecodet und dat Ding läuft.

;-)

PS: Du musst nicht mal der genauen Schnittpunkt ermitteln. Es reich vollkommen aus zu ermitteln, ob der Punkt, an dem sich das Objekt gerade befindet ein Punkt des Kreises K2 ist (einfach die aktuellen Koordinaten des Objektes in die Kreisgleichung von K2 einsetzen und schauen, ob der sich ergebende Radius passt). Natürlich muss man dann hier die Ungenauigkeit berücksichtigen und vor allem, dass zwischen zwei Bildern immer eine Zeitspanne vergeht. Aber wem erzähle ich das. Viel Glück jedenfalls noch.

PS2: Jetzt muss man den Mittelpunkt M2 nur noch wählen, dass der Wegverlauf zur Straße passt bzw. deinen persönlichen Vorgaben entspricht.

Link to comment
Share on other sites

Guest
This topic is now closed to further replies.
 Share

×
×
  • Create New...