Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

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






BeitragVerfasst am: 18 März 2005 - 12:29:46    Titel:

Hallo Aless

Der Witz ist gut - auch wenn er im Moment so nah an der Realität ist, dass mir das Lachen fast vergehen könnte: eine zeitlang ist das wunderbar gelaufen mit dem Testen, ich hab dann 'optimiert', hier eine Zeile weggelassen und dort eine und jetzt scheint eigentlich nur noch der Fehler übrigzubleiben Wink

Ich wäre Dir dankbar, wenn Du mir sagen könntest, welchen Output Du für diese beiden Fälle erhälst:


Code:
p1 = {x: 10, y:200};
p2 = {x: 10, y:100};
p3 = {x: 15, y:0};
p4 = {x: 10, y:200};

for(var i=0; i<=1; i += 0.1){
   p0 = cB.getPointOnCubicCurve(i, p1, p2, p3, p4);
   t1_arr = as2.getTOfPointOnCubicCurve(p0, p1, p2, p3, p4);
   trace('                    '+i+'   t_arr: '+t1_arr);
}


und - ebenfalls von 0 bis 1 - für diese Kurve:

Code:
p1 = {x: 10, y:200};
p2 = {x: 10, y:100};
p3 = {x: 10, y:0};
p4 = {x: 10, y:200};


Bei mir sind die Resultate zum Teil falsch (ich erhalte z.B für Start- und Endpunkt zugleich 0 und 1) und ich weiss nicht obs wegen den Aenderungen ist oder ob am Algorithmus selbst noch Aenderungen notwendig sind.

Besten Dank!

Andreas
Andreas Weber
Gast






BeitragVerfasst am: 18 März 2005 - 13:06:09    Titel:

Unsinn, sah da vor lauter Bäumen den Wald nicht mehr - die Punkte müssen in diesem Fall 2 Orte zurückgeben.
Bis später

Andreas Weber
Andreas Weber
Gast






BeitragVerfasst am: 18 März 2005 - 18:58:59    Titel:

Hallo Aless

Nachdem ich ziemlich intensiv mit der Funktion gearbeitet und noch ein paar kleinere Modifikationen gemacht habe, glaube ich jetzt sagen zu können: sie funktioniert bestens und ganz schön schnell! Very Happy

Ich muss vorsichtshalber hinzufügen, dass es immer noch gewisse 'Spezialfälle' gibt (vor allem bei den quadratischen), die ich noch nicht getestet habe oder die ich wohl getestet habe, nachträglich aber wieder Aenderungen gemacht habe und somit noch einmal testen muss.

Bei der 'Logik' hab ich noch ein ganz kleines Problem, das sich aber wahrscheinlich nicht lösen lässt:
Wenn der Start- und der Endpunkt am gleichen Ort sind und mit den Kontrollpunkten auf ener Linie liegen, steigt die Kurve zuerst in einer Linie auf und kommt dann auf der gleichen Linie zurück. Wir erhalten also für jeden Punkt auf der Linie korrekterweise 2 Werte für t.
Das kleine Problem ist nun, dass die Werte nicht in der 'logischen' Reihenfolge kommen. Wenn wir von t 0.1 bis 0.9 Punkte abfragen:
Code:
0.212786 | 0.1
0.2 | 0.168507
0.3 | 0.106879
0.4 | 0.046704
0.995141 | 0.5
0.93976 | 0.6
0.867562 | 0.7
0.8 | 0.776376
0.9 | 0.660081


In diesem Fall wird nur eine Liste verwendet (die andere enthält 'NAN') und die Wertpaare sind schon in dieser Reihenfolge in der Liste.
Ich sehe allerdings nicht, wie sich das korrigieren liesse, da sich die 'Logik' ja erst aus der Reihe (mehreren Punkten) ergibt, usere Funktionen aber nur einen Punkt auf's mal 'sehen'...


Hier meine ActionScript Version - beachte bitte vor allem die Aenderungen in der Funktion 'getTofPoint', Deiner 'reizeb'


Code:
   public function getTOfPointOnQuadCurve(p0:Object, p1:Object, p2:Object, p3:Object){
      return getTOfPoint.apply(this, arguments);
   }
   
   public function getTOfPointOnCubicCurve(p0:Object, p1:Object, p2:Object, p3:Object, p4:Object){
      return getTOfPoint.apply(this, arguments);
   }
   
   private function getTOfPoint(p0, p1, p2, p3, p4){
      var ax, bx, cx, dx, ay, by, cy, dy, xl, yl, i, j, k, jj, len1, len2, len3, min, p0, p1, p2, p3, p4, r, round, v;
      var p0x=p0.x, p0y=p0.y, p1x=p1.x, p1y=p1.y, p2x=p2.x, p2y=p2.y, p3x=p3.x, p3y=p3.y;
      
      // Due to rounding diffrences between the values of the xl and yl array
      // the correct result might be discarded, therefore we round to less decimal places.
      // Be aware that points that are very close to each other will have the same t
      round = 1000000;
      
      if(arguments.length==5){// cubic
         var p4x=p4.x, p4y=p4.y;
         
         ax = p4x-3*p3x+3*p2x-p1x;
         bx = 3*p3x-6*p2x+3*p1x;
         cx = 3*p2x-3*p1x;
         dx = p1x-p0x;
         
         ay = p4y-3*p3y+3*p2y-p1y;
         by = 3*p3y-6*p2y+3*p1y;
         cy = 3*p2y-3*p1y;
         dy = p1y-p0y;
      }else{// quadratic
         ax = 0;
         bx = p1x-2*p2x+p3x;
         cx = 2*p2x-2*p1x;
         dx = p1x-p0x;
      
         ay = 0;
         by = p1y-2*p2y+p3y;
         cy = 2*p2y-2*p1y;
         dy = p1y-p0y;
      }
      
      min = 1/round;
      if(ax < min && ax > 0-min){ax=0};
      if(bx < min && bx > 0-min){bx=0};
      if(cx < min && cx > 0-min){cx=0};
      if(dx < min && dx > 0-min){dx=0};
      if(ay < min && ay > 0-min){ay=0};
      if(by < min && by > 0-min){by=0};
      if(cy < min && cy > 0-min){cy=0};
      if(dy < min && dy > 0-min){dy=0};
      
      xl = solveCubicPolynomial(ax,bx,cx,dx);
      yl = solveCubicPolynomial(ay,by,cy,dy);
      
      for(i=0, len1 = xl.length; i<len1; i++){
         v = xl[i];
         if(v != 'NAN'){
            xl[i] = Math.round(v* round)/round;
         }
         v = xl[i];
         if(v<0 || v>1){
            xl.splice(i, 1);
            len1--;
            i--;
         }
      }
      for(i=0, len1=yl.length; i<len1; i++){
         v = yl[i];
         if(v != 'NAN'){
            yl[i] = Math.round(v* round)/round;
         }
         v = yl[i];
         if(v<0 || v>1){
            yl.splice(i, 1);
            len1--;
            i--;
         }
      }
      

      if (xl[0]=='NAN'){
          return yl;
      }else if (yl[0]=='NAN'){
         return xl;
      }else{
         r = new Array();
         
         len1=xl.length;
         len2=yl.length;
         
         for (i=0; i<len1 ; i++){
            for (j=0; j<len2 ; j++){
               if(xl[i] == yl[j]){
                  for (k=0, len3; k<r.length ; k++){
                     if(r[k] == xl[i]){
                        break;
                     }
                  }
                  r.push(xl[i]); 
                  yl.splice(j, 1);
                  len2--;
               }
            }
         }
         if(r.length > 0){
            return r;
         }else{
            return [-1];
         }
      }
   }
   
   /*by Aless Lasaruk, adapted by Andreas Weber*/
   private function solveCubicPolynomial(a, b, c, d) {
      var p, q, di, pi;
      
      if(a==0){
         if(b==0){
             if(c==0 && d==0){
               return ['NAN'];
             }else if(c != 0){
               return [-d/c];
             }
         }else{
            di = c*c-4*b*d;
            if (di < 0){
               return [];
            }else if(di==0) {
               return [-c/(2*b)];
            }else{
               return [(-c + Math.sqrt(di))/(2*b), (-c - Math.sqrt(di))/(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);
      
      di = q*q/4+p*p*p/27;
      if(di > 0){
         return [crt(-q/2+Math.sqrt(di))+crt(-q/2-Math.sqrt(di))-b/(3*a)];
      }else if(di==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)
               ];
      }

   }
   
   public function crt(x:Number):Number{
      return x<0 ? -Math.pow(-x,1/3) : Math.pow(x,1/3);
   }


Ich habe mich dazu entschlossen t auf 6 Dezimalstellen zu runden -
vielleicht kann ich die Zahl der Dezimalstellen auch noch erhöhen, aber das muss ich zuerst testen.
Code:
xl[i] = Math.round(v* round)/round;

Diese Lösung scheint mir etwas transparenter zu sein, als Differenzen fallweise zu ignorieren - oder spricht da etwas dagegen?

Die Anzahl Dezimalstellen sehe ich eher nicht als optionalen Parameter der durch den Benutzer der Funktion bestimmt wird - zumindest unter Flshcodern kann ich nicht erwarten, dass sie sich mit den Implikationen auseinandersetzen wollen (zuviele Dezimalstellen -> t kann unter Umständen nicht ermittelt werden, obwohl der Punkt auf der Kurve liegt) - ich glaube das sollte die Funktion als internes Problem behandeln.

Zudem: wir arbeiten hier mit einem visuellen Medium das an den Bilschirm gebunden ist - 6 Dezimalstellen sind 1000000 mögliche Werte für t - bei einer 1000 Pixel langen Kurve ist die Differenz zwischen 2 benachbarten Werten 1 tausensdstel Pixel - 1000 mal weniger als der Bildschirm darstellen kann.

Wie Du siehst

Code:
      if(ax < min && ax > 0-min){ax=0};
      if(bx < min && bx > 0-min){bx=0};
      if(cx < min && cx > 0-min){cx=0};
...

runde ich jetzt bereits die Parameter die der solve Methode übergegeben werden, wenn sie nahe bei 0 liegen. Ich hatte ein paar Kurven bei denen sonst die 'trivialen Fälle' (die ja auf 0 prüfen) nicht erkannt wurden.

Eine weitere Aenderung:

Code:
      if(v<0 || v>1){
            xl.splice(i, 1);
            len1--;
            i--;
         }


Ich entferne die Werte die nicht zwischen 0 und 1 liegen - ich kann mir beim besten Willen nicht vorstellen, was sie bedeuten könnten und wozu sie das aufrufende Programm verwenden könnte.

Beim Vergleich der beiden Listen ignoriere ich Werte die sonst mehrfach im Array, das zurückgegeben wird, vorkommen würden:

Code:
         for (i=0; i<len1 ; i++){
            for (j=0; j<len2 ; j++){
               if(xl[i] == yl[j]){
                  for (k=0, len3; k<r.length ; k++){
                     if(r[k] == xl[i]){
                        break;
                     }
                  }
                  r.push(xl[i]); 
                  yl.splice(j, 1);
                  len2--;
               }
            }
         }

Sonst erhalten wird in manchen Fällen (wenn Anfang und Endpunkt der Kurve identisch sind) solche Resultate: 1, 0, 0 - auch hier kann ich mir nicht vorstellen, dass die Ausgabe der doppelten 0 an das aufrufende Programm sinnvoll ist.

Die übrigen Aenderungen haben nichts mit der Logik der Funktionen zu tun, sondern sind semantischer Art (kein eigentliches Overloading/Polymorphismus in ActionScript, alle Zalhlen sind schlicht als 'Number' getypt, alse keine doubles etc.) und vor allem habe ich versucht die Funktion möglichst schnell zu machen und 'Bremser' zu eliminieren.
Beispiele:
Schleifen Optimierung
Code:
for (int i = 0; i < xl.size(); i++)

in ActionScript besser

Code:
for(var i=0, len= xl.length; i<len; i++){


da der erste Teil der Signatur (vor dem ersten ';') nur einmal ausgeführt wird, der 2. und 3. Teil jedoch bei jeder Iteration - was den Player zwingt die Länge des Arrays bei jedem Umgang neu zu evaluieren.

Bei verschachtelten Loops, die Elemente aus dem Array nehmen, die bei der nächsten Iteration nicht mehr gebraucht werden (splice() und Anpassen der Counter).

push() (push_back() in C++) zwingt den Player zuerst die Länge des Arrays zu evaluieren, direkte Zuweisung an eine bestimmte Indexposition ist deshalb schneller.
Der 'Lookup' von Referenzen kostet jedesmal ein bisschen Zeit: x.someProperty ist bei mehrfacher Verwendung langsamer als die Schaffung eines 'shortcuts' - xprop = x.someProperty auf den dann direkt zugegriffen werden kann.
Optimierung bei den Bedingungsprüfungen:

Code:
      if(a==0){
         if(b==0){
             if(c==0 && d==0){


Durch diese Stufung wird im Normalfall (eben kein 'trivialer Fall') nur 1 Test durchgeführt (vorher 9).

Das weisst Du ja alles auch und wahrscheinlich besser als ich - ich wollt nur zeigen, dass ich nicht völlig untätig auf die richtige Lösung gewartet habe Wink

Und noch einmal: herzlichen Dank!

Andreas Weber












[/code]
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 18 März 2005 - 20:20:17    Titel:

Ich sehe, Du hast Dich mächstig ins Zeug gelegt und teilweise numerische Probleme eliminiert, von denen ich gesprochen habe. Der Test auf Gleichheit ist Mist bei Gleitkommazahlen. Naja.

Zu weiteren Optimierungen könnte man komplett auch Vektoren verzichten, denn diese sind ja sowieso nur höchstens 3-elementig. Daher wäre es vielleicht sogar vernünftiger einfach mit 3-tupeln rumzuhantieren. So hart auf die Tour "double l[3]". Man könnte die Auswahl der gleichen Werte aus den Arrays noch hart codieren (ohne Schleifen).

Aus meiner Erfahrung sind aber solche Sachen nur dann vom Vorteil, wenn es in der Größenordnung 10^k mit k > 2 Elementar-Operationen (wie Bild- oder Arrayzugriffe) geht. Meine Erfahrung aus Bildverarbeitung (Das Sensorsystem unseres RoboCUP-Roboters hat 25ms zur Positionsbestimmung aus Kamerabildern benötigt. Dabei ist gut auf 1/3 des Bildes zugegriffen worden; durch harte Optimierung fast schon auf maschinensprachen-Niveau) ist, man sollte solange nicht an Pointern, Lookup-Tabellen und Referenzen optimieren sollte, bis der Algorithmus richtig optimiert wurde.

Naja. In diesem Fall geht es nachweisbar nicht schneller, außer in wenigen Speziallfällen.

Ich bin jetzt ein wenig mit meiner Diplomarbeit beschäftigt, schreibe aber, sobald ich mit meiner Theorie fertig bin. Ich hoffe bald...
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
Seite 4 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