2D-Punkte durch Kurve verbinden

XMAMan

Die Frage bezieht sich auf ein Spiel auch wenn sie Mathematisch klingt.

Gegeben ist eine Menge von 2D-Punkten, welche die Stützstellen einer Straße darstellen.

P1->P2->P3->P4->...Pn

Ich würde nun gerne eine Kurve durchlegen, welche durch alle Stützstellen geht.

Erster Gedanke: Kubische Splines.

Problem an der Sache: Die Splines werden dort als y=f(x) angegeben. D.h. in einen kartesischen Koordinatensystem. Das basiert ja auf den Gedanke, dass es für jedes X nur ein Y gibt. Bei einer Straße, welche ich von oben wie bei einer Karte sehe, geht das natürlich nicht.

Man könnte jetzt für jede Kante (Verbindet zwei Stützpunkte) das Koordinatensystem so drehen, dass die Abszisse auf der Kante liegt. Bei der Lösung müsste man aber zwischen zwei Koordinatensystem umrechnen. Gefällt mir nicht so.

Wenn ich zwei Punkte mit einer Linie verbinden will, dann gibt es dafür ja auch den Weg, dass ich ein Vektor zwischen die beiden Linien lege und dann diesen Vektor mit einer Float-Zahl multipliziere, um die Punkte auszurechnen.

Gibt es für den Anwendungsfall: Male Gebogene Linie durch 4 Punkte auch so eine schöne Lösung? Also Quasie ein Polynom 4. Grades, was nicht im kartischen Koordinatensystem definiert ist sondern im 2D-Vektorraum.

Ich erinnere mich noch das es in der Mathematik zwei Darstellungen für Funktionen gibt.

Möglichkeit 1: y=f(x)

Möglichkeit 2: x=fx(t) y=fy(t) t=float-Zahl

Wie nennt man die Darstellung von Möglichkeit 2? Sowas bräuchte ich und damit müsste ich dann ein Polynom 4. Grades beschreiben. Dann hätte ich die Lösung.

dot

Also ich weiß nicht was für merkwürdige y=f(x) Splines du dir da angeschaut hast, aber das hier sind die Splines die ich kenn...

Finnegan

Ich denke der Begriff, den du suchst ist "Parametrische Kurve".
Das sind Funktionen, die nicht einfach nur auf ein "y" abbilden, sondern auf einen Vektor.
Im 2D-Fall sehen die dann so aus: $\mathbf {f}(t) = \begin{pmatrix}x(t)\\y(t)\end{pmatrix}$ , wobei $x(t)$ und $y(t)$ individuelle Koordinatenfunktionen für jeweils die x- und die y-Koordinate sind.
Mit solchen Kurven kann der Funktionsgraph auch wunderbare Pirouetten drehen womit sich das "X nur ein Y"-Problem erübrigt.

Was die Interpolation angeht:
Schau dir nochmal die kubischen Splines an, der Ansatz ist schon ganz gut. Bedenke dass die Stützstellen dabei eben nicht nur y-Koordinaten sein können ("y=f(x)"),
sondern auch 2D-Vektoren ("(x,y)=f(x)") und die Spline-Funktion somit eine parametrische Kurve - die Berechnung läuft völlig analog.

Finnegan

dot schrieb:

Also ich weiß nicht was für merkwürdige y=f(x) Splines du dir da angeschaut hast, ...

Möglicherweise eine Vereinfachung mit "1D"-Kontrollpunkten. Wenn man nur einen simplen Funktiongraphen und keine Kurve interpolieren will reicht das aus

XMAMan

Vielen Dank für eure Antworten. Auf der Wiki-Seite ist ja die parametrische Kurve, wie ich sie gesucht habe.

Ich habe mich von der Seite hier wohl etwas in die Irre führen lassen:

http://www.codeproject.com/Articles/560163/Csharp-Cubic-Spline-Interpolation

Dadurch dachte ich, es gebe nur die f(x)-Darstellung dafür.

XMAMan

Ok, also die Formel ist echt erstmal super. Man könnte damit im Prinzip alles über eine Kurve interpolieren, was sich Menge von Floatzahlen darstellen läßt. Super Sache.

Nun aber zu mein nächsten Problem... Das ist ja jetzt erstmal nur eine Linie. Eine Straße hat aber eine Breite. Ich habe das Problem, dass in den Kurven es zu Überlappungen kommt.

Schaut mal hier:

http://www.m-i-u.de/thumb-i106630bbe15a.jpg

Hat jemand von euch eine Idee, wie ich diese Überlappungen weg bekomme? Momentan berechne ich die Straßenrandpunkte so:

private static void GetDrawingPointsForStreetSegment(IDrawingStreetData street, int segmentIndex, StreetDrawingPoints drawingPoints, MaxCubicHermitSplineParameter min, MaxCubicHermitSplineParameter max)
        {
            Vektor2D p0 = street.Nodes[segmentIndex].Position;
            Vektor2D p1 = street.Nodes[segmentIndex + 1].Position;
            Vektor2D m0 = street.Nodes[segmentIndex].Tangente;
            Vektor2D m1 = street.Nodes[segmentIndex + 1].Tangente;

            Vektor2D n1 = (p1 - p0).Normiere().Drehe90() * GlobalSettings.StreetWidth;

            float tMin = Math.Min(Math.Max(min.Min, -2), +2);
            float tMax = Math.Min(Math.Max(max.Max, -2), +2);

            for (float t = tMin; t <= tMax; t += 0.1f)
            {
                Vektor2D pos = (2 * t * t * t - 3 * t * t + 1) * p0 + (-2 * t * t * t + 3 * t * t) * p1 + (t * t * t - 2 * t * t + t) * m0 + (t * t * t - t * t) * m1;

                if (t >= min.Top && t <= max.Top)
                {
                    drawingPoints.List1.Add(pos + n1);
                }
                if (t >= min.Bottom && t <= max.Bottom)
                {
                    drawingPoints.List2.Add(pos - n1);
                }
            }
        }

Ich bräuchte einfach nur eine Idee. Vielleicht die Schnittpunkt zwischen zwei Benachbarten Straßenumrandungen bilden? Irgend sowas vielleicht.

XMAMan

Ein Teil der Überlappungen konnte ich wegschneiden, indem ich geschaut habe, ob es bei den Straßenrand-Segmenten ein Schnittpunkt gab. Leider gibt es noch immer kleiner fiese Stellen:

http://www.m-i-u.de/thumb-i106637b2edp3.png

Finnegan

Hi!

Jau, das ist sicher etwas herausfordernd das sauber hinzubekommen. Ich habe zwar nicht die Muße besesonders tief in die Problematik einzusteigen, aber für ein paar Tips bin ich immer zu haben

Der Ansatz für die Randpunkte ist eigentlich schon ganz gut (Punkte liegen in fester Entfernung in Richtung der Kurvennormalen), allerdings bestimmst du die Richtung der Kurve (und damit die Normale) lediglich durch den Poygonzug der durch die Kontrollpunkte (Nodes) gegebenen ist. Die Normalen basieren also nur auf einfacher linearer Interpolation (Kontrollpunkte durch gerade Linien verbunden), und nicht auf der schicken Spline-Interpolation.

Was du tatsächlich berechnen solltest, wenn du $n_1$ bestimmst, ist der sog. Tangentialvektor der interpolierten Kurve an Punkt $t$ . Diesen erhältst du, wenn du die Koordinaten-Funktionen deiner Spline-Kurve $\mathbf {x}(t) = \begin{pmatrix}x(t)\\y(t)\end{pmatrix}$ jeweils nach $t$ ableitest: $\mathbf {\dot x}(t) = \begin{pmatrix}\frac{d}{dt}x(t)\\\frac{d}{dt}y(t)\end{pmatrix}$ gibt dir für jeden Punkt auf der Kurve deren aktuelle Richtung (Tangentialvektor) und Geschwindigkeit (Länge des Vektors).

Du solltest dein $n_1$ als für jedes $t$ mithilfe des Tangentialvektors $\mathbf {\dot x}(t)$ bestimmen.

Bei besonders engen Kurven können natürlich auch dabei die so bestimmten Randpunkte "hinter" ihren Vorgänger "wandern". Ein Ansatz wie ich das intuitiv versuchen würde zu lösen:

Merke dir die Normale und den Kurvenpunkt $\mathbf {x}(t)$ des Vorgängers. Diese definieren eine Gerade die den 2D-Raum in zwei Halbräume unterteilt. Den Halbraum der in Laufrichtung der Straßen-Kurve liegt (Richtung des Tangentialvektors) nenne ich mal "Vorwärts-Halbraum", den anderen "Rückwärts-Halbaum". Für jeden neuen Randpunkt, den du berechnest, bestimmst du nun in welchem der beiden Halbräume dieser liegt. Ist es der Vorwärts-Halbraum, so verwendest du den Punkt unverändert, ansonsten nimmst du stattdessen den Randpunkt des Vorgängers. Keine Garantie, dass das die beste Lösung ist, aber für einen ersten Ansatz ist das denke ich mal ganz brauchbar.

Gruss,
Finnegan

P.S.: Vielleicht auch hilfreich, da es eine ähnlich Thematik anschneidet: https://www.c-plusplus.net/forum/334411. Besonders der letzte Beitrag könnte helfen, falls du dich wegen dem Ableiten der Spline-Kurve am Kopf kratzen solltest.

XMAMan

Nicht schlecht Herr Finnegan. Die Ableitung der Kubischen Funktion hat bereits gereicht das ganze zu lösen:

http://www.m-i-u.de/thumb-i106647bnqbuc.jpg

So siehts im Code nun aus:

for (float t = tMin; t <= tMax; t += stepWidth)
            {
                Vektor2D pos = (2 * t * t * t - 3 * t * t + 1) * p0 + (-2 * t * t * t + 3 * t * t) * p1 + (t * t * t - 2 * t * t + t) * m0 + (t * t * t - t * t) * m1;
                Vektor2D normale = ((6 * t * t - 6 * t) * p0 + (-6 * t * t + 6 * t) * p1 + (3 * t * t - 4 * t + 1) * m0 + (3 * t * t - 2 * t) * m1).Normiere().Drehe90() * GlobalSettings.StreetWidth;

                if (t >= min.Top && t <= max.Top)
                {
                    drawingPoints.List1.Add(pos + normale);
                }
                if (t >= min.Bottom && t <= max.Bottom)
                {
                    drawingPoints.List2.Add(pos - normale);
                }
            }

Als nächstes muss ich nun die Kreuzungen definieren.

Das Problem an Kubischen Splines: Das 1. und das letzte Liniensegment macht momentan etwas Ärger. Ich zeichne einfach nur eine gerade Linie anstatt hier was zu interpolieren:

Vektor2D pos1 = p0 * (1 - tMin) + p1 * tMin;
                Vektor2D pos2 = p0 * (1 - tMax) + p1 * tMax;

                drawingPoints.List1.Add(pos1 + n1);
                drawingPoints.List2.Add(pos1 - n1);
                drawingPoints.List1.Add(pos2 + n1);
                drawingPoints.List2.Add(pos2 - n1);

Dabei bekomme ich aber komischwerweise wieder so ein Schlenker rein:

http://www.m-i-u.de/thumb-i106648bnvjl8.jpg

Ich muss selber erstmal nachdenken, woher der nun wieder kommt. Außerdem muss ich die tMin und tMax-Wert noch richtig berechnen, damit die Linienstücke sich genau berühren. Die blauen Kreise geben die erechneten Schnittpunkte von den Linien-Endstücken an.

Finnegan

Ja, die Verbindung sieht ein wenig "unstetig" aus
Wenn du den Endpunkt der Spline-Kurve einfach so an die Kreuzung "dranflanschst", dann hat die Kurve in diesem letzten Punkt eine Tangente in Richtung der geraden Strecke zwischen den letzten beiden Kurvenpunkten.
Wenn ich mir die Straße anschaue, die z.B. von oben rechts in richtung der Kreuzung läuft, dann passt diese Tangente (von "oben rechts" nach "unten links") natürlich nicht zu derjenigen der Kreuzung an dieser Stelle (von rechts nach links).

Diese Spline-Kurven sind üblicherweise $C^2$ -stetig ( $C^n$ -stetig: $0$ -te bis $n$ -te Ableitungen stimmen an Verbindungspunkten der einzelnen Spline-Segmente überein, im Falle von $C^2$ -Stetigkeit heisst das, sie haben an diesen Punkten die selbe Tangente und Krümmung), allderings ist der Endpunkt kein solcher "Verbindungspunkt" mehr - es fehlt die Information wie die Kurve "dahinter" weiter gehen soll.

Die Einfachste Lösung dürfte sein, noch weitere ein bis zwei "virtuelle" Kontrollpunkte zur Kurve hinzuzufügen, die eigentlich nicht mehr zur Kurve, sondern zur Kreuzung gehören (wenn ich noch richtig in Erinnerung habe, wie sich diese Kurven verhalten, sollten ein weiterer Punkt für $C^1$ - und zwei Punkte für $C^2$ -Stetigkeit genügen). Das sollte dazu führen, dass die Kurve in Richtung des Ansatzstückes auf der Kreuzug "gebogen" wird, so dass sie sauber an die Kreuzung ansetzt.

Vielleicht macht es auch Sinn verschiedene Kreuzungstypen einzuführen:

1. "Echte Kreuzung": Wenn ich mir dein Bild ansehe, bilden deine Blauen Markierungen ein hübsches Dreieck mit Mittelpunkt. Man könnte dieses Dreieck so definieren, dass die Seiten immer senkrecht zur Tangente der dort auftreffenden Straßen-Kurve sind. Der Mittelpunkt des Dreiecks ist für jede der dort auftreffenden Straßen zusätzlicher "virtueller" Kontrollpunkt, so dass sich alle Straßen in richtung der Dreiecksmitte "biegen", d.h. deren Tangenten laufen alle in Richtung der Dreiecksmitte. Bei vier auftreffenden Straßen dasselbe analog mit einem Viereck.

2."Anschlussstelle": Eine Nebenstraße führt auf eine "Hauptstraße". Die Hauptstraße ist dabei eine durchgehende Kurve, die von der aufführenden Straße nicht beeinflusst wird. Der zusätzliche "virtuelle" Kontrollpunkt der Nebenstraße wird dabei so gewählt, dass die Nebenstrasse an der Verbindungsstelle senkrecht auf die Kurve der Hauptstraße trifft. Schnittpunkte der Randkurven schneidet man enspechend zu, so dass die verbindung bündig ist.

... und vielleicht noch diverse andere Kreuzungstypen (wohl ein fall für einen Straßen-Editor )

Gruss,
Finnegan

P.S.: Macht übrigens echt Spass dir Tips zu geben, wenn man gleich am nächsten Tag auf einen Screenshot zu sehen bekommt, dass die eigenen theoretsichen Überlegungen auch tatsächlich funktionieren. Weiter so

XMAMan

Also, ich habe jetzt einfach den letzen Punkt vom vorletzten Segment genommen und diesen mit den Schnittpunkt (Blauer Kreis) einfach direkt mit einer Linie verbunden.

Es klappen fast alle Kreuzungen bis auf eine:

http://www.m-i-u.de/thumb-i106653by7nc1.png

Da muss ich nochmal schauen wie ich das schaffe.

Die nächsten Schritte: Fußwege und weiße Striche in der Straßenmitte. Wenn jemand von euch noch Ideen hat, welche Dinge noch wichtig für so eine Karte, dann könnte ihr das mal sagen. Ich denke mal Bäume, Sträucher, Felsen, Schilder und Ampeln am Straßenrand sind auch noch wichtig. Das ganze soll aber rein durch ein Zufallsgenerator erfolgen. Ich habe bis jetzt kein Karteneditor und will damit auch nicht anfangen.

Edit 1:

Letzte Kreuzung klappt nun auch. Jetzt gibts sogar schon in der Mitte Striche:

http://www.m-i-u.de/thumb-i106667bo4kwa.jpg

Es gibt Tage, da weiß ich einfach nicht, wie ich meine Zeit auf Arbeit rumkriegen soll^^ Da komme ich dann echt gut mit diesen 'Spezial-Themen' vorran.

Edit 2:

Jetzt ist auch der Fußweg da:

http://www.m-i-u.de/thumb-i106717bcgnge.png