Hi, ich hab schon des öfter an folgendem Problem rumgeknabbert, aber
bislang noch keinen Ansatz für eine brauchbare Lösung gefunden.
Es geht darum, eine "gutmütige" Funktion
durch einen kubischen Bézier anzunähern.
Eine anschauliche Erklärung für Béziers gibt Onkel Wiki:
http://de.wikipedia.org/wiki/Bézierkurve#Kubische_B.C3.A9zierkurven_.28n.3D3.29
Kubische Béziers werden von SVG unterstützt (Kommandos s,S,t,T in path).
Man kommt also zwangsläufig auf die o.g. Problemstellung, wenn man
versucht, eine gute Approximation einer Kurve in SVG anzugeben.
Dazu wird die Kurve zunächst in Teilstücke zerlegt. Dieses Problem kann
als gelöst angesehen werden. Es verbleibt die Approximation der
Teilstücke durch je einen kubischen Bézier.
Der Bézier ist gegeben durch 4 Kontrollpunkte P0...P3: Die zwei
Randpunkte P0=ƒ(0) und P3=ƒ(1) sowie durch 2 weitere Punkte, die idR
nicht auf ƒ liegen, und diese Kontrollpunkte gilt es zu bestimmen.
Eine Reduktion des Problems ergibt sich dadurch, daß die Strecke P0-P1
den Bézier in P0 tangiert; analog gilt für P2, daß die Strecke P2-P3 den
Bézier in P3 tangiert.
Daher ist eine sinnige Wahl, P1 auf der Tangenten an ƒ durch den
Startpunkt P0 zu wählen, analog dazu wählt man P2 auf der Tangenten an ƒ
durch den Endpunkt P3.
Es verbleibt ein 2-dimensionales Problem: P1 kann man auf der Tangente
durch den Startpunkt hin- und her schieben; P2 auf der Tangenten durch
den Endpunkt.
Als Sprache für die Implementierung habe ich JavaScript angedacht, weil
es zum einen leicht via Internet benutzbar ist und mittels eval() sehr
leicht ist, Ausdrucke auszuwerten. Ein ausgewachsener numerischer
Zauberkasten steht also nicht zur Verfügung.
Das gegebene Kurvenstück soll nicht in Teilkurven zerlegt werden, da
dieses Problem wie gesagt bereits als gelöst angesehen werden kann.
Hat vielleicht jemand ne Idee, wie man das angehen kann?
Als "Arbeitskurve" hier noch das Beispiel eines Viertelkreises, hier mal
in verschiedenen Parametrisierungen mit einem q > 0 und t in [0,1]:
Die angehängte Grafik zeigt einen Viertelkreis (schwarz) und eine
Annähreung durch einen kubischen Bézier (orange, Kontrollpunkte rot).
D. I. schrieb:> Warum Bezierkurven und warum gerade Grad 3?
Es geht um die Darstellung in SVG, und das höchste der Gefühle sind
kubische Bézierkurven:
http://www.w3.org/TR/SVG/paths.html#PathDataCubicBezierCommandshttp://de.wikipedia.org/wiki/SVG#Pfad
Eine Strecke kann ebenfalls als kubischer Bézier aufgefasst werden,
abenso quadratische Béziers. Ansonsten bietet SVG nur noch
Ellipsenbögen, aber die sind weit weniger leistungsfähig.
> Was weißt du über die Funktionen die du annähren willst noch?
Die Funktionen sind "gutmütig", d.h. die x- und die y-Komponente sind
beliebig oft differenzierbar und damit auch stetig.
Ohne Einschränkung kann davon ausgegangen werden, daß die Funktion das
Intervall I=[0,1] in die Fläche abbildet, das Bild von ƒ ist also ein
Kurvenstück. Zudem ist ƒ injektiv, d.h. kein Punkt der Fläche wird von ƒ
zweimal (oder öfter) getroffen.
Allerdings kann ƒ singuläre Punkte enthalten. Ein Beispiel ist
was in t=1/2 eine Spitze ausbildet und aussieht wie
http://en.wikipedia.org/wiki/File:Cusp.svg> Willst du approximieren oder interpolieren?
Es geht um eine Approximation, d.h. man hat prinzipiell jeden
Funktionwert ƒ(t) zu Verfügung und kann diesen verwenden.
ƒ ergibt sich i.d.R als Parametrisierung einer Kurve, z.B. eines
Kreises, einer Lemniskate, Kartesischen Blatt, Cassini'schen Kurve, etc.
Wichtig ist im Endeffekt jedoch nur das Aussehen der Kurve, nicht ihre
konkrete Darstellung bzw. Parametrisierung.
So sind oben unterschiedliche Parametrisierungen für einen Viertelkreis
angegeben; jede dieser Darstellungen ist anders und durchläuft das
Kreisstück mit einer anderen Geschwindigkeit, aber das enstehende Bild
ist immer das selbe.
Johann L. schrieb:> Wichtig ist im Endeffekt jedoch nur das Aussehen der Kurve, nicht ihre> konkrete Darstellung bzw. Parametrisierung.
Du kannst dir den Inkscape Sourcecode laden, die haben eine
"Vektorisierungsfunktion" welche vermutlich einen Ähnlichen Ansatz
verfolgt.
Läubi .. schrieb:> Johann L. schrieb:>> Wichtig ist im Endeffekt jedoch nur das Aussehen der Kurve, nicht ihre>> konkrete Darstellung bzw. Parametrisierung.> Du kannst dir den Inkscape Sourcecode laden, die haben eine> "Vektorisierungsfunktion" welche vermutlich einen Ähnlichen Ansatz> verfolgt.
äh... das ist jetze nicht ernst gemeint, oder?
DU meinst wirklich, ich soll aus einer explizitn Darstellung erst mal
Pixelbrei erzeugen, dann nen Grafik-Filter drübernudeln und dann Kanten
suchen gehen (Sobel, Laplace)? Die Genauigkeit wird wohl deutlich unter
einem Pixel liegen und rau sein. Zudem liefern solche Verfahren
garantiert ne ganze Horde von (Teil-)Kurven und nicht eine einzige.
Natürlich nicht... Aber wenn die Kanten gefunden sind muß da doch auch
aus der "Funktion" irgendwas gemacht werden...
Vermutlich wäre die "Füllfunktion" besser geeignet, ich nutze das immer
ganz gern um (flächige) Grafiken nach SVG zu wandeln, das klappt ganz
gut und gibt garnichtmal soooo viele Kurven probiers halt einfach mal
aus:
Erzeuge eine Grafik lade die in Inkscape und nutz das Füllwerkzeug um
das ganze mit einer Fläche zu füllen. Dann kannst du dir den Pfad
welchen er daraus erzeugt im XML Editor anschauen (oder halt die Datei
speichern).
Es geht ja nicht darum, ein Bildchen zu erzeugen, daß "ungefähr so
aussieht wie" die richtige Kurve, sondern um Ideen für einen
Approximationsverfahren.
Für quatratische Bézierkurven ist es einfach:
1) Die Kurve wird durch einen Algorithmus in Teilstücke zerlegt
2) Die Endpunkte der Teilstücke stellen die Enpunkte der quadratischen
Béziers dar. Der (einzige) Kontrollpunkt des Q-Béziers ergibt sich als
Schnittpunkt der Tangenten an die Kurve (in den Endpunkten).
Kubische Béziers sind leistungsfähiger als quadratische: nach diesem
Verfahren bestimme Béziers 2. Ordnung berücksichtigen nicht den
Kurvenverlauf zwischen den Endpunkten, sie ergeben sich allein aus
Eigenschaften an den Enden der zu appriximierenden Kurve. Mit Béziers 3.
Ordnung kann die Tagnentenbedingung erfüllt werden, und man hat noch
zusätzlichen Gestaltungsspielraum.
Bei den Béziers 2. Ordnung verwendet man die 0. Ableitung -- also die
Funktionswerte -- in den Endpunkten sowie die 1. Ableitung, d.h. die
Richtung, die die Kurve dort hat.
Eine Idee war, das für Béziers 3.Ordnung dahingehend zu erweitern, auch
die 2. Ableitung in den Endpunkten zu verwenden, um die Lage der
Kontrollpunkte auf der jeweiligen Tangente zu bestimmen. Das führt zu
einem linearen Gleichungssystem, das leicht lösbar ist.
Die 2. Ableitung hat aber eine unangenehme Eigenschaft: sie ist von der
Parametrisierung der Kurve abhängig, während die 1. Ableitung dies
nicht ist.
Eine verwendbare Invariante wäre z.B. die Krümmung der Originalkurve in
den Endpunkten. Zur Erinnerung: die Krümmung k (der Kehrwert des Radius
des Schmiegekreises) ist gegeben durch
mit den Komponentenfunktionen x und y.
k ist invariante gegenüber Reparametrisierung, allerdings führt die
Definition von k auf implizite Gleichungen höherer Ordnung für die
Kontrollpunkte.
Johann L. schrieb:> Es geht ja nicht darum, ein Bildchen zu erzeugen, daß "ungefähr so> aussieht wie" die richtige Kurve, sondern um Ideen für einen> Approximationsverfahren.
Na eben diese Ideen wird sich wohl jemand schon gemacht haben! Denn eine
Pixellinie ist doch auch nichts anderes als eine (diskrete) Funktion die
dann (vermutlich mittels kleinster Fehlerquadrate oder so) an eine
Spline angenähert wird.
Das man es bei einem Bild schwerer hat (man muss ja erst die "Funktion"
extrahieren) ändert doch nix daran das dort (vermutlich) ein passendes
Verfahren zum Einsatz kommt.
Johann L. schrieb:> Ok, ich werd's mir mal zu Gemüte führen:>> 2.3.2 A Class of Bézier Curves>> http://potrace.sourceforge.net/potrace.pdf
Wirklich brauchbar ist das dort verwendete Verfahren leider nicht:
> we restrict ourselves to curves that are convex
und weiter:
> We can see immediately from the illustration that the Bezier> curves [...] are visually almost indistinguishable,> except perhaps in the case when α or β are very close to 0.> We will see that our algorithm never produces> Bezier curves with a and b very small, so that we can ignore> the latter possibility. It follows that we do not lose any> interesting curves if we restrict ourselves to the case α = β.> This eliminates one degree of freedom from the set of possible> Bezier curves that we need to consider, and thus it simplifies> our task of finding optimal curves.
Gute Kurven zu finden bedeutet da, Kurven zu finden, die
"gut und ungefähr so aussehen" wie die Polygone, die aus dem
Pixelbrei erhalten werden.
Von den 2 Dimensionen, in denen Lösungen gesucht werden können,
wird eine Dimension direkt weggelassen, und die verbleibendem Kurven
auf ein kleines Intervall zurechtgestutzt indem z.B. nur konvexe Kurven
betrachtet werden oder Eigenschaften der vorgeschalteten Verfahren
verwendet werden.
Probeweise hab ich inkscape mit einer Normalparabel gefüttert, gepixelt
mit einer Auflösung von 2000 Pixeln. Eine Parabel ist überigens durch
einen einzigen quadratischen Bézier darstellbar.
Inkscape produziert ca. 30(!) kubische Béziers; zudem ist die
Koordinateninformation komplett verlorengegangen, d.h. man muss die
Ausgabe erst noch einer linearen Trafo unterziehen (die man erst finden
und anwenden muss), um wirklich die Approximation an die Originalkurve
zu erhalten.
Für einen Vektorisierer ist diese herangehensweise auch ganz ok,
warum sollte Gehirnschmalz darauf verwendet werden, ein Verfahren
zu entwickeln/implementieren, das genauer ist, als die Pixels hergeben
oder es wahrgenommen wird?
Die Erleuchtung ist aus dieser Ecke also nicht wirklich zu erwarten :-(
Johann L. schrieb:> Auflösung von 2000 Pixeln
Viel hilft hier leider nicht immer viel, eine höhere Auflösung hat bei
mir oft auch eher zu einer Verschlechterung geführt :(
Johann L. schrieb:> Inkscape produziert ca. 30(!) kubische Béziers
Für eine ersten Wurf doch okay, es soll halt versucht werden möglichst
gut die Form zu approximieren, eventuell mal etwas mit den
Glättungsparametern spielen.
Mitte: dein "Bitmapisiertes" Beispiel.
Links: Das Ergebnis nach Anwendung des Füllwerkzeuges
Rechts: Anwenden der Inkscapefunktion "Pfad optimieren"
Ergebnis des "oberen Kreissegmentes:"
1
M 1.5848746,-0.35290595
2
C 1.587156,-0.45327866 1.569504,-0.5529803 1.542125,-0.648875
Bleiben noch zwei... nach jedem Optimierungsvorgang "rutscht" der
verbliebene Punkt etwas nach oben um letztendlich nach etwa 10
Vereinfachungsschritten zu folgendem Ergebnis zu kommen:
1
M 1.5848746,-0.35290595
2
C 1.585082,-0.95642792 1.0462908,-1.4928934 0.4483445,-1.5157838
Mit meinen bisherigen Verfahern bekomm ich das für einfache Fälle auch
hin.
Ich hatte nur gehofft, hier kämen vielleicht ein paar neue Idee auf.
Der Lösungsraum vom R² zu einem Intervall zu stutzen entfernt IMHO zu
viele Lösungen, und Voaraussetzungen wie Konvexität sind auch nicht
erfüllt. Sicher, man bekommt schöne Grafiken, aber es gibt auch keine
Fehlerabschgätzung, und das "Optimieren" vergrößert die Fehler weiter.
IdR sind die Kurven offen, Beispiel ist ne Archimedische Spirale.
Schwierigere Kurven wie sin(x)/x, sin(1/x) oder Cirps lassen sich damit
nicht behandeln.
Vielleicht gibt's ja noch kreative Ideen :-)
Johann L. schrieb:> Vielleicht gibt's ja noch kreative Ideen :-)
Also ich check ehrlich gesagt nicht so ganz was dein "Ziel" ist.
Einmal sind es dir zu viele Kurven, dann zu wenig, oder nicht die
richtigen oder dann doch nicht so wie du dir das vorgestellt hast...
Erst ist alles "gutmütig" dann darf der Algorithmus aber wieder keine
Randbedingungen (z.B. konvexität) haben und soll mit "schieriegen"
Funktionen klarkommen...
Willst du eine Art "SVG-Funktionsplotter" bauen? Oder Messwerte
interpolieren und dann eine (Spline-)Funktion daraus bilden?
Läubi .. schrieb:> Johann L. schrieb:> Also ich check ehrlich gesagt nicht so ganz was dein "Ziel" ist. [...]> Willst du eine Art "SVG-Funktionsplotter" bauen?
Ja. Es soll ein Plotter werden. Die Ausgabe besteht nicht aus einer
Pixel-Grafik, sondern aus einer Anzahl von Bézierkurven.
Als Sprache habe ich JavaScript angedacht. Zum einen ist das webfähig,
zum anderen ist es sehr einfach, Ausdrücke wie "sin(x)" auswerten zu
lassen, wenn das als Zeichenkette angegeben wird.
Die Kurve liegt vor in Form ihrer Komponentenfunktionen, also z.B.
x(t) = cos(t*t)
y(t) = sin(t)
und dem Intervall, das t überstreichen soll, z.B.
t in [0,20].
Die Komponentenfunktionsn sollen mindestens 2 mal ststig diff'bar sein.
Das erste Problem, dem man sich gegenübersieht, ist, daß ein Bézier
nicht ausreicht, um eine hinreichend gute Approximation zu ergeben --
zumindest wenn dessen Grad auf 3 beschrängt ist, wie es in SVG der Fall
ist.
Man muss die Kurve also in Teilstückchen zerlegen. Zweckmässig ist dabei
eine Zerlegung, die unabhängig ist von der Gestalt der
Komponentenfunktionen. Anschaulich heisst das, daß die Zerlegung
unabhängig sein soll von der Geschwindigkeit, mit der die Kurve von der
jeweiligen Darstellung durchlaufen wird. Ganz oben ist das Beispiel
eines 1/4-Kreises. Je nach Parametrisierung, wied dieser mit
unterschiedlichen, nicht-konstanten Geschwindigkeiten durchlaufen.
Eine mögliche Größe, die invariant gegenüber Umparametrisierung ist, ist
z.B. die Länge der Kurve: Egal, wie dir Komponentenfunktionen für den
1/4-Kreis aussehen, seine Länge ist immer π/2 (es sei denn, er wird
mehrfach von der Parametrisierung überstrichen, wovon erst mal abgesehen
werden soll).
Um die Kurve in 10 Teilstücke zu zerlegen, könnte man sie also in 10
gleichlange Stücke aufteilen. Die Formel für die Länge einer Kurve ist
bekanntlich
und man rechnet leicht nach, daß sie unabhängig von der Parameterwahl
ist.
Die Länge hat allerdings einen entscheidenden Nachteil, sie
berücksichtigt keine Details der Kurve. In Bereichen, wo die Kurve
relativ glatt und unspektakulär ist, wird man weniger zerstückeln müssen
als in Bereichen, wo viel passiert.
Liegt ein Punkt P auf der Kurve, gibt es Invarianten, die ebenfalls
unabhängig von der konkreten Darstellung der Kurve sind. Eine davon ist
der Krümmingsradius des Schmiegekreises, gegeben durch
wobei positive/negative Radien Links/Rechtskrümmung beschreiben.
Nun kann man über die Krümmung integrieren, und erhält sowas wie den den
Richtungswechsel bzw. wie akkumulierte Krümmung der Kurve:
Auch für K ist leicht zu zeigen, daß es invariant gegenüber
Parameterwechsel ist.
K für einen 1/4-Kreis ist z.B π/2. Setzt man einen zweiten 1/4-Kreis
ohne Knick daran an, ergibt sich K=π und zwar egal ob er link- oder
rechtsrum gekrümmt ist und welchen Radius er hat. Anschaulich summiert
man alle Richtungswechsel einer Tangente, die man an der Kurve
entlanglaufen lässt.
Dieses K verwende ich nun, um die Kurve in Teilstücke zu zerlegen. Die
Teilstücke sind so zerlegt, daß jedes in etwa das gleiche Detailreichtum
hat. Man kann z.B. festlegen, daß kein Teilstück einen Richtungswechsel
von mehr als 45° macht.
Das ist die o.g. Zerlegungsproblem, das als gelöst angesehen werden
kann. Die erhaltenen Teilstücke sind jedoch i.d.R. nicht konvex, und
auch eine weitere Zerlegung garantiert nicht die Konvexität der
Teilstücke.
Die müsste möglicherweite ein Zwischenschritt eingefügt werden, der,
falls bei der Berechnung von K ein Vorzeichenwechsel der Krümmung
erkannt wird, die Kurve möglichst dicht am Wendepunkt aufteilt.
Andererseits sind kubische Béziers in der Lage, Wendepunkte
darzustellen, und es ist nicht einzusehen, warum diese Eigenschaft nicht
genutzt werden sollte.
Zudem haben 3-Béziers gegenüber 2-Béziers zwei weitere Freiheitsgrade,
welche für die Approximation der Teilstücke genutzt werden können.
Abermals ist nicht einzusehen, auf einen kompletten Freiheitsgrad zu
verzichten, und den zweiten auf das Intervall [0,1] zu beschränken.
Für die Approximation habe ich einige Ansätze ausprogrammiert, die je
nach Kurve gute bis sehr gute ergebnisse liefern, für andere jedoch sehr
bescheidene.
Bei diesen Anzätzen hat man 8 Freiheitsgrade, denn ein 3-Bézier ist
durch seine 4 Kontrollpunkte eindeutig bestimmt. Die Endpunkte des
Béziers legt man an die Endpunkte der (Teil)Kurve; es verbleiben 4
Freiheitsgrade. Weiters ist geschickt, die Kontrollpunkte auf die
Tangenten durch die Endpunkte zu legen; es verbleiben 2 Freiheitsgrade.
Eine Idee war, Punkte auf der Kurve zu wählen und zu fordern, daß der
Bézier hindurchläuft. Aufgrund der Lage der Kontrollpunkte auf den
Tangenten und des Ausbaus von Béziers erhält man ein lineares
Gleichungssystem in 2 Variablen (die 2 Freiheitsgrade) der Gestalt
das bei Vorgabe von m weiteren Punkten jedoch 2m Gleichungen enthält und
somit überbestimmt ist. Least-Square führt auf das System
das nur noch 2 Gleichungen für 2 Variablen enthält und leicht gelöst
werden kann.
Der Nachteil ist hier, daß die Lösung von der Parametriesierung abhängt.
Oft ist die Lösung mies, weil die Kurve in einer ganz anderen
Geschwindigkeit durchlaufen wird als dies für den Bézier der Fall ist.
Eine gute Parametrisierung zu finden ist u.U. überaus mühsam; auch hab
ich versucht, das ganze als Variationsproblem zu formulieren mit einer
Reparametrisierung als Unbekannten, jedoch ist das entstehende
Variationsproblem viel zu kompliziert, als daß man es vernünftig
näherungsweise lösen könnte.
Eine andere, naheliegende Idee ist, 2 Punkte im Innern zu wählen und als
Approximation Bernsteinpolynome zu verwenden, siehe z.B.
http://de.wikipedia.org/wiki/Bernsteinpolynome#Approximation_durch_Bernsteinpolynome
Leider sind diese Approximationen eher von theoretischem Interesse und
für einen praktischen Einsatz nicht tauglich; die Annäherung geht zu
langsam mit dem Grad der Bernsteinpolynome.
Eine weitere Idee war, geometrische Eigenschaften an den Randpunkten zu
verwenden. Die 2-te ABleitung taugt übrigens nicht dafür, weil sie nicht
Invariant unter Parameterwechsel ist. Verwendbar wäre die Krümmung, aber
alles deutet darauf hin, daß diese Idee auch nicht gut ist.
Daher meine Frage hier im Forum. Die Aufgabenstellung ist ja sehr
anschaulich und leicht zu fassen, und van daher hatte ich gehofft, ein
paar neue Ideen zu bekommen.
Johann L. schrieb:> Die Aufgabenstellung ist ja sehr> anschaulich und leicht zu fassen
Also der Länge deines Beitrags zu urteilen haben wir beide ein etwas
verschiedenes Verständnis von "leicht und anschaulich" ;)
Da die Funktion kennst wäre möglicherweise folgender Ansatz möglich:
1) Zerlege die Kurve in Stücke sodass eine eindeutige Abbildung f(x) = y
entsteht.
2) für n = 1...Anzahl Stücke
2.1) Wählst im Intervall des n-ten Funktionsstücks äquidistante Punkte
(z.B. im Abstand 0.5) und Berechne die zugehörigen Funktionswerte.
2.2) Mit der Methode der kleinsten Quadrate bestimmst du nun eine
Bezierkurve durch diese Punkte
2.3) Wenn der Fehler
2.3.1) zu groß ist entfernst du den letzten Punkt (und fügst ihn der
"temp funktion" hinzu) und beginnst wieder bei 2.2.
2.3.2) innerhalb der Grenzen ist nutze die Kurve als Approximation
2.4) Wenn die "temp funktion" Punkte enthält setze diese als Kurvenstück
und gehe zu 2.2
3) Hoffentlich hast du nun das gewünschte Ergebnis, ggf. muss man an den
Randstücken noch sicherstellen, dass die Steigung übereinstimmt, da
hatten wir in Numerik mal ein Verfahren, was wir aber gerade entfallen
ist.
Das Verfahren müsste sich dann beliebig verfeinern lassen indem die
Schrittweite verringert wird.
Läubi .. schrieb:> Johann L. schrieb:>> Die Aufgabenstellung ist ja sehr>> anschaulich und leicht zu fassen> Also der Länge deines Beitrags zu urteilen haben wir beide ein etwas> verschiedenes Verständnis von "leicht und anschaulich" ;)
Daß die Beschreibung des Problems leicht zugänglich ist, heisst ja
nicht, daß es Lösungsansätze auch sind ;-)
Ja der Beitrag ist recht lang geworden, weil ich darstellen wollte,
welche Probleme auftauchen.
> Da die Funktion kennst wäre möglicherweise folgender Ansatz möglich:> 1) Zerlege die Kurve in Stücke sodass eine eindeutige Abbildung f(x) = y> entsteht.
Die Zerlegung in solche Stücke ist einfach, allerdings kennt man damit
noch nicht die Funktionsgleichung! Die Parameterfunktionan sind fx(t)
und fy(t). Durch die Aufteilung kann man z.B. fordern, daß der
Richtungswechsel kleiner als 180° ist. Die Endpunkte der Teilkurve
bildet man dann durch eine lineare Abbildung z.B. auf (0,0) und (1,0) ab
und erhält Komponentenfunktionen X(t) und Y(t) wobei X(t) stetig ist und
streng monoton wächst. Man kann also t auf die x-Achse abbilden, aber
wie kehr man X allgemein um? Das ist nämlich nötig, um eine Funktion in
der Gestalt "f(x)=y" zu bekommen. Obwohl man weiß, daß die Teilkurve
eine solche Darstellung hat, ist die Kurve immer noch durch gegben durch
X(t) und Y(t), eine explizite Darstellung als Funktion R→R hat man
nicht, es ist immer noch eine Darstellung R→R²
> 2) für n = 1...Anzahl Stücke> 2.1) Wählst im Intervall des n-ten Funktionsstücks äquidistante Punkte> (z.B. im Abstand 0.5) und Berechne die zugehörigen Funktionswerte.
Ok, ist aufwändige Sucharbeit, die man so oder so ähmlich auch bei der
Zerlegung zu machen hat.
> 2.2) Mit der Methode der kleinsten Quadrate bestimmst du nun eine> Bezierkurve durch diese Punkte> 2.3) Wenn der Fehler> 2.3.1) zu groß ist entfernst du den letzten Punkt (und fügst ihn der> "temp funktion" hinzu) und beginnst wieder bei 2.2.
Welche temp-Funktion? Was, wenn keine Punkte mehr überbleiben?
Das Problem mit dem Kleinste-Quadrate-Verfahren ist, daß egal wieviel
punkte man auch nimmt, daß keine Garantie für einen kleinen Fehler ist.
Stell die eine Kurve vor und eine Bézierkurve, die ungefähr so verläuft
wie diese Kurve. Stell dir weiter vor, daß sich die Kurven mit
wachsendem Parameter z.B. rot färben. Ist die Kurve so dargestellt, daß
sie sich gleichschnell wie der Bézier einfärbst, dann funktioniert
Least-Square gut. Wenn die Kurve sich anfange viel schnell färbt als der
Bézier, dann temdiert der Bézier dazu, gegen Ende einen Buckel
auszubilden. Dieser Buckel wird nicht kleiner, egal wieviel Punkte man
hinzunimmt. Das Problem ist die nicht-optimale Parametrisierung. Eine
Parametrisierung sichen zu gehen, habe ich beslang wegen der Komplexität
der Ausgabenstellung jedoch nicht in Erwägung gezogen.
> 2.3.2) innerhalb der Grenzen ist nutze die Kurve als Approximation
Hier gibt es ein weiteres Problem, nämlich die Güte der Approximation zu
bewerten. Das ist eine Aufgabe, für die ich auch noch keine praktikable
Idee hab.
Hat man zwei Funktionen f und g, die beide ein Intervall I in R^n
abbilden, ist eine Metrik
war ziemlich aufwändig anzunähern ist.
> 2.4) Wenn die "temp funktion" Punkte enthält setze diese als Kurvenstück> und gehe zu 2.2> 3) Hoffentlich hast du nun das gewünschte Ergebnis, ggf. muss man an den> Randstücken noch sicherstellen, dass die Steigung übereinstimmt, da> hatten wir in Numerik mal ein Verfahren, was wir aber gerade entfallen> ist.> Das Verfahren müsste sich dann beliebig verfeinern lassen indem die> Schrittweite verringert wird.
Das machen tatsächlich viele Verfahren. Sie wählen einfach eine winzige
Schrittweite und Nähern die Kurve durch einen Polygonzug an. Wenn man
die Schrittweite nur klein genug macht, sieht die Kurve auf dem
Stückchen ja fast aus wie eine Gerade. Allerdings muss man, um den
Fahler zu halbieren, die Schrittweite verdoppeln, etc. Kurven höherer
Ordnung sind da viel besser.
Ziel ist ja, möglicht wenige, dafür aber guten Teilapproximationen zu
erhalten, nicht umgekehrt.
Luk4s K. schrieb:> Ohne jetzt alles durchgelesen zu haben...
Das ist ein häufiger Fehler...
> Inkscape hat einen Funktionsplotter eingebaut, vielleicht ist dieser> einen Blick wert.
..weil er das natürlich schon gemacht hat.
Иван S. schrieb:> ..weil er das natürlich schon gemacht hat.
Nein es ging um den Vektorisierer, der aus Rastergrafiken Vektorgrafiken
macht. Der Funktionsplotter ist 'was anderes.
Luk4s K. schrieb:> Der Funktionsplotter ist 'was anderes.
Kannste ich noch garnicht, wirklich fazinierend und vermutlich wirklich
genau das was gesucht wird, zumal auch noch in Phython verfügbar wie es
scheint.
Läubi .. schrieb:> Luk4s K. schrieb:>> Der Funktionsplotter ist 'was anderes.> Kannste ich noch garnicht, wirklich fazinierend und vermutlich wirklich> genau das was gesucht wird, zumal auch noch in Phython verfügbar wie es> scheint.
Exakt, liegt in /usr/share/inkscape/extensions/funcplot.py
Ich hab's mal kurz überflogen: sieht nicht übermäßig kompliziert aus...
Luk4s K. schrieb:> Иван S. schrieb:>> ..weil er das natürlich schon gemacht hat.> Nein es ging um den Vektorisierer, der aus Rastergrafiken Vektorgrafiken> macht. Der Funktionsplotter ist 'was anderes.
Tut mir leid, dann war ich wohl etwas vorschnell mit meinem Urteil.
Ich möchte mich daher hiermit förmlichst bei Dir entschuldigen!
Gruß, Iwan
Ich hab Inkscape mal angetestet für f(x) = sin (1/x), x0=1e-3, x2=1, 50
Stützstellen. Also das Ergebnis sieht nach allem aus nur nicht nach
dieser Funktion. Ob sich da ein Reverse-Engineering lohnt?
Johann L. schrieb:> Ich hab Inkscape mal angetestet für ...
Hast du den auch mal was "gutmütiges" getest? Ich dachte du suchst
Anregungen? Dass das ganze möglicherweise nicht optimal auf deinen
Einsatzzweck passt heißt ja nicht das man es nicht optimieren könnte...
Zugegebenermassen bin ich kein Fan von Inkscape. Hochwertige Grafiken
wie z.B.
http://upload.wikimedia.org/wikipedia/commons/e/ed/Zeta0.5_100.svg
oder
http://upload.wikimedia.org/wikipedia/commons/6/6f/Gjl-t(x).svg
lassen sich damit nicht erzeugen.
In der Vektor-Szene scheint inkscape ja ne heilige Kuh zu sein...
Für f(x) = sin(1/x) in [0.01, 2] hab ich mal die Ausgabe von Inkscape
angehängt (ink1.svg).
Inkscape plottet einfach blind drauflos. Diese Funktion ist beliebig oft
diff'bar in dem Intervall und sogar beschränkt. Das einzig auffällige an
der Funktion ist, daß sie Regionen mit unterschiedlichem Detailreichtum
hat.
Mit meinen eigenen Verfahren bekomm ich da wesentlich bessere Ergebnisse
(own.svg).
Zudem kümmert sich Inkscape überhaupt nicht um die Skalierung, d.h. man
kann nicht den path von Inkscape hernehmen und weiterverwenden. Weiß der
Geier warum da eine lineare Trafo angewandt wird. Es wär doch ein Klacks
eine Trafo einfach HINZUSCHREIBEN, ich versteh nicht, warum das nicht
gemacht wird?
Leider dreht sich die Diskussion die ganze Zeit darum, wie man in
Inkscape was zusammenclickt. Die zugrundeliegenden Algorithmen scheinen
nicht wirklich brauchbar, sobald die zu zeichnenden Funktionen etwas
anspruchsvoller sind. Plotten von Kurven wird nicht unterstützt, etc.
Was das Plotten angeht hab ich meine Ideen in
http://de.wikipedia.org/wiki/Benutzer:Georg-Johann/Mathematik#Cubic
zusammengefasst.
Johann L. schrieb:> Hochwertige Grafiken> wie[...] lassen sich damit nicht erzeugen.
Alles eine Frage des Aufwandes, wieso sollte das nicht gehen?
Johann L. schrieb:> In der Vektor-Szene scheint inkscape ja ne heilige Kuh zu sein...
Wenn du meinst... möglicherweise gibt es besseres Alternativen welche
verwendest du den? Inkscape hat seine Macken ist dafür kostenlos
verfügbar und unterstützt die SVG Spezifikation weitaus besser als alle
Programme die ich bisher kennen gelernt habe.
Johann L. schrieb:> Mit meinen eigenen Verfahren bekomm ich da wesentlich bessere Ergebnisse
Nun versteh ich ehrlichgesagt garnix mehr... Ich denke du sichst noch
ein Verfahren und nun zauberst du deine Implementierung aus dem Hut
welche das Problem schon zu lösen scheint?
Johann L. schrieb:> Es wär doch ein Klacks
Das ist jetzt natürlich ein Vorteil von Inkscape, da das ganze im
Quellcode vorliegt ist es ja ein Klacks das mal eben zu ändern ;)
Johann L. schrieb:> Zudem kümmert sich Inkscape
Wie gesagt, das ist keine Inkscape Funktion sondern ein
"Erweiterungsskript" es hindert dich keiner das mal eben
anzupassen/optimieren, du könntest das ganze dann sogar wieder komitten
sodass andere davon profitieren.
Georg, bekleidest du eine Professur oder sowas?
Deine Ausführungen sehen mathematisch gut durchdacht aus. Ich verstehe
sie nämlich nur bruchstückhaft. Das scheint aber bei dir nicht der Fall
zu sein ;-)
Rehspeck!
Läubi .. schrieb:> Johann L. schrieb:>> In der Vektor-Szene scheint inkscape ja ne heilige Kuh zu sein...> Wenn du meinst... möglicherweise gibt es besseres Alternativen welche> verwendest du den?
Für Kurven-Plots mach ich das halbautomatisch: Die eigentliche
Approximation bekomm ich aus eigenen Algorithmen, die zugegenermassen
Potential für Verbesserung haben.
Den erzeugten PATH kopiere ich dann in ein SVG. Das alles ist weniger
Aufwand und liefert bessere Ergebnisse als Inkscape (oder was auch immer
da noch dranhängt): Die Koordinaten entsprechen den wirklichen
Koordinaten der Funktion und ist damit wiederverwendbar, die Verfahren
sind adaptiv, etc..
Was Inkscape und Standards angeht... wirf mal das ganze sodipodi-Zeugs
da raus, was dann noch übrig bleibt.
> Johann L. schrieb:>> Mit meinen eigenen Verfahren bekomm ich da wesentlich bessere Ergebnisse> Nun versteh ich ehrlichgesagt garnix mehr... Ich denke du suchst noch> ein Verfahren und nun zauberst du deine Implementierung aus dem Hut> welche das Problem schon zu lösen scheint?
Die Verfahren haben ihre Schwächen, und ich hab hier nach Ideen gesucht,
ohne die Leser hier mit meinen eigenen Implementierungen zuzutexten oder
eine Richtung vorgeben zu wollen. Vielleicht sind meine Ansätze ja
schlecht, und auch deshalb war die Frage erst mal nach Ideen, ohne die
Vorgabe was ich schon habe.
> Johann L. schrieb:>> Es wär doch ein Klacks> Das ist jetzt natürlich ein Vorteil von Inkscape, da das ganze im> Quellcode vorliegt ist es ja ein Klacks das mal eben zu ändern ;)
Scherzkeks :-) Hast du je versucht, was in Quelle zu ändern bei einem
großen Projekt, z.B. wenn dich was in GCC genervt hat. Zudem hab ich
nicht die Möglichkeit hier Inkscape zu generieren; mein armer Rechner
geht schon in die Knie, wenn ich den Riesenklotz an Software nur starte
;-)
Hast du je versucht, Inkscape zu generieren und alle benötigten
Abhängigkeiten aufzulösen?
> Johann L. schrieb:>> Zudem kümmert sich Inkscape> Wie gesagt, das ist keine Inkscape Funktion sondern ein> "Erweiterungsskript" es hindert dich keiner das mal eben> anzupassen/optimieren, du könntest das ganze dann sogar wieder komitten> sodass andere davon profitieren.
Was Inkscape angeht, da hab ich wirklich keine Ambitionen, dafür mag ich
Inkscape nicht genug.
Und wenn ich was einbaue, dann nur etwas, von dem ich überzeugt bin und
nachweisen kann, daß es funktioniert -- nicht nur was die Umsetzung
Formeln -> Code angeht, sondern auch was die zugrundeliegenden Formeln
angeht.
Gerade das haben die Schreiber des vorliegenden Plotters offenbar nicht
gemacht, was wiederum dazu führt, daß Anwender das Problem umgehen,
indem sie einfach wahnwitzig kleine Schrittweiten eingeben. Bei
wikipedia commons findet man teilweise Grafiken, die hunderte von
kilobytes oder megabyte groß sind, wo ein paar kb ausreichen würden --
ausgereifte Algorithmen zur Bestimmung der Approximation vorausgesetzt.
Ein seriöses Verfahren würde IMHO auch beihalten, Fehlerschranken
angeben zu können. Weil die Kurven, die zur Approximation verwendet
werden, Grad 3 haben, wird der Fehler bei Annäherung einer glatten Kuve
mit der 3. Potenz kleiner. Bei dem Inkscape-Verfahren würd ich meinen
A.... drauf verwetten, daß der Fehler bestenfalls linear kleiner wird
;-)
Ausserdem muss ein gites Verfahren notwendigerweise adaptiv sein. An
Stellen, die nicht viele Details haben, reichen weniger Elemente zur
Approximation aus als an Stellen, wo viel passiert -- sin(1/t) ist hier
nur ein Beispiel.
Johann L. schrieb:> Scherzkeks :-) Hast du je versucht, was in Quelle zu ändern bei einem> großen Projekt, z.B. wenn dich was in GCC genervt hat. Zudem hab ich> nicht die Möglichkeit hier Inkscape zu generieren; mein armer Rechner> geht schon in die Knie, wenn ich den Riesenklotz an Software nur starte> ;-)
Keine Bange, der Funktionsplotter steckt in einem kompakten
python-Skript, daran soll es nicht scheitern :)
Johann L. schrieb:> Was Inkscape und Standards angeht... wirf mal das ganze sodipodi-Zeugs> da raus, was dann noch übrig bleibt.
Inkscape kann auch als "normales" SVG speichern. Das läuft dann bis auf
ein paar xmlns Attribute problemlos durch den Validator.
Johann L. schrieb:> Hast du je versucht, Inkscape zu generieren und alle benötigten> Abhängigkeiten aufzulösen?
Wenn die verwendete Linuxdistribution ohnehin halb Quellenbasiert ist
(wie z.B. Arch Linux oder Gentoo) bekommt man die Buildskripte
mitgeliefert. Um Abhängigkeiten muss man sich dann auch keine Gedanken
mehr machen.
Luk4s K. schrieb:> Keine Bange, der Funktionsplotter steckt in einem kompakten> python-Skript, daran soll es nicht scheitern :)
Hab's eben mal überflogen:
-- das Verfahren ist nicht-adaptiv
-- für die Teilintervalle werden die x-Koordinaten der Kontroll-
punkte so gewählt, daß diese das Intervall im Verhältnis
2:1 bzw. 1:2 teilen. Damit ergibt sich genau das erste
Verfahren, das ich in
http://de.wikipedia.org/wiki/Benutzer:Georg-Johann/Mathematik#Cubic
für den Fall d²x/dx² = 0 abgeleitet habe.
Ich weiß nicht ob es für Dein Problem hilft, aber Gnuplot hat zum
Beispiel auch Beziers eingebaut. Die Interpolationsroutinen finden sich
in gnuplot/src/interpol.c (Funktion: cp_binominal)
1
cp_binomial() computes the binomial coefficients needed for bezier stuff
2
and stores them into an array...
3
* Method used: compute logarithms of these
4
* extremely large and small numbers, and only go back to the
5
* real numbers once they've cancelled out each other, leaving
6
* a reasonable-sized one.
Imagemagik wird wohl ebenfalls etwas ähnliches haben.
Gruß, Iwan
In der Funktion werden lediglich die Koeffizienten für Béziers —
übrigens beliebig hohen Grades — ausgerechnet. Die Verwendung erfolgt
dann in Casteljau-Manier, indem vorgegebene Punkte als Kontrollpunkte
hergenommen werden. That's it.
Die Spline-Berechnung in
http://gnuplot.sourcearchive.com/documentation/4.2.2-1/interpol_8c-source.html
beziehen sich nur auf skalarwertige Funktionen, also ist da auch nix zu
holen.
Ausserdem ist das Zeug kaum kommentiert. Da nach Ideen zu suchen,
gleicht wohl dem Versuch, in der Firmware eines Navigationssatelliten
nach den Feldgleichungen der Allgeneinen Relativitätstheorie suchen zu
wollen ;-)
Nachtrag: Um eine auf [0,1] definierte, stetige Funktion durch eine
gleichmässig konvergente Funktionenfolge anzunähern, kann man als
Folge nehmen
Genau das wird da gemacht, es gibt also nicht die Einschränkung auf
Kurven dritten Grades. Bricht man diese Entwicklung beim 3. Glied ab, so
stellt man fest, daß ƒ_3 bei gekrümmten Kurven eine "Abkürzung" nimmt,
was dazu führt, daß es bessere Approximationen gibt, nämlich solche,
deren Kontrollpunkte nicht auf der Kurve liegen so wie das bei den ƒ_n
der Fall ist, sondern ausserhalb der Kurve.
Ein Beispiel ist wieder der 1/4-Kreis von oben. Die Approximation ist
also nicht so gut wie sie sein könnte. (Zudem ergeben sich Knicke an den
Randpunkten)
Thread beobachten
Seitenaufteilung abschalten
.svg){kind=link}
