Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Kontrollpunktberechnung bei quadratischen/kubischen Beziers
Gehe zu Seite Zurück  1, 2, 3, 4, 5, 6  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Kontrollpunktberechnung bei quadratischen/kubischen Beziers
 
Autor Nachricht
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 12 Jul 2005 - 23:19:58    Titel:

Zitat:
Was lehrst du denn eigentlich beruflich wenn man fragen darf?


Noch nichts. Ich habe in 3 Monaten meine letzte Diplomprüfung in Informatik/NF Mathe. Ich hoffe auf eine Stelle an der Uni im Bereich intelligente Systeme oder Computeralgebra, da diese meine Spezialisierungs-/Fachrichtungen sind. Ich habe in meinen 6 Studiumsjahren so gut, wie alle Grundlagenvorlesungen in Mathe (LA,Analysis[mittlerweile schon 5 mal],Numerik,Diskrete,Algebra,Zahlentheorie usw.), die es an unserer Uni gibt, betreut (Korrektur/Übungen im Wesentlichen). Daher kann ich mit allem ein wenig was anfangen. Hoffe nicht zu übertreiben mit meiner Lebensgeschichte Smile
sHo
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden

BeitragVerfasst am: 13 Jul 2005 - 01:04:29    Titel:

Na so aktiv und konstruktiv wie du deine - nicht wenige - Kritik hier im Forum preis tust kann ich ruhigen Gewissens sagen : "Junge du hats echt drauf!" ! Smile Ich kenn zwar auch noch einige Mathe-Freaks von der Uni aber du scheinst der freakigste zu sein. Wink

mfg sHo
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 13 Jul 2005 - 14:24:19    Titel:

Einen habe ich.
Zitat:

a_12 = 3u^2(1-u)

ist nicht
Code:

a_12 = ((3 * u)*(3 * u)) * (1-u)

sondern
Code:

a_12 = 3 * u * u * (1-u)

denn ^ bindet stärker als *.
sHo
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden

BeitragVerfasst am: 13 Jul 2005 - 14:27:38    Titel:

Hab den Fehler gefunden. Es lag dran, dass ich für 3u^2 geschrieben habe ((3 * u) * (3*u))
.. was vollkommen falsch ist, mit 3 * (u * u) funktionierts jetz auch super. Smile
Habe aber keine gravierende Veränderung der Auslastung (6-8% CPU).

Hier der Code:
Code:
function getCubicControlPoints(p0:Object, p1:Object, p2:Object, p3:Object, te:Number, tf:Number):Object {
   
   var te3 = 3 * te;
   var tf3 = 3 * tf;
   
   var te_2 = te * te;
   var tf_2 = tf * tf;
   
   var te_3 = te_2 * te;
   var tf_3 = tf_2 * tf;
   
   var te_12 = (1-te) * (1-te);
   var tf_12 = (1-tf) * (1-tf);
   
   var te_13 =  te_12 * (1-te);
   var tf_13 =  tf_12 * (1-tf);
   
   //
   
   var a_1 = te3 * te_12 ;      // a_11 & a_23
   var a_2 = 3 * te_2 * (1-te);   // a_12 & a_24
   var a_3 = tf3 * tf_12 ;      // a_31 & a_43
   var a_4 = 3 * tf_2 * (1-tf);   // a_32 & a_44
   
   var b_1  = p1.x - p0.x * te_13 - p3.x * te_3;
   var b_2  = p1.y - p0.y * te_13 - p3.y * te_3;
   var b_3  = p2.x - p0.x * tf_13 - p3.x * tf_3;
   var b_4  = p2.y - p0.y * tf_13 - p3.y * tf_3;
   
   // Nenner
   var n = a_1 * a_4 - a_3 * a_2;
   
   // Kontrollpunkt 1
   var x_1 = - (a_2 * b_3 - b_1 * a_4) / n; // x_1
   var y_1 = - (a_2 * b_4 - b_2 * a_4) / n; // y_1
   
   // Kontrollpunkt 2
   var x_2 =   (a_1 * b_3 - a_3 * b_1) / n; // x_2
   var y_2 =   (a_1 * b_4 - a_3 * b_2) / n; // y_2
   
   // return
   return { x1: x_1, y1: y_1,
         x2: x_2, y2: y_2 }
}


Hier zum rumspielen: [gelöscht]

mfg sHo

edit: hehe zwei Dumme ein Gedanke! .. naja ein Dummer, war ja mein Fehler Wink


Zuletzt bearbeitet von sHo am 18 Okt 2013 - 12:57:28, insgesamt einmal bearbeitet
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 13 Jul 2005 - 15:25:22    Titel:

Ich habe heute gute Laune, denn ich habe heute gemeinsam mit zwei überdurchschnittlich begabten Kollegen ein Problem geknackt, was ich schon seit einem Jahr mit mir rumtrage (ein terminierendes Konklusionsableitungsystem für Formeln erster Stufe in Presburger-Arithmetik und dann auch allgemein). Die Diplomarbeit eines der Kollegen ist dadurch schön angereichert und ich habe noch einen Grund einen Artikel zu schreiben, denn es scheint neu zu sein Smile Naja.

Ich beschreibe mal einen einfachen Weg zur Lösung des Problems mit der Bisektion.

B(u) sei die vektorwertige Bezier-Funktion mit den Komponenten Bx(u) und By(u).
B'(u) ist die Ableitung von B(u) nach u ebenfalls mit Komponenten B'x(u) und B'y(u).
Dann ist ein ordnungsäquivalenter Ausdruck für die (euklidische) Norm von B'(u):

N(u) = (B'x(u))^2+(B'y(u))^2

Dieser ist ein Polynom 4-en Grades in u, denn B'(u) ist vektorwertig polynomiell vom Grad 2 in u. Weiterhin ist N(u) positiv semidefinit (>= 0).

Gesucht ist eine Abschätzung von sup{N(u) | a <= u <= b}. Das Intervall [a,b] ist zusammenhängend und abgeschlossen. Daher liegen die Maxima von N(u) in [a,b] entweder an den Nullstellen der Ableitung von N(u) oder an den Rändern a oder b. Alles ist explizit bestimmbar, denn der Grad der vorkommenden Polynome ist kleiner gleich 4.

Würde man das so direkt implementieren (also Nullstellen von N'(u) berechnen, einsetzen, und das Maximum nehmen) so wäre es ein Overkill, denn man müsste viele Rechenoperationen durchführen. Da aber N(u) positiv definit ist, ist zur Suche nach dem Maximum jede Abschätzung nach oben erlaubt (wenn sie nicht all zu heftig ist, denn man will ja eine brauchbare haben).

Soweit so gut.

D.h. was noch fehlt ist N(u) abzuschätzen durch etwas geeignetes. Das mache ich in Kürze (heute Abend oder so), wenn ich gesehen habe, wie N(u) bzw. N'(u) aussieht.

Bitte an alle, die das mitverfolgen. Korrektur/Verbesserungsvorschläge sind gefragt und willkommen!
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 13 Jul 2005 - 21:57:03    Titel:

Soweit, so gut.

Code:

>> bx := x0*(1-u)^3+x1*3*u*(1-u)^2+x2*3*u^2*(1-u)+x3*u^3;

           3                3                 2      2
          u  x3 - x0 (u - 1)  + 3 u x1 (u - 1)  - 3 u  x2 (u - 1)
>> by := y0*(1-u)^3+y1*3*u*(1-u)^2+y2*3*u^2*(1-u)+y3*u^3;

           3                3                 2      2
          u  y3 - y0 (u - 1)  + 3 u y1 (u - 1)  - 3 u  y2 (u - 1)
>> bxs := diff(bx,u);

   2         2                  2               2
3 u  x3 - 3 u  x2 - 3 x0 (u - 1)  + 3 x1 (u - 1)  - 6 u x2 (u - 1) +

   3 u x1 (2 u - 2)
>> bys := diff(by,u);

   2         2                  2               2
3 u  y3 - 3 u  y2 - 3 y0 (u - 1)  + 3 y1 (u - 1)  - 6 u y2 (u - 1) +

   3 u y1 (2 u - 2)
>> n := bxs^2+bys^2;

    2         2                  2               2
(3 u  x2 - 3 u  x3 + 3 x0 (u - 1)  - 3 x1 (u - 1)  + 6 u x2 (u - 1) -

                             2         2                  2
   3 u x1 (2 u - 2))^2 + (3 u  y2 - 3 u  y3 + 3 y0 (u - 1)  -

               2
   3 y1 (u - 1)  + 6 u y2 (u - 1) - 3 u y1 (2 u - 2))^2


Zuletzt bearbeitet von algebrafreak am 16 Jul 2005 - 14:31:49, insgesamt einmal bearbeitet
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 13 Jul 2005 - 22:17:01    Titel:

Das gibt

Code:

>> poly(n,[u]);

                                 2                              2   4
poly(((3 x0 - 9 x1 + 9 x2 - 3 x3)  + (3 y0 - 9 y1 + 9 y2 - 3 y3) ) u  +

   (- 2 (6 x0 - 12 x1 + 6 x2) (3 x0 - 9 x1 + 9 x2 - 3 x3) -

                                                         3
   2 (6 y0 - 12 y1 + 6 y2) (3 y0 - 9 y1 + 9 y2 - 3 y3)) u  +

   (2 (3 x0 - 3 x1) (3 x0 - 9 x1 + 9 x2 - 3 x3) +

                                                                      2
   2 (3 y0 - 3 y1) (3 y0 - 9 y1 + 9 y2 - 3 y3) + (6 x0 - 12 x1 + 6 x2)  +

                        2   2
   (6 y0 - 12 y1 + 6 y2) ) u  + (- 2 (3 x0 - 3 x1) (6 x0 - 12 x1 + 6 x2) -

   2 (3 y0 - 3 y1) (6 y0 - 12 y1 + 6 y2)) u +

                 2                2
   ((3 x0 - 3 x1)  + (3 y0 - 3 y1) ), [u])


Die Koeffizienten kann man nun abschätzen. Ich müsste dazu noch was wissen. Sind die x_0,...,x_3 und y_0,...,y3 positiv?


Zuletzt bearbeitet von algebrafreak am 14 Jul 2005 - 01:31:39, insgesamt einmal bearbeitet
sHo
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden

BeitragVerfasst am: 14 Jul 2005 - 00:06:57    Titel:

Wow! Shocked Das muss ich mir erst nochmal vier-, fünfmal durchlesen und dann bestimmt nochmal nachfragen was das sein soll. Wink
Aber zu deiner Frage: Eigentlich sind die normalwerte alle positiv, sowohl auf x, als auch auf y. Es kann aber auch vorkommen,
das ein Punkt in den negativen Bereich verschoben wird. Wenn es der Berechnung zu viel abverlangt oder zu umständlich ist,
kann ich das aber auch schon vorher im Programm Abfangen - ist kein Problem.

mfg sHo
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 14 Jul 2005 - 01:20:43    Titel:

Ich mache das mal in kleinen Schritten, da der Irrtum so weniger wahrscheinlich ist, wenn man Zeit zum Nachdenken hat zwischendurch.

Bemerkenswert ist, dass x0, x2, y0 und y2 stets mit positiven Koeffizienten vorkommen und x1, x3, y1 und y3 stets mit negativen. Doof ist nur, dass bei ungeraden u-Potenzen die Koeffizienten nochmal negiert werden.

D.h. bei den geraden Potenzen von u kann man x0,x2,y0 und y2 durch max{x0,x2,y0,y2} ersetzen. Analog kann man dabei x1,x3,y1 und y3 durch min{x1,x3,y1,y3} ersetzen. Die Berechnung von minima und maxima ist algorithmisch weniger anspruchsvoll, als rechenoperationen mit floats, da im Wesentlichen lexikographischer Vergleich stattfindet, der linear ist. Bei ungeraden Potenzen von u muss man max und min vertauschen.

D.h. so wie es ausschaut, braucht man nur vier Werte zunächsteinmal.

omax = max{x0,x2,y0,y2}
omin = min{x0,x2,y0,y2}
emax = max{x1,x3,y1,y3}
emin = min{x1,x3,y1,y3}

Damit läßt sich das Polynom von oben abschätzen durch

p(x) = a u^4 + b u^3 + c u^2 + d u + e

mit

a = (3 omax - 9 emin + 9 omax - 3 emin)^2 + (3 omax - 9 emin + 9 omax - 3 emin)^2 = 2 (12 omax - 12 emin)^2

b = - 2 [(6 omin - 12 emax + 6 omin)(3 omin - 9 emax + 9 omin - 3 emax) + (6 omin - 12 emax + 6 omin)(3 omin - 9 emax + 9 omin - 3 emax)] = -4 (12 omin - 12 emax)(12 omin - 12 emax) = -4 (12 omin - 12 emax)^2

c = 2(3 omax - 3 emin)(3 omax-9 emin + 9 omax -3 emin) + 2(3 omax - 9 emin + 9 omax - 3 emin) + (6 omax - 12 emin + 6 omax)^2 + (6 omax - 12 emin + 6 omax)^2 = 4 (3 omax - 3 emin)(12 omax - 12 emin) + 2 (12 omax - 12 emin)^2

d = -2 [(3 omin - 3 emax)(6 omin - 12 emax + 6 omin) + (3 omin - 3 emax)(6 omin - 12 emax + 6omin)] = -4 (3 omin - 3 emax)(12 omin - 12 emax)

e = (3 omax - 3 emin)^2 + (3 omax - 3 emin)^2 = 2 (3 omax - 3 emin)^2

Ich bitte alle, die es lesen und helfen wollen, es nachzurechnen. Ich pflege in sowas Fehler zu machen.

Das geht ja so, als ob das eine Übungsaufgabe wäre, die bedacht gestellt worden ist Smile Man führt offenbar alles auf die Differenz omax - emin und omin - emax zurück.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 14 Jul 2005 - 01:27:11    Titel:

Setzt man nun im obigen

v = omax-emin
w = omin-emax

so erhält man

p(x) = a u^4 + b u^3 + c u^2 + d u + e

a = 288 v^2
b = -576 w^2
c = 432 v^2
d = -144 w^2
e = 18 v^2

Was auch mehr oder weniger zu erwarten war. Ich hoffe das ist keine all zu harte Abschätzung.

Morgen (d.h. heute) geht es ein Stück weiter. Vielleicht sieht der eine oder der andere Mist darin Smile
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Kontrollpunktberechnung bei quadratischen/kubischen Beziers
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite Zurück  1, 2, 3, 4, 5, 6  Weiter
Seite 5 von 6

 
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