Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Integrationsproblem
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Integrationsproblem
 
Autor Nachricht
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 17 März 2005 - 14:07:14    Titel: Integrationsproblem

Hallo zusammen,

dieses Problem stammt aus

http://www.uni-protokolle.de/foren/viewt/17503,0.html

Zu bestimmen ist die Länge der Bezier-Curve mit 4 Punkten (p0 = (x0,y0) ... p3 = (x3,y3)) bis zu einem Punkt, gegeben durch einen Parameter u aus [0,1] und die zweidimensionale Funktion

B(u) = p0 (1-u)^3 + 3 p1 u (1-u)^2 + 3 p2 u^2 (1-u) + p3 u^3

Nach z.B. Forster S. 28 Satz 1 ist die Kurve rektifizierbar da stetig differenzierbar und für die Längenbestimmung reicht es

L = int_0^t | B'(u) | du

zu bestimmen. Die erste Ableitung ist in beiden Koordinaten ein Polynom 2 Grades in u. Somit ist die Norm | B'(u) | gegeben durch

|B'(u)| = sqrt((a1 u^2 + b1 u + c1)^2 + (a2 u^2+ b2 u + c2)^2)

und ist somit von der Form

sqrt(a u^4 + b u^3 + c u^2 + d u + e)

Frage: Wer kann diesen Integral berechnen? oder Wer hat Ideen zu Bestimmung davon?
DMoshage
Gast






BeitragVerfasst am: 17 März 2005 - 15:31:24    Titel:

Hallo algebrafreak,

eine Lösung habe ich auch nicht aber hier ist ein PDF über die Bestimmung der Länge einer Bezierkurve.

http://www.tinaja.com/glib/bezlenjf.pdf
http://www.tinaja.com/third01.asp

Ansonsten würde ich es wahrscheinlich mit einer numerischen Integration (z.B. Romberg Integration ) versuchen.

Gruß
Dirk
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 17 März 2005 - 15:52:21    Titel:

Danke für den Hinweis.

Ich frage mich, wie nahe man an sqrt(p) für p Polynom vom Grad 4 mit einer Orthogonalbasisapproximation mit Polynomen vom Grad 3 oder 2 rankommt. Die Polynome sind ja immer positiv definit. So nach dem Motto

sqrt sum_i=0^n a_i x^i = sum_i=0^n sqrt(a_i) x^(i/2)

wobei das natürlich total falsch ist, aber das Gefühl für eine Näherung geben sollte.

Ich folge da dem Bedarf an einem schnellen Verfahren (am besten O(1)), wenn man schon nähern muss.
DMoshage
Gast






BeitragVerfasst am: 17 März 2005 - 18:43:59    Titel:

Hallo algebrafreak,

mir fiel grad noch was ein.
Du kannst die Wurzel natürlich auch als Reihenwicklung ausdrücken. Das gibt zwar am Anfang eine etwas aufwendige Rechnerei bis die Terme alle ausmultipliziert sind. Dafür können die daraus entstehenden Terme trivial integriert werden. Ist nur eine Frage der Anzahl der Entwicklungsglieder für die Genaugkeit der Berechnung.

Gruß
Dirk
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 17 März 2005 - 18:59:41    Titel:

Jo, danke. Das hört sich ja interessant und vielversprechend an. Probiere ich gleich mal aus.

Ich habe nur Angst, daß eine Reihenentwicklung eben die typischen Eigenschaften mitbringt, etwa die Lokalität. Als Entwicklungspunkt würde man vermutlich den Erwartungswert der Auswahl von t nehmen. Bei Gleichverteilung die Mitte. Da schaut es dann an den Rändern schlecht aus.

Nichts desto trotz probiere ich das mal aus.
DMoshage
Gast






BeitragVerfasst am: 20 März 2005 - 12:08:21    Titel:

Hallo algebrafreak,

ich glaube, das die Idee mit der Reihenentwicklung der Wurzel nicht funktioniert. Die Reihenentwicklung hat nur einen Konvergenzbereich von 1. Der Wert in der Wurzel ist aber abhängig von den Koordinaten des Bezierpolynoms und kann daher beliebig groß sein.

Im folgendem Dokument
http://www.uni-weimar.de/~bauinf/Publikationen/SA/SABock.pdf
wird auch auf die numerische Integration verwiesen. Ich habe dies mal mit der Rombergintegration probiert. Bei einem Bezierpolynom mit einer Länge von ca. 150 und einem Schwellwert von 1e-4 bricht die Iteration schon nach 5 Schritten ab. Die Triviallösung, das Polynom in ein Kantenpolygon umzuwandeln und die Teilstrecken aufzusummieren, bringt die Genauigkeit erst bei ca. 500 Teilstücken.

Gruß
Dirk
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 März 2005 - 14:25:31    Titel:

Zitat:
Die Reihenentwicklung hat nur einen Konvergenzbereich von 1 Reihenentwicklung hat nur einen Konvergenzbereich von 1.


Das Kontraargument verstehe ich nicht ganz. Man entwickelt doch

p(x) ~= sum_{i=0}^infty a_i (x-a)^i

um den Punkt a. Für Kvg. Radius 1 ist |x-a| < 1 stets für a und x in [0,1] erfüllt. Speziell für a = 0.5 liegen alle Werte im Kvz. Radius. Irrw ich mich da?

Zitat:
Schwellwert von 1e-4


Ich glaube eine solche Genauigkeit bzgl. t ist nicht gefordert. Ich sehe allerdings noch ein fettes Problem dabei, denn die Position eines Punktes auf der Kurve hat vom Wert von t, die Andreas Weber im Posting oben angemerkt hat, keine lineare Abhängigkeit. Es könnte sein, daß 1e-4 für manche Kurvenabschnitte ein Overkill ist und für andere gerade ein 10 Pixel-Schritt.

Zitat:
bricht die Iteration schon nach 5 Schritten ab


Ich checke mal das "Gewicht" einer Romberg-Iteration. Was ich mir überlegt habe, und hoffentlich noch irgendwan mal fertig wird, hätte eine Komplexität von O(1). Ich würde mit einer Orthogonalbasis von Polynomen bzgl. eines festen Skalarproduktes einen VR-Einbettung in einen Polynomenunterraum bauen, die einer Auswertung einer Funktion die Koordinaten eines bzgl. des Skalarproduktes optimalen Approximationspolynoms zuordnet. Das ist im Wesentlichen eine 4x4 Matrix an die die Punkte ranmultipliziert werden. Und das Ergebnis müsste man nur noch trivial integrieren.

Ich bin aber zurzeit total ausgelastet mit meiner Diplomarbeit, sodaß ich frühestens am Dienstag wieder was hier mache.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Integrationsproblem
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum