Kurve clever in Punkte zerlegen

Guten Tag!

Ich habe eine lange Kurve, die ich jetzt einigermaßen clever in xy Punkte zerlegen will (zum rechnen und zeichnen). Ich könnte nun natürlich einfach die Kurve in festen Sample Abständen auswerten, z.B. alle 0.5m: Punkt1 = f(0), Punkt2 = f(0.5), Punkt3 = f(1.0) usw.

Würde gehen, aber die Kurve hat unterschiedliche Krümmungen und da würde es ja vermutlich mehr Sinn machen, den Sample-Abstand in Abschnitten starker Krümmung zu erhöhen und bei niedriger Krümmung (wenn es fast linienartig ist) zu senken.

Kennt da jemand einen Algorithmus oder Artikel, der sowas behandelt?

In welcher Form hast du die Kurve denn gegeben?

Du kannst natürlich ein Modell, z.B. Polynome vom Grad $\le k$ oder Splines hernehmen, um dein Kurve zu approximieren. Du könntest zum Beispiel eine Spline-Interpolation mit fester Anzahl an Interpolationspunkten verwenden und dann die Position der Interpolationpunkte über ein Optimierungsverfahren bestimmen.

Meine Kurve ist eine Kette von Linien, Kreissegmenten und Spiralsegmenten. Also z.B. Linie, Spirale, Kreis, Spirale, Linie, Linie etc.

Die Linie zu sampeln ist natürlich trivial und im Kreissegmenten macht eigentlich nur eine feste Schrittweite Sinn. Nur in der Spirale nimmt die Krümmung zu oder ab. Hier könnte ich irgendwie adaptiv sampeln.

Wenn du die Kurve schon in dieser Form gegeben hast, warum willst du sie dann nicht einfach so speichern? Oder ist deine Frage, wie du die Kurve möglichst gut durch kurze Linien approximieren kannst?

Ich muss diese "höhere" Kurve für ein anderes Dateiformat in eine Punktkette konvertieren.

SeppJ

Curvor schrieb:

Ich muss diese "höhere" Kurve für ein anderes Dateiformat in eine Punktkette konvertieren.

Und dieses Format, wenn man es wieder interpretiert, wie geht das? Werden da einfach stumpf Linien durch die Punkte gezogen?

Ja, da werden dann einfach die Punkte mit Linien verbunden.

Wieso stellt ihr ständig neue Fragen, die gar nix mit der Kernfrage zu tun haben? Is doch letztlich total egal, WIESO ich Punkte brauche. Ich muss die Linien/Kreis/Spiral Kurve eben in Punkte zerlegen!

SeppJ

Curvor schrieb:

Wieso stellt ihr ständig neue Fragen, die gar nix mit der Kernfrage zu tun haben? Is doch letztlich total egal, WIESO ich Punkte brauche. Ich muss die Linien/Kreis/Spiral Kurve eben in Punkte zerlegen!

Du kannst dir wirklich nicht vorstellen, wozu diese Gegenfragen gut sind? Hast du denn nicht selber über das Problem nachgedacht?

Wie dir vielleicht auffällt, hast du deine Kurve schließlich bereits als eine Menge Punkte vorliegen, nämlich die Punkte, wo Linen-, Kreis- und Spiralsegmente ineinander übergehen. Das wäre nämlich eine mögliche Art, eine Kurve sehr clever in Punkte zu zerlegen. Das mussten wir dir also erst aus der Nase ziehen, dass es diese Methode nicht sein soll. Und auch keine der vielen anderen cleveren Möglichkeiten, sondern anscheinend die allereinfachste. Das geht alles nicht aus deinem Eingangsbeitrag hervor. Zudem kann man durch das Wissen, dass deine Kurve jetzt bereits als Linen-, Kreis- und Spiralsegmente gegeben ist, auch ganz einfache Abkürzungen bei der Umwandlung erkennen. Beispielsweise kann man schließlich alle Linien unberührt lassen, wenn das Zielformat sowieso auf Linien basiert. Und wenn man weiß, dass alle Kurven entweder Kreise oder Spiralen sind, dann weiß man eine Menge über das mögliche Krümmungsverhalten und kann dieses Wissen nutzen.
Wenn deine Kurve hingegen anders gegeben wäre, dann könnte man vielleicht ganz andere Dinge nutzen oder hätte ganz andere Einschränkungen.

Deshalb stellen wir Gegenfragen.

Und auf meine ursprüngliche Frage hat nach wie vor niemand eine Antwort gegeben. Kann geschlossen werden. Hab in einem anderen Forum eine hilfreiche (!) Antwort bekommen.

Jester

Also ich kann die Reaktion des OP voll und ganz nachvollziehen.

Nathan

Curvor schrieb:

Hab in einem anderen Forum eine hilfreiche (!) Antwort bekommen.

Wirklich? Find zu dem Thema nichts bei Google aus der letzten Woche...

volkard

Mein Vorschlag:
Du hast also Geradensegmente, Kreissegmente und Spiralsegmente.

- Alle Berührungspunkte zwischen den Segmenten werden übernommen. Das ist wichtig, wenn die Quelle einen absichtlichen Knick macht, so wollen wir genau folgen und ihn nicht verrunden. Wenn die Quelle den Kreis genau an die Gerade anschmiegt, wollen wir so genau bleiben, wie Gerade und Kreis es darstellen können. Gleiche Abstände fallen dann schonmal weg.

- Geradensegmente erzeugen keine weiteren Punkte. Auch ein Grund gegen gleiche Abstände.

- Kreissegmente: Es war es früher üblich, in der Cumputergrafik Kreise durch 72 Geraden am Umfang darzustellen, man sagte, ab 72 sei es rund genug, um nicht aufzufallen. Machen wir es auch so. Den Öffnungewinkel des Kreissegments mal 5 rechnen und aufrunden, dann hat man die Gradzahlen wo ich die Punkte setzen würde und dann isses wohl glatt genug.

- Spiralsegmente: Genauso! Wo der "Radius" kleiner ist, kommen durch die gleichen Winkelabstände automatisch mehr Punkte. Und es ist insofern genausogut wie die Glätte am Kreissegment, weil ich die Spirale abschnittweise betrachtet wie einen Kreis sehe.

ps: Die Fragen waren doch nötig. Anderenfalls hätte ich hier nur ein paar Allgemeinplätze brummeln können: adaptive Verfahren mit noch zu erstellenden Heuristiken, Approximationen,…

~Und dann wäre noch die Frage, ob die Linienzüge beliebig vergrößert werden können sollen, wie die hübsch geschwungen Kanten an Buchstaben. Wenn ja, wäre es hiermit fertig. Wenn nein, könnte man bei sehr kleinen Radien von der 72 runtergehen, im Bereich wo ein Kreisumfang aus 16 Pixels besteht, werden vielleicht auch 6 Randpunkte reichen.~

Nathan schrieb:

Curvor schrieb:

Hab in einem anderen Forum eine hilfreiche (!) Antwort bekommen.

Wirklich? Find zu dem Thema nichts bei Google aus der letzten Woche...

Ich wäre auch recht neugierig, was die anderen vorgeschlagen haben.

berniebutt

Was macht ihr euch so viele Gedanken um eine unklar gestellte Aufgabe?

Die Planer von Strassen- und Eisenbahntrassen kennen so etwas: Gerade, Kreis, Klothoide.
Auf der Baustelle braucht man aber zum Abstecken der Trasse nur feste Abstände,
schon wegen der Querschnitte und Mengenberechungen.

Ich betrachte diesen Thread als praxisfern, solange wir den genauen Hintergrund nicht wissen.

Curvor schrieb:

Wieso stellt ihr ständig neue Fragen, die gar nix mit der Kernfrage zu tun haben? Is doch letztlich total egal, WIESO ich Punkte brauche. Ich muss die Linien/Kreis/Spiral Kurve eben in Punkte zerlegen!

Du hast geschrieben, dass du die Kurve "clever" in Punkte "zerlegen" willst. Eine Kurve hat in der Regel unendlich viele Punkte. Was du mit "clever" und mit "zerlegen" meinst ist mir von Anfang an nicht klar gewesen. Darum die Fragen. Aber bei so einer Reaktion habe ich auch keine Lust, Zeit für dich aufzuwenden. Das Thema ist für mich beendet.

Jester