mikrocontroller.net

Forum: Offtopic [Mathe]: Wie Funktion durch kubschen Bézier annähern


Autor: Johann L. (gjlayde) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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_...

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).

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Johann L. schrieb:
... das ist natürlich kein Viertelkreis.

So ist's richtig:

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Warum Bezierkurven und warum gerade Grad 3?

Was weißt du über die Funktionen die du annähren willst noch? Willst du 
approximieren oder interpolieren?

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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#PathDataCubicB...
http://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.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Sebastian S. (sebastians)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kannst dir auch mal den Source von OpenCasCADe anschauen. Wenn ich mich 
richtig erinnere, haben die eine Konvertierung in kubische Splines drin.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 :-(

Autor: Läubi .. (laeubi) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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:"
M 1.5848746,-0.35290595 
C 1.587156,-0.45327866 1.569504,-0.5529803 1.542125,-0.648875
  1.4877623,-0.82633628 1.3929342,-0.99202953 1.264625,-1.1265312
  1.1160437,-1.287159 0.92488802,-1.409188 0.71515625,-1.47125
  0.63414041,-1.495484 0.54937631,-1.50779 0.4653125,-1.514
  0.4591425,-1.51522 0.4534575,-1.51583 0.4483437,-1.51578
Immerhin schon mal 5 C-Beziers
Nach zweimaligem Optimieren wird daraus:
M 1.5848746,-0.35290595
C 1.5855492,-0.73251614 1.3682333,-1.0914093 1.0604433,-1.3046129
  0.88111188,-1.4294757 0.66712125,-1.5060424 0.4483445,-1.5157838
Bleiben noch zwei... nach jedem Optimierungsvorgang "rutscht" der 
verbliebene Punkt etwas nach oben um letztendlich nach etwa 10 
Vereinfachungsschritten zu folgendem Ergebnis zu kommen:
M 1.5848746,-0.35290595 
C 1.585082,-0.95642792 1.0462908,-1.4928934 0.4483445,-1.5157838
Ein wunderschöner Kreisbogen ;)

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 :-)

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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#App...
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.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Lukas K. (carrotindustries)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ohne jetzt alles durchgelesen zu haben: Inkscape hat einen 
Funktionsplotter eingebaut, vielleicht ist dieser einen Blick wert.

Autor: Иван S. (ivan)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Lukas K. (carrotindustries)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Иван 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.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Lukas K. (carrotindustries)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Иван S. (ivan)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es geht um einen Funktionsplotter

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?

Autor: Lukas K. (carrotindustries)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Johann L. schrieb:
> Also das Ergebnis sieht nach allem aus nur nicht nach
> dieser Funktion.

Den Haken bei Polarkoordinaten vergessen wegzumachen? ;)

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Johann L. (gjlayde) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Zugegebenermassen bin ich kein Fan von Inkscape. Hochwertige Grafiken 
wie z.B.
   http://upload.wikimedia.org/wikipedia/commons/e/ed...
oder
   http://upload.wikimedia.org/wikipedia/commons/6/6f...
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...
zusammengefasst.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Lukas K. (carrotindustries)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...
   für den Fall d²x/dx² = 0 abgeleitet habe.

Autor: Иван S. (ivan)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)
cp_binomial() computes the binomial coefficients needed for bezier stuff
and stores them into an array...
 * Method used: compute logarithms of these
 * extremely large and small numbers, and only go back to the
 * real numbers once they've cancelled out each other, leaving
 * a reasonable-sized one. 

Imagemagik wird wohl ebenfalls etwas ähnliches haben.

Gruß, Iwan

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

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 ;-)

Autor: Johann L. (gjlayde) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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)

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Yahoo-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.