Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Umformen einer monströsen Gleichung
Gehe zu Seite Zurück  1, 2, 3, 4  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Umformen einer monströsen Gleichung
 
Autor Nachricht
Andreas Weber
Gast






BeitragVerfasst am: 11 März 2005 - 11:50:07    Titel:

Einfach ist immer gut - aber das ist jetzt des Guten wohl etwas zuviel...

In der ursprünglichen Gleichung habe ich neben t noch 8 weitere Variablen drin (p1x, p2x etc., das sind Variablennamen, nicht etwa das Produkt oder so, während * für das Multiplikationszeichen steht).

Ich fürchte diese 8 Gesellen müssten in der richtigen Lösung immer noch irgendwo sein - vorzugsweise auf der rechten Seite, und t auf der linken...

Danke für Deine Zeit!

Andreas Weber
Andreas Weber
Gast






BeitragVerfasst am: 12 März 2005 - 15:06:51    Titel:

Zitat:
Wenn das nicht Zufriedenheit bietet schreibe ich heute nachmittags
Code in C++.


... für den Fall, das bei meiner Antwort nicht klar genug geworden ist:
ja, das wär natürlich super nett!

Very Happy

Andreas Weber
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 12 März 2005 - 22:55:55    Titel:

Ich bin heute ein wenig beschäftigt. Setze mich morgen an den Code.
Gast







BeitragVerfasst am: 13 März 2005 - 17:10:11    Titel:

So. Der Mist ist fertig. Der Code ist für 3-er gcc. Der Code compiliert und liefert für Werte von 0 <= u <= 1, wie man aus dem Bsp. sieht richtige Ergebnisse. Ich habe den Parameterwert zwischen 0 und 1 angesiedelt und nicht, wie oben, zwischen 0 und 100. Es sollte kein Problem sein das zu verändern.

Code:

// Der Code ist ein Prototyp und sollte auf keinen Fall so wie er ist,
// schon allein wegen der Rechte und GPL (erstellt in GPL Emacs) in
// komerzieller Software verwendet werden. Als weiteren Grund ist
// zu nennen, daß hier keinerlei Gedanken bzgl. der Numerischen
// Stabilität verschwendet wurden, was auch als Grund dienen kann :)

#include <vector>
#include <iostream>
#include <cmath>

class v2D {

  // Zweidimensionale vektoren

public:
 
  // Es ist dämlich auf koordinaten über accessor methoden zuzugreifen
  double x,y;

  v2D::v2D(double nx,double ny) {
    x = nx;
    y = ny;
  };

};

// Gibt eine liste der reellen Nullstellen eines kubischen Polynoms zurück,
// falls nicht (alle Koeffizienten 0) gilt. Sonst liefert der Algorithmus
// leere Liste mit der Semantik R.
std::vector<double> solve(double a,double b,double c,double d) {

  std::vector<double> r;

  // Triviale Fälle
 
  // Das Nullpolynom
  if (a == 0 && b == 0 && c == 0 && d == 0) return r;
  // Lineares Polynom c x + d
  if (a == 0 && b == 0 && c != 0) {
    r.push_back(-d/c);
    return r;
  }
  // Quadratisches Polynom
  if (a == 0 && b == 0) {
    double diskr = c*c-4.0*b*d;
    // Keine Nullstellen
    if (diskr < 0) return r;
    // Eine Nullstelle
    if (diskr == 0) {
      r.push_back(-c/(2.0*b));
      return r;
    };
    // Zwei Nullstellen
    r.push_back((-c + sqrt(diskr))/(2.0*b));
    r.push_back((-c - sqrt(diskr))/(2.0*b));
    return r;   
  }

  // Cardansche Formeln
  double p = (3.0*a*c - b*b)/(3.0*a*a);
  double q = (2.0*b*b*b-9.0*a*b*c+27.0*a*a*d)/(27.0*a*a*a);

  // Gelöst wird nun y^3 + py + q = 0

  double diskr = q*q/4.0+p*p*p/27.0;

  if (diskr > 0) {
    // Eine reelle Lösung
    double x = pow(-q/2.0+sqrt(diskr),1.0/3.0)+
      pow(-q/2.0-sqrt(diskr),1/3.0)-b/(3.0*a);
    r.push_back(x);
    return r;
  }

  // Sehr bedenklich
  if (diskr == 0) {
    // Zwei reelle Lösungen
    double x1 = pow(q/2.0,1.0/3.0)-b/(3.0*a);
    double x2 = -pow(4.0*q,1.0/3.0)-b/(3.0*a);
    r.push_back(x1);
    r.push_back(x2);
    return r;
  }

  // 3 reelle Lösungen

  double pi = 3.1415927;
 
  double x1 = 2.0*sqrt(-p/3.0)*cos(1.0/3.0*acos(-q/2.0*sqrt(-27.0/(p*p*p))))
    - b/(3.0*a);
  double x2 = -2.0*sqrt(-p/3.0)*cos(1.0/3.0*acos(-q/2.0*sqrt(-27.0/(p*p*p)))+
              pi/3.0) - b/(3*a);
  double x3 = -2.0*sqrt(-p/3.0)*cos(1.0/3.0*acos(-q/2.0*sqrt(-27.0/(p*p*p)))-
              pi/3.0) - b/(3.0*a);
  r.push_back(x1);
  r.push_back(x2);
  r.push_back(x3);
  return r;
}

// B(u) = p0 * (1-u)^3 + 3 * p1 * u * (1-u)^2 + 3 * p2 u^2 * (1-u) + p3 * u^3
v2D bezier(double u,v2D& p0,v2D& p1,v2D& p2, v2D& p3) {

  double v = 1-u;

  double x = p0.x*v*v*v+p1.x*3*u*v*v+p2.x*3*u*u*v+p3.x*u*u*u;
  double y = p0.y*v*v*v+p1.y*3*u*v*v+p2.y*3*u*u*v+p3.y*u*u*u;

  return(v2D(x,y));
}

double reizeb(v2D& p,v2D& p0,v2D& p1,v2D& p2, v2D& p3) {
 
  // Berechnen von koeffizienten
  double ax = p3.x-3.0*p2.x+3.0*p1.x-p0.x;
  double bx = 3.0*p2.x-6.0*p1.x+3.0*p0.x;
  double cx = 3.0*p1.x-3.0*p0.x;
  double dx = p0.x - p.x;

  double ay = p3.y-3.0*p2.y+3*p1.y-p0.y;
  double by = 3.0*p2.y-6.0*p1.y+3.0*p0.y;
  double cy = 3.0*p1.y-3.0*p0.y;
  double dy = p0.y - p.y;

  std::vector<double> xl = solve(ax,bx,cx,dx);
  std::vector<double> yl = solve(ay,by,cy,dy);
 
  // Intersection bilden. Die Funktion sollte injektiv sein :)
  // Sollte man auch degenerierte Fälle betrachten wollen, so ist
  // hier noch zu unterscheiden, wenn eine der Listen oder beide
  // leer sind.
  for (int i = 0; i < xl.size(); i++)
    for (int j = 0; j < yl.size(); j++)
      if (abs(xl[i] - yl[j]) < 0.01)
   return xl[i];   

  return(-1);
}


int main() {

  v2D p0(1,2);
  v2D p1(2,3); 
  v2D p2(3,0);
  v2D p3(4,-1);

  double t = 0;

  while (t <= 1) {

    v2D v = bezier(t,p0,p1,p2,p3);
    double r = reizeb(v,p0,p1,p2,p3);

    std::cout << "Testwert : " << t << " Antwort : " << r << std::endl;

    if (abs(r - t) > 0.01)
      std::cout << "Fuck " << r << std::endl;
   
    t = t + 0.00001;
   
  }

}



P.S. Der Code sollte vor allem Ideen geben, wie sowas gemacht werden sollte. ER IST AUF KEINEN FALL SO IN EIN PROGRAMM ZU ÜBERNEHMEN, denn da gibt es so viel daran auszusetzen, dass ich gar nicht darüber reden möchte. Würde man alles richtig machen, wäre der Code 10 mal länger und 10^3 mal unverständlicher.
Andreas Weber
Gast






BeitragVerfasst am: 13 März 2005 - 21:39:17    Titel:

Hallo algebrafreak

Du hast Dich da ja mächtig ins Zeug gestürzt - herzlichen Dank!

Ich hab bei Deinen C++ Code ein paar kleine syntaktische Unterschiede zu ActionScript eliminiert, damit ich ihn in Flash kompilieren konnte - funktioniert soweit gut, nur - du ahnst es schon - es gibt ein aber...

Ich verstehe nicht genau (Euphemismus...) was Du in den Funktionen 'reizeb' und 'solve' machst, aber wenn ich dann sehe, wie Du in main loopst und t ganz allmählich t von 0 auf 1 inkrementierst gemahnt mich das schon sehr daran, wie wir den Wert von t bereits jetzt, mit Hilfe der schon geposteteten Funktion finden:

Code:
// die hatten wir schon...
function getPointsOnCubicCurve(targ:Number, p1:Object, p2:Object, p3:Object, p4:Object):Object {
      var a:Number,b:Number,c:Number;
      var v:Number = targ / 100;
      a = 1 - v;
      b = a * a * a;
      c = v * v * v;
      var p:Object = {};
      p.x = b * p1.x + 3 * v * a * a * p2.x + 3 * v * v * a * p3.x + c * p4.x;
      p.y = b * p1.y + 3 * v * a * a * p2.y + 3 * v * v * a * p3.y + c * p4.y;
      return p;
   }

// 4 Punkt-Objekte die die kubische Bezier Kurve definieren
// Im folgenden alles 'quick and dirty' programmiert:
// - der Kürze halber initialisieren wir die Objekte direkt,
// nicht als Instanzen von Klassen
// - wir verzichten auf das 'typen' der Objekte/Variablen
p1 = {x:100, y:100};
p2 = {x:200, y:0};
p3 = {x:250, y:20};
p4 = {x:400, y:150};

// der fragliche Punkt:
// liegt auf der Kurve
// wir wollen wissen wo, an welchem Punkt des prozentualen Verlaufs
p5 ={x:297, y:69};


// wenn wir jetzt einen Punkt P5 haben von dem wir wissen dass er auf der Kurve liegt,
// und wissen wollen, an welchem prozentualen Verlauf der Kurve
// können wir die Kurve mit der Funktion 'getPointsOnCubicCurve' (die wir von Anfang an hatten)
// in kleinen Intervallen abtasten: indem wir (in einem Loop) den Parameter 'targ' - den prozentualen
// Ort auf der Kurve - verändern erhalten wir eine Menge Punkte auf der Kurve zurück, von denen
// wir den prozentualen Ort kennen - wenn einer dieser Punkte -nennen wir ihn PX - nahe genug bei P5, ist unsere Frage
// beantwortet: P5 liegt auf dem (annähernd...) gleichen prozentualen Verlauf wie PX.

targ = getTargOfClosestPointOnCubicCurve(p5, p1, p2, p3, p4, 0.1);

trace(targ);// gibt in diesem Fall 73 zürück

function getTargOfClosestPointOnCubicCurve(searchPoint, p1, p2, p3, p4, precision){
   var refPoint;
   var i = 100;
   var deltaX, deltaY;
   var closestDist = Number.POSITIVE_INFINITY;
   for(var i=0, len = 100*(1/precision); i<=len; i++){
      refPoint = getPointsOnCubicCurve(i*precision, p1, p2, p3, p4);
      deltaX = searchPoint.x-refPoint.x;
      deltaY = searchPoint.y-refPoint.y;
      curDist = Math.sqrt(deltaX*deltaX + deltaY*deltaY);
      if(curDist < closestDist){
         closest = i*precision;
         closestDist = curDist;
      }
   }
   return closest;
}


Habe ich Deinen Code völlig missverstanden - leistet er etwas anderes? Schneller?

Und diese Lösung hat ja zwei gewichtige Schönheitsfehler:
- das iterative Suchen des nächsten Punktes ist langsam
- wir finden nur einen approximativen Wert, nicht den exakten

Deshalb auch meine ursprüngliche Frage: können wir t (oder targ oder wie immer wir den prozentualen Verlauf nennen wollen) 'mathematisch' und direkt, ohne iterative Approximation, bestimmen, ebenso wie wir die x und y Koordinaten in der Funktion getPointsOnCubicCurve bestimmen.

Es ist wahrscheinlich nur Ausdruck meiner mathematischen Ahnungslosigkeit, dass ich glaubte, es sollte möglich sein, die Gleichung die in getPointsOnCubicCurve steckt, so umzuformen, dass wir t direkt errechnen können, da wir ja - wenn wir 5 Punkte kennen - nur eine Unbekannte, eben t, haben.

Uebrigens: eine solche Funktion/Gleichung wäre für Flash (aber wahrscheinlich auch andere Applikationen) ausserordentlich hilfreich und es würde vieles möglich was jetzt nicht realisiert werden kann, weil die iterative Lösung zu langsam ist.

Immer noch ratlos aber ehrlich sehr dankbar

Andreas Weber
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 13 März 2005 - 21:52:41    Titel:

Ich überbringe ungerne schlechte Nachrichten. Ich muß leider sagen, daß deine Sorgen völlig berechtigt sind. Ich fasse alle Irtümmer kurz zusammen:

- Ich gebe durch obiges Programm eine bis auf die Berechnung der Werte algebraische Lösung

- Ich benutze kein iteratives Verfahren, sondern die cardanischen Formeln

- Es gibt eine explizite Umformung, die für das angegebene Problem (Bestimmung von u aus Punkten bei 4 Kontrollpunkten) aus den Punkten einen Wert von t liefert

- Der Weg oben von Dir ist weder aus algorithmischer noch aus mathematischer Sicht vertretbar Sad (nicht böse sein, meine lösung ist zumindest aus estetischer sicht nicht vertretbar)

- Für n > 4 geht es nur approximativ, aber mit völlig anderen Mitteln.

Die Methode solve löst allgemein eine kubische univariate Polynomgleichung

ax^2+bx^2+cx+d = 0

direkt, ohne Approximation mit den Cardanischen Formeln.

Die Methode reizeb stellt die Umformung der Gleichungen dar so, daß aus diesen zur Laufzeit ein Polynom dritten grades rauskommt, bestimmt seine Nullstellen und sucht eine gemeinsame raus. Unter gegebenen Voraussetzungen gibt es genau eine solche Stelle und sie ist genau der Wert von u.

Die main() methode testet für eine zufällige Wahl von Punkten, ob meine Methode korrekt arbeitet. Sollte nur eine Angabe zur Benutzung sein.

Ich biete Dir zwei Möglichkeiten zur Verfügung:

- Ich kommentiere den Code besser
- Ich schreibe die Umformungen hin

Es geht natürlich auch beides.
Gast







BeitragVerfasst am: 13 März 2005 - 22:16:30    Titel:

Zitat:
Ich überbringe ungerne schlechte Nachrichten.


Im Grundtenor stimmen mich Deine 'schlechten Nachrichten' überaus hoffnungsvoll...

Zitat:
Ich biete Dir zwei Möglichkeiten zur Verfügung:

- Ich kommentiere den Code besser
- Ich schreibe die Umformungen hin


Ich wähle fürs erste die 3. - die dir wahrscheinlich am wenigsten Arbeit macht:

Wie finde ich t für diesen Punkt:

p5 = {x:160.3372, 51.31752}

die Kurve ist definiert durch:

p1 = {x:100, y:100};// Anker - Startpunkt
p2 = {x:200, y:0};// Kontrollpunkt, nicht auf Kurve
p3 = {x:250, y:20};// Kontrollpunkt, nicht auf Kurve
p4 = {x:400, y:150};// Anker - Endpunkt

Wenn Du mir einfach anhand dieses Beispiels aufzeigen könntest, wie Du die Funktionen mit diesen Parametern aufrufst!

Danke!

Ein freudiger gespannter

Andreas Weber
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 14 März 2005 - 00:51:49    Titel:

Das Beispiel hat einen sehr hässlichen, aber nicht unberechtigten, Fehler im Code aufgedeckt. Ich arbeite letzter Zeit viel mit algebraischen Sprachen, die alles exakt berechnen und habe nicht aufgepasst, daß pow nicht wissen kann, daß ich die 3-te Wurzel berechne. Das muss man ihr doch beibringen Smile

Der folgende Code ist nun korrekt und gibt 0.22 zurück.

Code:


// Der Code ist ein Prototyp und sollte auf keinen Fall so wie er ist,
// schon allein wegen der Rechte und GPL (erstellt in GPL Emacs) in
// komerzieller Software verwendet werden. Als weiteren Grund ist
// zu nennen, daß hier keinerlei Gedanken bzgl. der Numerischen
// Stabilität verschwendet wurden, was auch als Grund dienen kann :)

#include <vector>
#include <iostream>
#include <cmath>

class v2D {

  // Zweidimensionale vektoren

public:
 
  // Es ist dämlich auf koordinaten über accessor methoden zuzugreifen
  double x,y;

  v2D::v2D(double nx,double ny) {
    x = nx;
    y = ny;
  };

};

// Kubikwurzel
double crt(double x) {

    // Achsensymmetrie verwenden
    if (x < 0) return -pow(-x,1.0/3.0);
    return pow(x,1.0/3.0);

}

// Gibt eine liste der reellen Nullstellen eines kubischen Polynoms zurück,
// falls nicht (alle Koeffizienten 0) gilt. Sonst liefert der Algorithmus
// leere Liste mit der Semantik R.
std::vector<double> solve(double a,double b,double c,double d) {

  std::vector<double> r;

  // Triviale Fälle
 
  // Das Nullpolynom
  if (a == 0 && b == 0 && c == 0 && d == 0) return r;
  // Lineares Polynom c x + d
  if (a == 0 && b == 0 && c != 0) {
    r.push_back(-d/c);
    return r;
  }
  // Quadratisches Polynom
  if (a == 0 && b == 0) {
    double diskr = c*c-4.0*b*d;
    // Keine Nullstellen
    if (diskr < 0) return r;
    // Eine Nullstelle
    if (diskr == 0) {
      r.push_back(-c/(2.0*b));
      return r;
    };
    // Zwei Nullstellen
    r.push_back((-c + sqrt(diskr))/(2.0*b));
    r.push_back((-c - sqrt(diskr))/(2.0*b));
    return r;   
  }

  // Cardansche Formeln
  double p = (3.0*a*c - b*b)/(3.0*a*a);
  double q = (2.0*b*b*b-9.0*a*b*c+27.0*a*a*d)/(27.0*a*a*a);

  // Gelöst wird nun y^3 + py + q = 0

  double diskr = q*q/4.0+p*p*p/27.0;

  if (diskr > 0) {
    // Eine reelle Lösung
      double x = crt(-q/2.0+sqrt(diskr))+
     crt(-q/2.0-sqrt(diskr))-b/(3.0*a);
      r.push_back(x);
    return r;
  }

  // Sehr bedenklich
  if (diskr == 0) {
    // Zwei reelle Lösungen
    double x1 = crt(q/2.0)-b/(3.0*a);
    double x2 = -crt(4.0*q)-b/(3.0*a);
    r.push_back(x1);
    r.push_back(x2);
    return r;
  }

  // 3 reelle Lösungen

  double pi = 3.1415927;
 
  double x1 = 2.0*sqrt(-p/3.0)*cos(1.0/3.0*acos(-q/2.0*sqrt(-27.0/(p*p*p))))
    - b/(3.0*a);
  double x2 = -2.0*sqrt(-p/3.0)*cos(1.0/3.0*acos(-q/2.0*sqrt(-27.0/(p*p*p)))+
              pi/3.0) - b/(3*a);
  double x3 = -2.0*sqrt(-p/3.0)*cos(1.0/3.0*acos(-q/2.0*sqrt(-27.0/(p*p*p)))-
              pi/3.0) - b/(3.0*a);
  r.push_back(x1);
  r.push_back(x2);
  r.push_back(x3);
  return r;
}

// B(u) = p0 * (1-u)^3 + 3 * p1 * u * (1-u)^2 + 3 * p2 u^2 * (1-u) + p3 * u^3
v2D bezier(double u,v2D& p0,v2D& p1,v2D& p2, v2D& p3) {

  double v = 1-u;

  double x = p0.x*v*v*v+p1.x*3*u*v*v+p2.x*3*u*u*v+p3.x*u*u*u;
  double y = p0.y*v*v*v+p1.y*3*u*v*v+p2.y*3*u*u*v+p3.y*u*u*u;

  return(v2D(x,y));
}

double reizeb(v2D& p,v2D& p0,v2D& p1,v2D& p2, v2D& p3) {
 
  // Berechnen von koeffizienten
  double ax = p3.x-3.0*p2.x+3.0*p1.x-p0.x;
  double bx = 3.0*p2.x-6.0*p1.x+3.0*p0.x;
  double cx = 3.0*p1.x-3.0*p0.x;
  double dx = p0.x - p.x;

  double ay = p3.y-3.0*p2.y+3*p1.y-p0.y;
  double by = 3.0*p2.y-6.0*p1.y+3.0*p0.y;
  double cy = 3.0*p1.y-3.0*p0.y;
  double dy = p0.y - p.y;

  std::vector<double> xl = solve(ax,bx,cx,dx);
  std::vector<double> yl = solve(ay,by,cy,dy);
 
  // Intersection bilden. Die Funktion sollte injektiv sein :)
  // Sollte man auch degenerierte Fälle betrachten wollen, so ist
  // hier noch zu unterscheiden, wenn eine der Listen oder beide
  // leer sind.
  for (int i = 0; i < xl.size(); i++)
    for (int j = 0; j < yl.size(); j++)
      if (abs(xl[i] - yl[j]) < 0.01)
   return xl[i];   

  return(-1);
}


int main() {

  v2D p0(100.0,100.0);
  v2D p1(200.0,0.0); 
  v2D p2(250.0,20.0);
  v2D p3(400.0,150.0);

  v2D p(160.3372, 51.31752);

  double r = reizeb(p,p0,p1,p2,p3);
 
  std::cout << r << std::endl;

}



P.S. Die solve Methode arbeitet nach

http://www.formel-sammlung.de/ld-Cardanische-Formeln-312.html

Für die reizeb Methode habe ich folgendes gemacht (hier nur für 1 Dimension):

x0*(1-u)^3 + x1*3*u*(1-u)^2 + x2*3*u^2*(1-u) + x3*u^3 - x = 0

Ausmultiplizieren ergibt:

u^3 * (x3-3*x2+3*x1-x0) +
u^2 * (3*x2-6*x1+3*x0) +
u * (3*x1-3*x0) +
x0 - x;

Vergeiche. In klammern sind genau die Koeffizienten einer kubischen Gleichung.
Andreas Weber
Gast






BeitragVerfasst am: 14 März 2005 - 09:02:49    Titel:

Lieber algebrafreak:

Very Happy Very Happy Very Happy Das ist absolut brilliant! Very Happy Very Happy Very Happy

Ich möchte mit dem Code noch etwas spielen, bevor ich dann noch ein paar Fragen habe.

Vielen, vielen Dank!

Andreas Weber
Andreas Weber
Gast






BeitragVerfasst am: 15 März 2005 - 22:00:00    Titel:

Hallo algebrafreak!

Hier die Funktion(en) nun im Einsatz:

http://tinyurl.com/5hy4w

Die kubische Kurve kann jetzt über 6 Punkte kotrolliert werden (einfach Punkte ziehen)

Deine Funktion - ich nenne sie jetzt getTOfPointOnCubicCurve - dient zum Feststellen von t (dem 'prozentualen Ort') der grünen Punkte auf der Kurve - wenn wir t nicht kennen, können diese Punkte nicht mehr auf der Kurve positioniert werden sobald sie über einen der beiden Kontollpunkte modifiziert wird.
In der Praxis hat die Flash Community eine ganze Menge Verwendungsmöglichkeiten dafür, z.B. um Objekte auf nicht-planen Oberflächen darzustellen - einen Surfer auf einer Welle (Surfer == grüner Punkt, Welle == Kurve die über die Kontrollpunkte programmatisch animiert wird).

Eine Bemerkung am Rande: Flash kann keine kubischen Kurven rendern - die Kurve wird durch einen Spline aus mehreren quadratischen Kurven emuliert (mathematisch und algebraisch sicherlich völlig unhaltbar Wink)


Code:
   /*Adapted from algebrafreak by Andreas Weber*/
   
   // Parameters: 5 objects with x and y properties
   // - p0 the search point, must be on the curve
   // - p1 the first anchor
   // - p2 and p3 are points _on_ the curve, _not_ the control points
   // - p4 the second anchor
   
   
   // Returns t for p0, the search point. t ranges from 0 to 1:
   // At the start of the curve close to 0, close to 1 at the end of the curve
   // -1 if t was not found

   // Caution:
   //        1.   does not return t for every cubic curve.
   //         If the x or y values of the defining points (p1, p2, p3, p4)
   //         are on one line, t cannot be calculated.
   //         In these cases -1 is returned
   //       2. Does only return the expected coordinates when the points p1, p2, p3, p4 are evenly spaced 
   //          if p2 and p3 are, e.g., close to p1, and p0 is about the midpoint of the curve
   //         the returned t will not be 0.5 but quite a bit lower
   //         (each point has some kind of 'attraction')
   
   public function getTOfPointOnCubicCurve(p0:Object, p1:Object, p2:Object, p3:Object, p4:Object){
      var ax, bx, cx, dx, ay, by, cy, dy, xl, yl, i, j, jj;
   
      ax = p4.x-3*p3.x+3*p2.x-p1.x;
      bx = 3*p3.x-6*p2.x+3*p1.x;
      cx = 3*p2.x-3*p1.x;
      dx = p1.x - p0.x;
      
      ay = p4.y-3*p3.y+3*p2.y-p1.y;
      by = 3*p3.y-6*p2.y+3*p1.y;
      cy = 3*p2.y-3*p1.y;
      dy = p1.y - p0.y;


      xl = solveCubic(ax,bx,cx,dx);
      yl = solveCubic(ay,by,cy,dy);

      for (var i=0, len1=xl.length; i<len1 ; i++){
         for (var j=0, len2=yl.length; j<len2 ; j++){
            if (Math.abs(xl[i] - yl[j]) < 0.01){
               return xl[i]; 
            }
         }
      }
      return(-1);
   }
   
   /*Adapted from algebrafreak by Andreas Weber*/
   private function solveCubic(a, b, c, d) {
      var p, q, diskr, pi;
      var p, q, diskr;
      
      if(a == 0 && b == 0 && c == 0 && d == 0){
         return [];
      }else if(a == 0 && b == 0 && c != 0) {
         return [-d/c];
      }else if(a == 0 && b == 0) {
         diskr = c*c-4*b*d;
         if (diskr < 0){
            return [];
         }else if(diskr == 0) {
            return [-c/(2*b)];
         }else{
            return [(-c + Math.sqrt(diskr))/(2*b), (-c - Math.sqrt(diskr))/(2*b)];
         }
      }
   
      p = (3*a*c - b*b)/(3*a*a);
      q = (2*b*b*b-9*a*b*c+27*a*a*d)/(27*a*a*a);
      
      diskr = q*q/4+p*p*p/27;

      if(diskr > 0){
         return [crt(-q/2+Math.sqrt(diskr))+crt(-q/2-Math.sqrt(diskr))-b/(3*a)];
      }else if(diskr == 0) {
         return [crt(q/2)-b/(3*a), -crt(4*q)-b/(3*a)];
      }else{
         pi = Math.PI;
         return [2*Math.sqrt(-p/3)*Math.cos(1/3*Math.acos(-q/2*Math.sqrt(-27/(p*p*p))))- b/(3*a),
               -2*Math.sqrt(-p/3)*Math.cos(1/3*Math.acos(-q/2*Math.sqrt(-27/(p*p*p)))+ pi/3) - b/(3*a),   
               -2*Math.sqrt(-p/3)*Math.cos(1/3*Math.acos(-q/2*Math.sqrt(-27/(p*p*p)))- pi/3) - b/(3*a)
               ];
      }
   }
   
   // cubic root
   public function crt(x:Number):Number{
      return x<0 ? -Math.pow(-x,1/3) : Math.pow(x,1/3);
   }


Ich würde diesen Port ins ActionScript gerne in dieser Form der 'Flash Community' zur Verfügung stellen (natürlich unentgeltlich) - ist das ok für Dich?
Und statt des Pseudonyms würd ich dort eigentlich gerne Deinen Namen einsetzen - mein mail ist webweber [at] motiondraw [dot] com


Wie die ursprünglich von mir gepostete Funktion zum Ermitteln eines Punktes auf t der Kurve, hat auch Deine Version die Eigenschaft, dass t nicht (direkt) mit der Länge der Kurve korreliert - oder nur im Spezialfall dass p2 auf t 33.333 und p3 auf 66.666 liegen. In allen anderen Fällen ist t 'verzerrt' - p2 und p3 scheinen einen mysteriösen 'Magnetismus' auszuüben.

Beispiel:
Alle Kontrollpunke auf einer 100 Pixel langen, (fast, um einen 'trivialen Fall' zu vermeiden) geraden Linie, p2 jedoch nahe bei p1 und p3 nahe bei p4.
Naiverweise würden wir erwarten, dass ein Punkt der 30 Pixel vom Startpunkt liegt t == 0.3 zurückgeben sollte. Tatsächlich ergibt sich folgenden Bild, für die Punkte mit x 0, 10, 20, 30 etc.:

0 - 0
10 - 0.0496
20 - 0.1328
30 - 0.2412
40 - 0.3664
50 - 0.5
60 - 0.6336
70 - 0.7588
80 - 0.8672
90 - 0.9504
100 - 1

Die Abstände werden an den Enden immer kürzer - wir erhalten kein lineares, sondern irgenwie 'kurviges' Ergebnis, eben, dieser mysteriöse 'Magnetismus'.

Frage: lassen sich diese Werte 'irgendwie' - (Einbezug der relativen Position von P2 und P3) so umrechnen, dass t mit der Länge der Kurve korreliert? (Im Ergebnis: t ist 0, 0.1, 0.2 etc.)

Wenn das möglich wäre liesse sich für manche (alle?) 'triviale Fälle' die jetzt -1 zurückgeben, ein effektiver Wert zurückgeben - z.B. obiges Beispiel:
wenn alle Punkte auf einer geraden, 100 pixel langen Linie liegen ist t für den Punkt der 30 pixel rechts von p1 liegt 0.3.

Wenn... dann liesse sich sicher auch die Länge einer quadratischen oder kubischen Bezier Kurve eleganter bestimmen als mit der iterativen/approximativen (und langsamen) Methode die wir jetzt benutzen: Addition der Abstände zwischen einer möglichst grossen Zahl von aufeinanderfolgenden Punkten auf der Kurve.

Noch einmal vielen Dank für die Zeit, die Du Dir für dieses Problem genommen hast - das war ja fast wie im Märchen.

Apropos Märchen -
Wenn ich noch einen Wunsch frei hätte (rein hypothetisch nätürlich...) die gleiche Funktion für quadratische Bezier Kurven (und es wäre natürlich versprochen, dass ich dann nicht noch mit den quintischen und so weiter nachkomme...). Die abzuleitende Funktion wäre (nur so für den hypothetischen Fall, natürlich...)

Code:
public function getPointsOnQuadCurve(targ:Number, p1:Object, p2:Object, p3:Object):Object {
      var a:Number,b:Number,c:Number;   
      var v:Number = targ / 100;   
      c = v * v;
      a = 1 - v;
      b = a * a;
      var p:Object = {};
      p.x = p1.x * b + 2 * p2.x * a * v + p3.x * c;
      p.y = p1.y * b + 2 * p2.y * a * v + p3.y * c;   
      return p;   
   }


Und wenn Du findest, dass das nun wirklich reicht: volles Verständnis.

Danke!

Andreas Weber Very Happy
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Umformen einer monströsen Gleichung
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite Zurück  1, 2, 3, 4  Weiter
Seite 2 von 4

 
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