[Erledigt] PHP Bresenham-Algorithmus für alle Oktanten und m > 1 OR m < -1 - Seite 2

eagle275 · 04.01.2011, 15:46

na hast du ein Glück - c++ verwendet nicht nur die gleiche Syntax wie php (oder php die von C / C++ ^^) sondern damit bist du ja quasi fertig -

alles was dir bleibt ist die Aufrufe von plot() umzubauen, dass dort die Farbe des Pixels an diesen Koordinaten ermittelt wird und geeignet reagieren.

und "natürlich" kannst du dir bei php die Typdeklarationen der Variablen sparen - und die Variablen brauchen ein $ davor ...

im Zweifel schau hier nach, ob du Operatoren ersetzen musst http://www.html-world.de/program/php_4.php aber ich hab bisher nichts gesehen, dass php nicht könnte ....

AIRMAKZ · 04.01.2011, 16:11

Also ich habe den Code jetzt soweit umgeschrieben, dass PHP zumindest keinen Fehler mehr ausspuckt.

PHP-Code:

    $x1 = 1;

  $y1 = 1;

  $x2 = 50;

  $y2 = 100;

  

  $delta_x = ($x2 > $x1?($ix = 1 AND $x2 - $x1):($ix = -1 AND $x1 - $x2)) << 1;

  $delta_y = ($y2 > $y1?($iy = 1 AND $y2 - $y1):($iy = -1 AND $y1 - $y2)) << 1;

 
  print "x: " . $x1 . " y: " . $y1 . "<br>";

  if ($delta_x >= $delta_y) {

    $error = $delta_y - ($delta_x >> 1);

    while ($x1 != $x2) {

      if ($error >= 0) {

        if ($error || ($ix > 0)) {

          $y1 += $iy;

          $error -= $delta_x;

        }

      }

      $x1 += $ix;

      $error += $delta_y;

      print "x: " . $x1 . " y: " . $y1 . "<br>";

    }

  }

  else {

    $error = $delta_x - ($delta_y >> 1);

    while ($y1 != $y2) {

      if ($error >= 0) {

        if ($error || ($iy > 0)) {

          $x1 += $ix;

          $error -= $delta_y;

        }

      }

      $y1 += $iy;

      $error += $delta_x;

      print "x: " . $x1 . " y: " . $y1 . "<br>";

    }

  }

Funktioniert bisher auch einwandfrei. Man beachte allerdings den Fall, dass die Steigung > 1 ist (siehe Variablen x1, y1, x2, y2). Das Script zählt immer nur 1 hoch und bleibt am Ende bei x = 50 stehen (y hat ebenfalls den Wert 50). Umgekehrt wenn die Steigung geringer ist und die Schleife rückwärts läuft, liefert er negative Werte was auf keinen Fall sein darf.

Bin gerade dabei zu verstehen was das Script eigentlich genau macht...

eagle275 · 04.01.2011, 16:22

nein - da hast du irgendwas übersehen - die Zeilen mit der Berechnung von $delta_x und $delta_y - die stimmen nicht

PHP-Code:

  
$delta_x = 0;
if ($x2 > $x1) {
 $ix = 1; 
 $delta_x= ($x2 - $x1)<<1;
}
else {
 $ix = -1;
 $delta_x=($x1 - $x2) << 1;
}
$delta_y =0;
if  (y2 > y1) {
 $iy = 1;
 $delta_y=($y2 - $y1)<< 1;
}
else {
 $iy = -1;
 $delta_y=($y1 - $y2) << 1;
}

php kann beim Trinären Operator leider immer nur 1 Befehl ausführen, C++ offensichtlich mehrere Operationen mit Komma stapeln

wenn du die Zeilen durch meinen Code hier ersetzt, wirst du sehen, dass sehr wohl Steigungen über 1 möglich sind

Und kurz zur Erklärung .. zuerst wird der X-Abstand und der y-Abstand der Punkte berechnet (zusammen mit den Steigungen in x-Richtung $ix und y-Richtung $iy) und dann anhand dessen entschieden, ob nun in X-Richtung oder in Y-Richtung gearbeitet wird ( das erste große if außen herum)

im Then / Else zweig werden die Punkt-Koordinaten in einer Schleife berechnet (x1 += ix (increment x , also der Zuwachs in x - Richtung) y1+=iy (increment y, Zuwachs in y-Richtung) -

mit error wird festgestellt, ob man den Rand des Bildes erreicht hat - theoretisch kann passieren, dass die Funktion durch die increment-Werte in Bereiche außerhalb des Bildschirms gerät (iimmer genau beim letzten Rechenschritt, wegen der Rundungsdifferenzen )

AIRMAKZ · 04.01.2011, 16:35

Wow, danke! Funktioniert jetzt alles einwandfrei und wesentlich schneller als mein bisheriges Script!

Hier nochmals die Zusammenfassung (falls irgendwann nochmal jemand danach suchen sollte)

PHP-Code:

    # $x1 = rand(1,500);
  # $y1 = rand(1,500);
  # $x2 = rand(1,500);
  # $y2 = rand(1,500);
  
  # print "Alt x: " . $x1 . " y: " . $y1 . "<br>Neu x: " . $x2 . " y: " . $y2 . "<br><br>";

  $delta_x = 0;
  
  if($x2 > $x1) { $ix = 1; $delta_x = ($x2 - $x1) <<1; }
    else { $ix = -1; $delta_x = ($x1 - $x2) << 1; }
    
  $delta_y = 0;
  
  if($y2 > $y1) { $iy = 1; $delta_y = ($y2 - $y1) << 1; }
    else { $iy = -1; $delta_y = ($y1 - $y2) << 1; }  

  print "x: " . $x1 . " y: " . $y1 . "<br>";
  if ($delta_x >= $delta_y) {
    $error = $delta_y - ($delta_x >> 1);
    while ($x1 != $x2) {
      if ($error >= 0) {
        if ($error || ($ix > 0)) {
          $y1 += $iy;
          $error -= $delta_x;
        }
      }
      $x1 += $ix;
      $error += $delta_y;
      print "x: " . $x1 . " y: " . $y1 . "<br>";
    }
  }
  else {
    $error = $delta_x - ($delta_y >> 1);
    while ($y1 != $y2) {
      if ($error >= 0) {
        if ($error || ($iy > 0)) {
          $x1 += $ix;
          $error -= $delta_y;
        }
      }
      $y1 += $iy;
      $error += $delta_x;
      print "x: " . $x1 . " y: " . $y1 . "<br>";
    }
  }

Problem solved! (Rasterung einer Linie zwischen 2 Punkten mit dem Bresenham-Algorithmus für alle Oktanten/Steigungen/Richtungen in PHP)

Jetzt muss ich nur noch meine Streckenberechnung und die Kollisionsabfrage einbauen.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Thema bewerten
Thema bewerten:

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Scriptangebot Paginator Algorithmus	Chriz	Scriptbörse	7	16.11.2010 22:04
[Erledigt] Algorithmus für: Es sind nur xyz Anfragen gleichzeitig möglich.	Curcio	Server, Hosting und Workstations	2	16.10.2010 18:06
SEARCH deutsche Alternative für PorterStemmer algorithmus?	phpstudent	Datenbanken	14	08.03.2010 22:34
[Erledigt] PHP MYSQL problem: Algorithmus	wuk	PHP Tipps 2010	5	03.03.2010 15:41
[Erledigt] Timestamp Algorithmus	fisianer2099	PHP Tipps 2009	4	31.10.2009 19:25
Umsetzung eines eigenen Caching Algorithmus	HStev	Software-Design	35	24.12.2008 16:16
Tag Cloud: Algorithmus für Schriftgröße	Simbo	PHP-Fortgeschrittene	15	23.10.2008 19:53
Pathfinding Algorithmus optimieren? (Algorith. von Dijkstra)	Martin13	PHP Tipps 2007	19	04.09.2007 19:20
Bruteforce Algorithmus	aceflow	PHP Tipps 2008	4	04.09.2007 16:53
Algorithmus für Suchwortrelevanz	tinchen	PHP Tipps 2006	3	06.12.2006 01:27
Algorithmus, verschlüsselungssystem	notyyy	PHP Tipps 2006	7	22.08.2006 09:08
[Erledigt] Algorithmus für binomische Formeln...		PHP-Fortgeschrittene	19	02.12.2004 09:03
Algorithmus Bestimmung d. äußeren Polygons im 2D-Punktfeld?	tapferesschneiderlein	Off-Topic Diskussionen	4	31.08.2004 15:12

04.01.2011, 15:46
eagle275 Erfahrener Benutzer Registriert seit: 01.09.2010 Beiträge: 4.561 PHP-Kenntnisse: Fortgeschritten	na hast du ein Glück - c++ verwendet nicht nur die gleiche Syntax wie php (oder php die von C / C++ ^^) sondern damit bist du ja quasi fertig - alles was dir bleibt ist die Aufrufe von plot() umzubauen, dass dort die Farbe des Pixels an diesen Koordinaten ermittelt wird und geeignet reagieren. und "natürlich" kannst du dir bei php die Typdeklarationen der Variablen sparen - und die Variablen brauchen ein $ davor ... im Zweifel schau hier nach, ob du Operatoren ersetzen musst http://www.html-world.de/program/php_4.php aber ich hab bisher nichts gesehen, dass php nicht könnte .... __________________ "Irren ist männlich", sprach der Igel und stieg von der Drahtbürste


Mister Ad PHP Code Flüsterer Registriert seit: 21.08.2005 Beiträge: 4682 PHP-Kenntnisse: Fortgeschritten

04.01.2011, 16:11
AIRMAKZ Neuer Benutzer Registriert seit: 03.01.2011 Beiträge: 8 PHP-Kenntnisse: Fortgeschritten	Also ich habe den Code jetzt soweit umgeschrieben, dass PHP zumindest keinen Fehler mehr ausspuckt. PHP-Code: $x1 = 1; $y1 = 1; $x2 = 50; $y2 = 100; $delta_x = ($x2 > $x1?($ix = 1 AND $x2 - $x1):($ix = -1 AND $x1 - $x2)) << 1; $delta_y = ($y2 > $y1?($iy = 1 AND $y2 - $y1):($iy = -1 AND $y1 - $y2)) << 1; print "x: " . $x1 . " y: " . $y1 . "<br>"; if ($delta_x >= $delta_y) { $error = $delta_y - ($delta_x >> 1); while ($x1 != $x2) { if ($error >= 0) { if ($error \|\| ($ix > 0)) { $y1 += $iy; $error -= $delta_x; } } $x1 += $ix; $error += $delta_y; print "x: " . $x1 . " y: " . $y1 . "<br>"; } } else { $error = $delta_x - ($delta_y >> 1); while ($y1 != $y2) { if ($error >= 0) { if ($error \|\| ($iy > 0)) { $x1 += $ix; $error -= $delta_y; } } $y1 += $iy; $error += $delta_x; print "x: " . $x1 . " y: " . $y1 . "<br>"; } } Funktioniert bisher auch einwandfrei. Man beachte allerdings den Fall, dass die Steigung > 1 ist (siehe Variablen x1, y1, x2, y2). Das Script zählt immer nur 1 hoch und bleibt am Ende bei x = 50 stehen (y hat ebenfalls den Wert 50). Umgekehrt wenn die Steigung geringer ist und die Schleife rückwärts läuft, liefert er negative Werte was auf keinen Fall sein darf. Bin gerade dabei zu verstehen was das Script eigentlich genau macht...

04.01.2011, 16:22
eagle275 Erfahrener Benutzer Registriert seit: 01.09.2010 Beiträge: 4.561 PHP-Kenntnisse: Fortgeschritten	nein - da hast du irgendwas übersehen - die Zeilen mit der Berechnung von $delta_x und $delta_y - die stimmen nicht PHP-Code: `$delta_x = 0; if ($x2 > $x1) { $ix = 1; $delta_x= ($x2 - $x1)<<1; } else { $ix = -1; $delta_x=($x1 - $x2) << 1; } $delta_y =0; if (y2 > y1) { $iy = 1; $delta_y=($y2 - $y1)<< 1; } else { $iy = -1; $delta_y=($y1 - $y2) << 1; }` php kann beim Trinären Operator leider immer nur 1 Befehl ausführen, C++ offensichtlich mehrere Operationen mit Komma stapeln wenn du die Zeilen durch meinen Code hier ersetzt, wirst du sehen, dass sehr wohl Steigungen über 1 möglich sind Und kurz zur Erklärung .. zuerst wird der X-Abstand und der y-Abstand der Punkte berechnet (zusammen mit den Steigungen in x-Richtung $ix und y-Richtung $iy) und dann anhand dessen entschieden, ob nun in X-Richtung oder in Y-Richtung gearbeitet wird ( das erste große if außen herum) im Then / Else zweig werden die Punkt-Koordinaten in einer Schleife berechnet (x1 += ix (increment x , also der Zuwachs in x - Richtung) y1+=iy (increment y, Zuwachs in y-Richtung) - mit error wird festgestellt, ob man den Rand des Bildes erreicht hat - theoretisch kann passieren, dass die Funktion durch die increment-Werte in Bereiche außerhalb des Bildschirms gerät (iimmer genau beim letzten Rechenschritt, wegen der Rundungsdifferenzen ) __________________ "Irren ist männlich", sprach der Igel und stieg von der Drahtbürste Geändert von eagle275 (04.01.2011 um 16:36 Uhr).

04.01.2011, 16:35
AIRMAKZ Neuer Benutzer Registriert seit: 03.01.2011 Beiträge: 8 PHP-Kenntnisse: Fortgeschritten	Wow, danke! Funktioniert jetzt alles einwandfrei und wesentlich schneller als mein bisheriges Script! Hier nochmals die Zusammenfassung (falls irgendwann nochmal jemand danach suchen sollte) PHP-Code: # $x1 = rand(1,500); # $y1 = rand(1,500); # $x2 = rand(1,500); # $y2 = rand(1,500); # print "Alt x: " . $x1 . " y: " . $y1 . "<br>Neu x: " . $x2 . " y: " . $y2 . "<br><br>"; $delta_x = 0; if($x2 > $x1) { $ix = 1; $delta_x = ($x2 - $x1) <<1; } else { $ix = -1; $delta_x = ($x1 - $x2) << 1; } $delta_y = 0; if($y2 > $y1) { $iy = 1; $delta_y = ($y2 - $y1) << 1; } else { $iy = -1; $delta_y = ($y1 - $y2) << 1; } print "x: " . $x1 . " y: " . $y1 . "<br>"; if ($delta_x >= $delta_y) { $error = $delta_y - ($delta_x >> 1); while ($x1 != $x2) { if ($error >= 0) { if ($error \|\| ($ix > 0)) { $y1 += $iy; $error -= $delta_x; } } $x1 += $ix; $error += $delta_y; print "x: " . $x1 . " y: " . $y1 . "<br>"; } } else { $error = $delta_x - ($delta_y >> 1); while ($y1 != $y2) { if ($error >= 0) { if ($error \|\| ($iy > 0)) { $x1 += $ix; $error -= $delta_y; } } $y1 += $iy; $error += $delta_x; print "x: " . $x1 . " y: " . $y1 . "<br>"; } } Problem solved! (Rasterung einer Linie zwischen 2 Punkten mit dem Bresenham-Algorithmus für alle Oktanten/Steigungen/Richtungen in PHP) Jetzt muss ich nur noch meine Streckenberechnung und die Kollisionsabfrage einbauen. Geändert von AIRMAKZ (04.01.2011 um 16:39 Uhr).