Ungefähre eine Liste von Punkten mit einer kurzen Liste von Bézier-Kurven

Question

Ich habe eine Liste von (x, y) Punkte. Ich weiß, wie man eine Liste von Bézier-Kurven erstellt, die alle diese Punkte durchlaufen und eine kontinuierliche erste (und zweite, wenn auch weniger wichtige) Ableitung haben. Allerdings ist die Liste, zu der ich komme, viel zu lang. Ich würde es vorziehen, die Punkte, die ich habe, anzunähern, wenn ich dadurch die Anzahl der Kurven, die ich habe, reduzieren kann. Ich würde gerne in der Lage sein, einen Parameter zu übergeben, entweder wie nahe eine Näherung ich bekomme oder eine maximale Anzahl von Kurven, vorzugsweise erstere.

Der Grund dafür ist, dass das Endergebnis über eine grafische Benutzeroberfläche verfügt, auf der Benutzer die Bézier-Kurven bearbeiten können, und es ist nicht kritisch, dass die Kurven genau durch jeden Punkt verlaufen, solange sie sich in der Nähe befinden. Mehr Kurven machen das Bearbeiten schwieriger.

EDIT: Einige weitere Informationen über den Zweck dieser. Ich versuche eine Bildbearbeitungssoftware zu erstellen. Wenn jemand eine Bitmap lädt, möchte ich in der Lage sein, eine Mittellinie zu verfolgen. Potrace ist, was ich verwenden würde, um den Umriss einer Form zu verfolgen, aber es wird nicht für die Verfolgung von Strichen funktionieren. Ich konnte viele Punkte entlang der Mittellinie identifizieren und diese Daten in eine Liste von verbundenen Bézier-Kurven umwandeln. Der Grund, warum ich keinen Bézier-Spline machen möchte, ist, dass es zu viele Kontrollpunkte geben wird, damit dies einfach zu bearbeiten ist. "Too many" ist kein einfach zu definierender Begriff, aber ich würde gerne einen Parameter übergeben können, um die Anzahl der Kurven zu begrenzen. Entweder eine Funktion, die minimiert, wie weit die Kurven von den Punkten entfernt sind, basierend auf einer maximalen Anzahl von Kurven oder eine Funktion, die die Anzahl der Kurven basierend auf einer maximalen Abweichung von den Punkten minimiert.

Answer 1

mehrere Ansätze existieren für das erreichen, was Sie tun möchten:

1) Verwenden Sie RDP-Algorithmus die Anzahl der Punkte zu reduzieren, dann eine Liste von Bezier-Kurven erzeugen durch die verbleibenden Punkte geht.

2) Verwenden Sie Kurvenanpassungsalgorithmen (z. B. Schneider-Algorithmus), um mehrere Bezier-Kurven zu erzeugen, die mit G1 (Tangens) -Kontinuität verbunden sind. Überprüfen Sie die Implementierung des Schneider-Algorithmus in dieser link.

3) Verwenden Sie die kleinste quadratische Anpassung mit B-Spline, um eine einzelne B-Spline-Kurve zu erzeugen.

Vom Standpunkt der Implementierung aus ist Ansatz 1 wahrscheinlich der einfachste für Sie, da Sie bereits wissen, wie Bezier-Kurven erstellt werden, die eine Liste von Punkten interpolieren. Ansatz 3 ist viel schwieriger zu implementieren und Sie müssen wahrscheinlich die B-Spline-Kurve in Bezier-Kurven umwandeln, um sie auf der Ebene der Benutzeroberfläche zu verwenden. Bitte beachten Sie diese SO article für eine detaillierte Diskussion.