Kubische Interpolation einer Linie

[javampir]

Hallo zusammen,
ich habe eine Reihe von Punkten mit konstantem x-Abstand, aber mit vom User einstellbarem y-Wert. Die Punkte sollen durch eine Linie verbunden verden. g.drawPolyline tuts, aber schön schaut das ganze ja nicht grad aus. Was mir vorschwebt ist eine nette Verbindung der punkte durch eine kubische interpolirte Linie. Ich wollte es mit java.awt.geom.CubicCurve2D machen, aber ich habe keine Ahnung, wo ich die ControlPoints hinsetzen soll. Die Linie geht ja natürlich nicht durch die controls an sich. Die ControlPoints immer genau in die Mitte zu setzen wäre auch schwachsinn, dann hat man ja immer eine gerade Linie weil die Controls draufliegen...
Ich bitte um Hilfe!
javampir

 

[Ruzmanz]

Für AWT gibt es eine Bibliothek, die das kann ... habe den Namen vergessen. Dort wurde auf Anti-Grain Geometry - Interpolation with Bezier Curves verwiesen. Ist eigentlich "relativ simple", wenn man es mal verstanden hat. Sofern nachträglich keine Punkte hinzugefügt oder entfernt werden könnte das so aussehen: https://github.com/RuZman/JMotion/blob/master/src/de/ruzman/fx/util/PolyBezier.java (ist für JavaFX). Hatte zwar versucht Punkte nachträglich hinzuzufügen und zu löschen, aber das ist nach "stundenlangem" hin und her an unendlich vielen IndexOutOfBounds-Exceptions gescheitert ...

PS: Falls du da was findest oder selbst machst, wäre es nett, wenn es postest. Damit kann man ziemlich coole Sachen machen 😉

 

[PencilHB]

Mein Rat: keine fertigen Toolboxen benutzen – du beraubst dich um den grössten Spass des Programmierens. Linien und Flächen im Raum auszurichten, ist eine tolle Aufgabe.

Ich würde dein Problem mit Vektorrechnung lösen.

Für die Kontrollpunkte würde ich Innenpunkte (d.h. Polygonpunkte mit zwei Nachbarn) und Endpunkte (d.h. Polygonpunkte mit einem Nachbar) unterscheiden – bitte auch den Spezialfall eines Polygons mit genau zwei Punkten nicht vergessen.

Innenpunkte:
Die Kontrollpunkte liegen auf der Tangente am Innenpunkt. Die Tangente erhältst du in dem du die beiden Nachbar-Richtungsvektoren addierst, durch zwei teilst und anschliessend x und y vertauschst. Ab jetzt berechnest du zuerst die eine Richtung und dann die invertierte Richtung. Was noch fehlt ist der Abstand, also die Länge dieser ‚halben Tangenten’. Diesen Abstand bekommst du aus der Länge des jeweiligen Nachvektors. Ich würde hier genau die Hälfte verwenden (alternativ vielleicht ein Drittel, aber nie mehr als die Hälfte, sonst können die Beziers Knicke bekommen). Die gleiche Berechnung in der anderen Richtung und schon hast du die beiden Kontrollpunkte um einen Innenpunkt (diese gehören natürlich zu jeweils unterschiedlichen Bezierkurven). Wichtig ist, dass du den Spezialfall der linearen Abhängigkeit der Nachbarvektoren beachtest – in diesem Fall ist die Tangente der Nullvektor, was nichts bringt – deshalb einfach einen der Nachbarvektoren verwenden.

Endpunkte:
Wenn es zu einem Endpunkt einen Nachbar-Innenpunkt gibt, dann liegt jetzt bereits ein Kontrollpunkt fest. Den Vektor vom Endpunkt zu diesem Kontrollpunkt würde ich verwenden, um die Lage des äusseren Kontrollpunktes zu berechnen. Auch hier wieder: die halbe Länge genau dort abtragen und schon hast du alle Kontrollpunkte.

‚Jetzt sollte es dich in den Fingern jucken…’

 

[Warrior7777]

Wie wäre die Formulierung und Lösung als Ausgleichs-Problem? Der Abstand aller Kontrollpunkte sollte von der Gerade mit Gleichung a*x + b=y minimiert werden, du suchst also die Parameter a und b, die deine Gerade beschreiben. In Python wäre das einfach mit der numpy-Bibliothek zu realisieren. Ich habe allerdings keine Ahnung, ob es sowas auch für Java gibt... Weiss da jemand mehr?
Oder habe ich da etwas an der Aufgabenstellung falsch verstanden, d. h. es geht gar nicht um Geraden, sondern um beliebige Linien. In diesem Fall vielleicht mehrere Ausgleichsprobleme auf kleinen Strecken und anschliessend eine Interpolation durch die "Endpunkte" der Geraden?

Nur mal so als Anregung. Wenn du Genaueres wissen willst, frag einfach nach! 🙂

 

[PencilHB]

Weil ich ein Beispiel für eine Grafikausgabe gesucht habe, habe ich kurzerhand den obigen Algorithmus implementiert.

Damit jeder das Resultat und die Implementierung einsehen kann, habe ich eine Download-Seite eingerichtet. Dort könnt ihr eine JAR-Datei und eine JAVA-Datei laden und euch das Verfahren genau ansehen.

Im JAR-Programm einfach mit der linken Maustaste auf den weisen Hintergrund klicken und Punkte setzen – das Programm legt eine runde Kurve um die Punkte… (so hoffe ich )

 

[javampir]

Hallo zusammen,
Es war abenteuerlich, aber ich habe es schließlich mit den vektoren geschafft. Sobald ich dad hochladen kann, mache ich das hier.
Javampir