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

AIRMAKZ · 03.01.2011, 17:35

Problem gelöst! Siehe: http://www.php.de/php-fortgeschritte...tml#post568598 ([Erledigt] PHP Bresenham-Algorithmus für alle Oktanten und m > 1 OR m < -1)

Hallo zusammen! Meine Frage habe ich bereits ausführlich gegooglet und in einer leichten Abwandlung bereits in einem anderem Forum geposted (wo man mir scheinbar nicht helfen wollte oder nicht helfen konnte...zumindest ist nichts draus geworden).

Ich formuliere es so kurz wie möglich:

Ich habe eine weiße Bilddatei auf der sich zufällige schwarze Pixel befinden.
Nun sind zwei Punkte gegeben deren Anordnung ebenfalls zufällig sein kann.

X_a kann sich also z.B. rechts von X_b befinden. Für eine lineare Funktion bedeutet dies, dass ich die Punkte a und b also vertauschen müsste.

Auf der Strecke zwischen beiden Punkte soll nun überprüft werden, ob sich dort ein schwarzer Pixel befindet (die Abfrage ist kein Problem).

Ebenso kann die Steigung m > 1 oder m < -1 sein, was für die lineare Funktion bedeuten würde dass sie nicht mehr alle Punkte auf der Strecke erfasst (Rasterung von Linien).

Ich habe in PHP bereits ein ausführliches Script geschrieben, welches alle Fälle für alle Oktankten berücksichtigt:

- X_a < X_b
-- m >= -1 AND m <= 1
-- m > 1
-- m < 1
- X_a > X_b
-- gleiche Fälle wie oben, X_a und X_b werden aber vertauscht
- X_a = X_b
-- hier wird nur noch unterschieden ob Y_a <> Y_b ist und die Punkte bis zum ,,Ziel" gezählt

Wie man sich sicher vorstellen kann, ist meine Lösung äußerst unelegant und ,,frisst" bei starker Belastung viele Serverressourcen. Bei meiner Recherche ist mir allerdings aufgefallen, dass PHP bereits über eine Funktion verfügt die problemlos gerasterte Linien in alle Richtungen zeichnen kann. Ich weiß leider nicht, wie man diese abwandeln könnte dass sie den Zweck einer Kollisionsabfrage erfüllt - denn eine Linie zeichnen möchte ich nicht.

Um Ressourcen zu sparen habe ich mich bereits auch kurz mit dem Bresenham-Algorithmus beschäftigt (der sicher von der oben genannten PHP-Funktion benutzt wird). Allerdings sind im Internet nur Beispiele in Java/Pseudo-Code vorhanden, was an sich kein Problem darstellen würde wenn ich die Abwandlungen für alle anderen Oktanten nicht selbst abstrahieren müsste, was zur Folge hat dass der Code wohlmöglich wieder unendlich lang wird.

Mein nächstes Problem beschäftigt sich dann noch mit der Berechnung der Länge der Strecke zwischen den beiden Punkten, die man zwar mit dem Satz des Pythagoras berechnen kann aber ebenfalls für alle anderen Oktanten wieder umgeschrieben werden muss.

Das letzte Problem beschäftigt sich dann letztendlich noch mit der Richtung in Grad, die mit tan^-1 auch kein Problem darstellt, wenn ich nicht vorher die Abwandlungen gemacht hätte, damit die lineare Funktion überhaupt alle Fälle umfasst.

Ihr seht, es handelt sich um ein größeres Problem...meinen Code würde ich auch ehrlich gesagt nur ungern posten.

Vielleicht habt ihr ja auf Anhieb einen erleuchtenden Vorschlag.

Nochmal kompakte Kurzfassung:

Gegeben sind 2 Punkte. Punkt A kann sich rechts von Punkt B befinden. Ich möchte die vollständige Punktmenge der Geraden bestimmen (Rasterung von Linien). Dies soll für alle Fälle möglich sein (egal welche Steigung, egal welche Richtung). Zudem möchte ich die Länge der Strecke berechnen und die Richtung in Grad. Und das alles möglichst kompakt und vor allem ressourcensparend.
Ich möchte keine Linie zeichnen!

Grüße, Simon

Edit:

Die Funktion, die ich gerne abwandeln würde heißt imageline.
Gibt es nicht eine Möglichkeit die Pixel, die von imageline gezeichnet werden über Arrays auszulesen? z.B. irgendwie P_a[1] = imageline () oder ähnliches?

Chriz · 03.01.2011, 18:13

Hallo,

also meine erste Idee war es einfach ein neues Bild zu nehmen, die Linie zu zeichnen (liegt im Speicher, stört ja keinen) und die Punkte dann auszulesen. Nicht performant, aber zumindest korrekt und vor allem flexibel. Weil wie du die Linie zeichnest, mit welcher Seitenstärke, gerade oder gebogen ist dann egal.

Mein zweiter Ansatz wäre dann die Linienlänge pixelweise zu verkleinern.

Wenn du eine Linie (0/0; 10/10) hast, verkürzt du die Linienlänge von Wurzel(200) immer schrittweise um 10% (da 10=10-0, aber je nach Genauigkeit, ausgehend von der Originallänge) und landest dann (starten von 0/0) eben auf einem deiner gesuchten Pixel (bzw. eher einer Pixelmenge mit Gewichtung). Ich kenn jetzt ehrlich gesagt die Formel nicht mehr dafür (obwohl ichs müsste, da ich letztes Jahr Diagramme mit Imagick gezeichnet hab), aber die sollte sich doch in jedem Matheheftchen finden lassen. Oder ists gerade das was du suchst? Dann stellst du die Frage vielleicht besser in einem Matheforum

AIRMAKZ · 03.01.2011, 18:16

Zitat:

Zitat von Chriz

Hallo,

also meine erste Idee war es einfach ein neues Bild zu nehmen, die Linie zu zeichnen (liegt im Speicher, stört ja keinen) und die Punkte dann auszulesen. Nicht performant, aber zumindest korrekt und vor allem flexibel. Weil wie du die Linie zeichnest, mit welcher Seitenstärke, gerade oder gebogen ist dann egal.

[...]

Die Idee hatte ich bereits auch. Das Problem ist (abgesehen von der benötigten Serverleistung) dann aber dass ich zwar die Pixel der Linie habe, aber nicht mehr von Punkt A nach Punkt B wander und dafür eine zusätzliche Funktion schreiben müsste. Das könnte größeren Aufwand bedeuten als mein jetziges Script (welches zwar jeden Fall berücksichtigt, aber auch immer wieder das gleiche in leichter Abwandlung erledigt).

Edit:
Um besser darzustellen was ich eigentlich machen möchte poste ich mal meinen Code...vielleicht kann der ein oder andere da sogar noch was optimieren.

PHP-Code:

    $x_a = $_POST['x_a'];
  $y_a = $_POST['y_a'];
  # Startpunkt
  $x_b = $_POST['x_b'];
  $y_b = $_POST['y_b'];
  # Zielpunkt

  $step = 50;
  $speed = 1000;
  # Nachher nur wichtig um die Geschwindigkeit anhand der Strecke zu berechnen,
  # für mein Problem derzeit aber unwichtig

  $image = imagecreatefromgif("map.gif");
  # Die Bilddatei, auf der die Kollisionen überprüft werden

  $signum = 1;
  # Vorzeichen für den Zähler nachher (in diesem Fall: gehe nach RECHTS)
  $start = $x_a;
  $ziel = $x_b;
  # Setzt die Variablen für die Schleife
  $coll = -5;
  # Geht 5 Schritte zurück wenn eine Kollision gefunden wurde
  if($x_a > $x_b) {
  # Prüft ob der Startpunkt RECHTS vom Zielpunkt liegt
    list($x_a, $x_b) = array($x_b, $x_a);
    list($y_a, $y_b) = array($y_b, $y_a);
    # Vertauscht dann die Variablen, damit eine lineare Funktion möglich ist
    $signum = -1;
    # Vorzeichen um vom Startpunkt aus nach links zu gehen
    $start = $x_b;
    $ziel = $x_a;
    # Setzt die Variablen für die Schleife, in diesem Fall anders weil die Schleife rückwärts
    # zählt um von LINKS nach RECHTS zu gehen
    $coll = 5;
  }
  @$m = ($y_b - $y_a) / ($x_b - $x_a);
  # Berechnet nun die Steigung der linearen Funktion
  if($m >= -1 AND $m <= 1) {
  # Prüft ob die Steigung ,,gültig" ist.
  # Sollte die Steigung nämlich nicht die oben geforderten Bedingungen erfüllen,
  # so kann die lineare Funktion nicht alle Punkte berechnen (siehe ,,Rastern von Linien")
    while($start != $ziel) {
    # Solange wir noch nicht am Ziel sind...
      $start = $start + $signum;
      # ...gehe einen Schritt
      $y_tmp = ($m * ($start - $x_a)) + $y_a;
      # Berechne den y-Wert des aktuellen x-Wertes
      if(imagecolorat($image, $start, $y_tmp) == 0) {
      # Prüfe den aktuellen Punkt auf eine Kollision
        $start = $start + $coll;
        $y_tmp = ($m * ($start - $x_a)) + $y_a;
        $duration = [...] # <- unwichtiger Code entfernt (zu lang)
        # Geht dann 5 Schritte zurück und berechnet die Geschwindigkeit, wie gesagt derzeit unwichtig
        print round($start) . "," . round($y_tmp) . "," . $duration;
        exit();
        # Gibt den Punkt der Kollision aus (bzw. 5 Werte vorher) und beendet das Script
      }
    }
    $duration = [...] # <- unwichtiger Code entfernt (zu lang)
    if($signum == -1) { list($x_a, $x_b) = array($x_b, $x_a);
    list($y_a, $y_b) = array($y_b, $y_a); }
    # Vertauscht wieder die Variablen, falls sie zuvor vertauscht wurden
    print $x_b . "," . $y_b . "," . $duration;
    # Gibt den Zielpunkt aus, wenn keine Kollision gefunden wurde
  }
  else {
  # Im Prinzip das selbe wie oben, allerdings ,,gespiegelt" falls die Steigung >1 oder <-1 ist
  # (Siehe dazu Rastern von Linien)
    if($signum == -1) { list($x_a, $x_b) = array($x_b, $x_a);
    list($y_a, $y_b) = array($y_b, $y_a); }
    $signum = 1;
    $start = $y_a;
    $ziel = $y_b;
    $coll = -5;
    if($y_a > $y_b) {
      list($x_a, $x_b) = array($x_b, $x_a);
      list($y_a, $y_b) = array($y_b, $y_a);
      $signum = -1;
      $start = $y_b;
      $ziel = $y_a;
      $coll = 5;
    }
    @$m = ($x_b - $x_a) / ($y_b - $y_a);
    while($start != $ziel) {
      $start = $start + $signum;
      $x_tmp = ($m * ($start - $y_a)) + $x_a;
      if(imagecolorat($image, $x_tmp, $start) == 0) {
        $start = $start + $coll;
        $x_tmp = ($m * ($start - $y_a)) + $x_a;
        $duration = [...] # <- unwichtiger Code entfernt (zu lang)
        print round($x_tmp) . "," . round($start) . "," . $duration;
        exit();
      }
    }
    $duration = [...] # <- unwichtiger Code entfernt (zu lang)
    if($signum == -1) { list($x_a, $x_b) = array($x_b, $x_a);
    list($y_a, $y_b) = array($y_b, $y_a); }
    print $x_b . "," . $y_b . "," . $duration;
  }

Paul.Schramenko · 04.01.2011, 11:44

Zitat:

Zitat von AIRMAKZ

PHP-Code:

    @$m = ($y_b - $y_a) / ($x_b - $x_a);
  # Berechnet nun die Steigung der linearen Funktion
  if($m >= -1 AND $m <= 1) {

Bin noch am lesen, aber für den Fall das beide Punkte den selben $x-Wert haben ergibt $m = false. Ist wohl nicht berücksichtigt. Damit wird $m=0 wie der else-Part behandelt (-1 > $m > 1)
Bin aber noch am lesen

eagle275 · 04.01.2011, 12:17

ich versteh dich so, dass du für jeden Oktanten / Quadranten die Rechenvorschrift separat codierst - das ist aber blödsinn - warum tauschst du nicht einfach "quick and dirty" die Koordinatenwerte der Punkte aus, dann berechnest du das m und gut ist. Wenn ich mich dunkel an meine Assembler-Zeit aufm C64 erinnere blieben am Ende sowieso nur noch 2 Fälle übrig, weil die Optimierung dahin lief, m immer größer oder gleich 1 zu machen (sprich es wurde untersucht ob der X-Abstand oder der Y-Abstand der beiden Punkte größer war und die Schleife nahm immer den längeren "Weg", wenn ich mich recht erinnere - einmal wurde also anhand der y-Koordinate iteriert und beim anderen Pfad anhand der x-Koordinate (warum, siehst du bei Paul und bei mir weiter unten). Alles andere wurde mit dem Koordinatentauschen normalisiert.

Anmerkung zu Pauls These .. wenn du IMMER über x-gehst, dann ergibt gleiche X-Koordinate leider eine unendliche Steigung, weil Division durch 0 .... daher die Betrachtung, was der kürzere Weg ist.

In meinem Fall wäre der x-Weg kürzer und daher würde m nunmehr als (x_a-x_b) / (y_a-y_b) berechnet .. und eine Steigung von 0 als Abweichung zur Senkrechten ist ja auch verständlich

AIRMAKZ · 04.01.2011, 13:51

Die Division durch 0 liefert in PHP einen Fehler zurück, deswegen steht auch ein @ vor $m. In der Mathematik sind Berechnungen mit Steigung 0 bei linearen Funktionen problemlos möglich.

Die Schleife wird ja trotzdem korrekt durchlaufen. Bisher macht jede Funktion ja in etwa das selbe. Wenn x_a < x_b und m >= -1 AND m <= 1 normale lineare Funktion. Wenn x_a > x_b dann werden die Koordinaten x_a mit x_b und y_a mit y_b vertauscht und die Schleife läuft rückwärts. Damit habe ich 4 Oktankten abgedeckt.

Wenn die Steigung allerdings m < -1 OR m > 1 beträgt wird es allerdings etwas komplizierter, weil die Schleife durch y läuft und x mit der linearen Funktion berechnet wird.

Theoretisch müsste das alles mit einer Schleife lösbar sein, daran arbeite ich auch derzeit, hab allerdings noch so meine Probleme damit.

Mein Ziel ist es, wie bereits gesagt, dass alles möglichst ressourcensparend funktioniert. Deswegen auch nochmal eine Frage am Rande: gibt es eine Möglichkeit die von imageline berechneten Koordinaten aus der Funktion zu extrahieren?

eagle275 · 04.01.2011, 14:12

nicht ohne dass du es entsprechend einbaust - und das wird nicht gehen, weil die Funktionen von GD nunmal in einem shared-Object stecken (vergleichbar DLL-Datei) also in binärer Form.

Mithin kannst du auch gleich selbst nen Bresenham-Algorithmus bauen, nur eben statt setpixel analysierst du die Farbe des Bildpunktes ( das hast du ja hinbekommen)

eventuell hilft da auch noch was anderes ...

Kennst du denn die Koordinaten der zufälligen Punkte in der Grafik ? dann kannst du auch direkt mit Berechnungen herausfinden, ob und welche der Punkte auf der Verbindungslinie liegen - ich werd zu hause mal in mein Algorithmen Buch gucken - Robert Sedgewick ein genialer Autor und Professor (MIT) ist zwar Pascal aber leicht in php umzuwandeln.

AIRMAKZ · 04.01.2011, 15:07

Zuerst wollte ich meinen derzeitigen ,,Algorithmus" so gut wie es geht optimieren, bevor ich mich direkt mit dem Bresenham-Algorithmus beschäftige.

Die Koordinaten der Kollisionspunkte kenne ich nicht. Es wäre möglich die Bilder einzulesen und die Punkte in einer Datenbank abzuspeichern...aber die Datenbank-Abfrage wäre bei so vielen Koordinaten bestimmt aufwendiger (von der Rechenleistung her) als das direkte Ansprechen der Bilddatei.

Bzw. ich bin mir nicht sicher ob es ressourcenraubender wäre...aber bei einem Kollisionsobjekt von 100x100px sind das schon 2x10.000 Werte in der Datenbank.

eagle275 · 04.01.2011, 15:21

nö die Datenbank macht das schon fix - das Problem ist eher das script, das die Bilder mit den Zufallspixeln analysiert - das muss nämlich in einer geschachtelten Schleifenkonstruktion das Bild quasi scannen (von x =0 bis MAX_X und dabe dann jeweils y von 0 bis MAX_Y ) .. das dauert ja ewig - je nach Anzahl der Bilder

Da wär es besser du optimierst deinen Algorithmus in Richtung Bresenham - eigentlich bist du gar nicht mehr so weit davon entfernt

AIRMAKZ · 04.01.2011, 15:28

Zitat:

Zitat von eagle275

nö die Datenbank macht das schon fix - das Problem ist eher das script, das die Bilder mit den Zufallspixeln analysiert - das muss nämlich in einer geschachtelten Schleifenkonstruktion das Bild quasi scannen (von x =0 bis MAX_X und dabe dann jeweils y von 0 bis MAX_Y ) .. das dauert ja ewig - je nach Anzahl der Bilder

Da wär es besser du optimierst deinen Algorithmus in Richtung Bresenham - eigentlich bist du gar nicht mehr so weit davon entfernt

Nunja, allzu viele Bilder sind es ja nicht...und wenn die einmal eingetragen sind spielt die Dauer des ,,Einscannens" für die weiteren Abfragen keine Rolle mehr, da im Endeffekt ja nur noch auf die Datenbank zugeriffen wird.

Aber ich kann mir schlecht vorstellen, dass die Datenbank wirklich so fix arbeitet wie die direkte Abfrage des Bildes mit Bresenham.
Beim Bresenham habe ich eine gewisse Punktmenge die abgefragt werden muss. In der Datenbank wird jeder Eintrag abgefragt und das könnte, wie bereits oben beschrieben, recht große Dimensionen annehmen.

Zumal die Abfrage recht aufwendig formuliert werden muss, da mir zwar die Kollisionen bekannt sind aber nicht die Richtung etc.

Edit:

Ich habe hier einen Code für Bresenham gefunden, allerdings in C++
Ich bin nicht schlüssig welche Fälle der Code berücksichtigt und auch noch nicht sicher wie man das in PHP umschreibt. Aber vielleicht ist mir das ja schon eine große Hilfe

Code:

void Bresenham(int x1,
    int y1,
    int x2,
    int y2)
{
    signed char ix;
    signed char iy;
 
    // if x1 == x2 or y1 == y2, then it does not matter what we set here
    int delta_x = (x2 > x1?(ix = 1, x2 - x1):(ix = -1, x1 - x2)) << 1;
    int delta_y = (y2 > y1?(iy = 1, y2 - y1):(iy = -1, y1 - y2)) << 1;
 
    plot(x1, y1);
 
    if (delta_x >= delta_y)
    {
        // error may go below zero
        int error = delta_y - (delta_x >> 1);
 
        while (x1 != x2)
        {
            if (error >= 0)
            {
                if (error || (ix > 0))
                {
                    y1 += iy;
                    error -= delta_x;
                }
                // else do nothing
            }
            // else do nothing
 
            x1 += ix;
            error += delta_y;
 
            plot(x1, y1);
        }
    }
    else
    {
        // error may go below zero
        int error = delta_x - (delta_y >> 1);
 
        while (y1 != y2)
        {
            if (error >= 0)
            {
                if (error || (iy > 0))
                {
                    x1 += ix;
                    error -= delta_y;
                }
                // else do nothing
            }
            // else do nothing
 
            y1 += iy;
            error += delta_x;
 
            plot(x1, y1);
        }
    }
}

Quelle: http://roguebasin.roguelikedevelopme...Line_Algorithm

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

03.01.2011, 17:35
AIRMAKZ Neuer Benutzer Registriert seit: 03.01.2011 Beiträge: 8 PHP-Kenntnisse: Fortgeschritten	[Erledigt] PHP Bresenham-Algorithmus für alle Oktanten und m > 1 OR m < -1 Problem gelöst! Siehe: http://www.php.de/php-fortgeschritte...tml#post568598 ([Erledigt] PHP Bresenham-Algorithmus für alle Oktanten und m > 1 OR m < -1) Hallo zusammen! Meine Frage habe ich bereits ausführlich gegooglet und in einer leichten Abwandlung bereits in einem anderem Forum geposted (wo man mir scheinbar nicht helfen wollte oder nicht helfen konnte...zumindest ist nichts draus geworden). Ich formuliere es so kurz wie möglich: Ich habe eine weiße Bilddatei auf der sich zufällige schwarze Pixel befinden. Nun sind zwei Punkte gegeben deren Anordnung ebenfalls zufällig sein kann. X_a kann sich also z.B. rechts von X_b befinden. Für eine lineare Funktion bedeutet dies, dass ich die Punkte a und b also vertauschen müsste. Auf der Strecke zwischen beiden Punkte soll nun überprüft werden, ob sich dort ein schwarzer Pixel befindet (die Abfrage ist kein Problem). Ebenso kann die Steigung m > 1 oder m < -1 sein, was für die lineare Funktion bedeuten würde dass sie nicht mehr alle Punkte auf der Strecke erfasst (Rasterung von Linien). Ich habe in PHP bereits ein ausführliches Script geschrieben, welches alle Fälle für alle Oktankten berücksichtigt: - X_a < X_b -- m >= -1 AND m <= 1 -- m > 1 -- m < 1 - X_a > X_b -- gleiche Fälle wie oben, X_a und X_b werden aber vertauscht - X_a = X_b -- hier wird nur noch unterschieden ob Y_a <> Y_b ist und die Punkte bis zum ,,Ziel" gezählt Wie man sich sicher vorstellen kann, ist meine Lösung äußerst unelegant und ,,frisst" bei starker Belastung viele Serverressourcen. Bei meiner Recherche ist mir allerdings aufgefallen, dass PHP bereits über eine Funktion verfügt die problemlos gerasterte Linien in alle Richtungen zeichnen kann. Ich weiß leider nicht, wie man diese abwandeln könnte dass sie den Zweck einer Kollisionsabfrage erfüllt - denn eine Linie zeichnen möchte ich nicht. Um Ressourcen zu sparen habe ich mich bereits auch kurz mit dem Bresenham-Algorithmus beschäftigt (der sicher von der oben genannten PHP-Funktion benutzt wird). Allerdings sind im Internet nur Beispiele in Java/Pseudo-Code vorhanden, was an sich kein Problem darstellen würde wenn ich die Abwandlungen für alle anderen Oktanten nicht selbst abstrahieren müsste, was zur Folge hat dass der Code wohlmöglich wieder unendlich lang wird. Mein nächstes Problem beschäftigt sich dann noch mit der Berechnung der Länge der Strecke zwischen den beiden Punkten, die man zwar mit dem Satz des Pythagoras berechnen kann aber ebenfalls für alle anderen Oktanten wieder umgeschrieben werden muss. Das letzte Problem beschäftigt sich dann letztendlich noch mit der Richtung in Grad, die mit tan^-1 auch kein Problem darstellt, wenn ich nicht vorher die Abwandlungen gemacht hätte, damit die lineare Funktion überhaupt alle Fälle umfasst. Ihr seht, es handelt sich um ein größeres Problem...meinen Code würde ich auch ehrlich gesagt nur ungern posten. Vielleicht habt ihr ja auf Anhieb einen erleuchtenden Vorschlag. Nochmal kompakte Kurzfassung: Gegeben sind 2 Punkte. Punkt A kann sich rechts von Punkt B befinden. Ich möchte die vollständige Punktmenge der Geraden bestimmen (Rasterung von Linien). Dies soll für alle Fälle möglich sein (egal welche Steigung, egal welche Richtung). Zudem möchte ich die Länge der Strecke berechnen und die Richtung in Grad. Und das alles möglichst kompakt und vor allem ressourcensparend. Ich möchte keine Linie zeichnen! Grüße, Simon Edit: Die Funktion, die ich gerne abwandeln würde heißt imageline. Gibt es nicht eine Möglichkeit die Pixel, die von imageline gezeichnet werden über Arrays auszulesen? z.B. irgendwie P_a[1] = imageline () oder ähnliches? Geändert von AIRMAKZ (04.01.2011 um 16:38 Uhr). Grund: Anordnung der Liste


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

03.01.2011, 18:13
Chriz Moderator Registriert seit: 11.05.2008 Beiträge: 6.268	Hallo, also meine erste Idee war es einfach ein neues Bild zu nehmen, die Linie zu zeichnen (liegt im Speicher, stört ja keinen) und die Punkte dann auszulesen. Nicht performant, aber zumindest korrekt und vor allem flexibel. Weil wie du die Linie zeichnest, mit welcher Seitenstärke, gerade oder gebogen ist dann egal. Mein zweiter Ansatz wäre dann die Linienlänge pixelweise zu verkleinern. Wenn du eine Linie (0/0; 10/10) hast, verkürzt du die Linienlänge von Wurzel(200) immer schrittweise um 10% (da 10=10-0, aber je nach Genauigkeit, ausgehend von der Originallänge) und landest dann (starten von 0/0) eben auf einem deiner gesuchten Pixel (bzw. eher einer Pixelmenge mit Gewichtung). Ich kenn jetzt ehrlich gesagt die Formel nicht mehr dafür (obwohl ichs müsste, da ich letztes Jahr Diagramme mit Imagick gezeichnet hab), aber die sollte sich doch in jedem Matheheftchen finden lassen. Oder ists gerade das was du suchst? Dann stellst du die Frage vielleicht besser in einem Matheforum __________________ "Nuschel ich?" - "Was?"

04.01.2011, 12:17
eagle275 Erfahrener Benutzer Registriert seit: 01.09.2010 Beiträge: 4.561 PHP-Kenntnisse: Fortgeschritten	ich versteh dich so, dass du für jeden Oktanten / Quadranten die Rechenvorschrift separat codierst - das ist aber blödsinn - warum tauschst du nicht einfach "quick and dirty" die Koordinatenwerte der Punkte aus, dann berechnest du das m und gut ist. Wenn ich mich dunkel an meine Assembler-Zeit aufm C64 erinnere blieben am Ende sowieso nur noch 2 Fälle übrig, weil die Optimierung dahin lief, m immer größer oder gleich 1 zu machen (sprich es wurde untersucht ob der X-Abstand oder der Y-Abstand der beiden Punkte größer war und die Schleife nahm immer den längeren "Weg", wenn ich mich recht erinnere - einmal wurde also anhand der y-Koordinate iteriert und beim anderen Pfad anhand der x-Koordinate (warum, siehst du bei Paul und bei mir weiter unten). Alles andere wurde mit dem Koordinatentauschen normalisiert. Anmerkung zu Pauls These .. wenn du IMMER über x-gehst, dann ergibt gleiche X-Koordinate leider eine unendliche Steigung, weil Division durch 0 .... daher die Betrachtung, was der kürzere Weg ist. In meinem Fall wäre der x-Weg kürzer und daher würde m nunmehr als (x_a-x_b) / (y_a-y_b) berechnet .. und eine Steigung von 0 als Abweichung zur Senkrechten ist ja auch verständlich __________________ "Irren ist männlich", sprach der Igel und stieg von der Drahtbürste Geändert von eagle275 (04.01.2011 um 12:22 Uhr).

04.01.2011, 13:51
AIRMAKZ Neuer Benutzer Registriert seit: 03.01.2011 Beiträge: 8 PHP-Kenntnisse: Fortgeschritten	Die Division durch 0 liefert in PHP einen Fehler zurück, deswegen steht auch ein @ vor $m. In der Mathematik sind Berechnungen mit Steigung 0 bei linearen Funktionen problemlos möglich. Die Schleife wird ja trotzdem korrekt durchlaufen. Bisher macht jede Funktion ja in etwa das selbe. Wenn x_a < x_b und m >= -1 AND m <= 1 normale lineare Funktion. Wenn x_a > x_b dann werden die Koordinaten x_a mit x_b und y_a mit y_b vertauscht und die Schleife läuft rückwärts. Damit habe ich 4 Oktankten abgedeckt. Wenn die Steigung allerdings m < -1 OR m > 1 beträgt wird es allerdings etwas komplizierter, weil die Schleife durch y läuft und x mit der linearen Funktion berechnet wird. Theoretisch müsste das alles mit einer Schleife lösbar sein, daran arbeite ich auch derzeit, hab allerdings noch so meine Probleme damit. Mein Ziel ist es, wie bereits gesagt, dass alles möglichst ressourcensparend funktioniert. Deswegen auch nochmal eine Frage am Rande: gibt es eine Möglichkeit die von imageline berechneten Koordinaten aus der Funktion zu extrahieren?

04.01.2011, 14:12
eagle275 Erfahrener Benutzer Registriert seit: 01.09.2010 Beiträge: 4.561 PHP-Kenntnisse: Fortgeschritten	nicht ohne dass du es entsprechend einbaust - und das wird nicht gehen, weil die Funktionen von GD nunmal in einem shared-Object stecken (vergleichbar DLL-Datei) also in binärer Form. Mithin kannst du auch gleich selbst nen Bresenham-Algorithmus bauen, nur eben statt setpixel analysierst du die Farbe des Bildpunktes ( das hast du ja hinbekommen) eventuell hilft da auch noch was anderes ... Kennst du denn die Koordinaten der zufälligen Punkte in der Grafik ? dann kannst du auch direkt mit Berechnungen herausfinden, ob und welche der Punkte auf der Verbindungslinie liegen - ich werd zu hause mal in mein Algorithmen Buch gucken - Robert Sedgewick ein genialer Autor und Professor (MIT) ist zwar Pascal aber leicht in php umzuwandeln. __________________ "Irren ist männlich", sprach der Igel und stieg von der Drahtbürste Geändert von eagle275 (04.01.2011 um 14:21 Uhr).

04.01.2011, 15:07
AIRMAKZ Neuer Benutzer Registriert seit: 03.01.2011 Beiträge: 8 PHP-Kenntnisse: Fortgeschritten	Zuerst wollte ich meinen derzeitigen ,,Algorithmus" so gut wie es geht optimieren, bevor ich mich direkt mit dem Bresenham-Algorithmus beschäftige. Die Koordinaten der Kollisionspunkte kenne ich nicht. Es wäre möglich die Bilder einzulesen und die Punkte in einer Datenbank abzuspeichern...aber die Datenbank-Abfrage wäre bei so vielen Koordinaten bestimmt aufwendiger (von der Rechenleistung her) als das direkte Ansprechen der Bilddatei. Bzw. ich bin mir nicht sicher ob es ressourcenraubender wäre...aber bei einem Kollisionsobjekt von 100x100px sind das schon 2x10.000 Werte in der Datenbank.

04.01.2011, 15:21
eagle275 Erfahrener Benutzer Registriert seit: 01.09.2010 Beiträge: 4.561 PHP-Kenntnisse: Fortgeschritten	nö die Datenbank macht das schon fix - das Problem ist eher das script, das die Bilder mit den Zufallspixeln analysiert - das muss nämlich in einer geschachtelten Schleifenkonstruktion das Bild quasi scannen (von x =0 bis MAX_X und dabe dann jeweils y von 0 bis MAX_Y ) .. das dauert ja ewig - je nach Anzahl der Bilder Da wär es besser du optimierst deinen Algorithmus in Richtung Bresenham - eigentlich bist du gar nicht mehr so weit davon entfernt __________________ "Irren ist männlich", sprach der Igel und stieg von der Drahtbürste