Kürzeste Verbindung zwischen 2 beliebigen Tabellenfeldern

[Niko]

Hallo Zusammen!

Folgendes Problem:

Ich habe eine beliebig große Tabelle, der Einfachheit halber gehe ich hier mal von 4x4 Feldern aus. Die einzelnen Felder haben je eine eindeutige X- und Y-Koordinate.

Wenn ich nun ein Start und ein Zielfeld gegeben habe, möchte ich die auf direktem Weg dazwischenliegenden Felder (bzw deren Koordinaten)ermitteln.

Soweit kein Problem, sofern Start- und Zielfeld auf einer Höhe oder auf einer Horizontalen liegen. Auch wenn sie genau im 45° Winkel zueinander stehen sind die auf der Verbindungsgerade liegenden Felder leicht zu bestimmen.

Schwer wird es bei außerhalb dieser Spezialfälle liegenden Start- und Zielpunkten.

Als Verdeutlichung hier eine kleine Skizze:
http://neff.alfahosting.org/publicstuff/tabelle.png

Die farbigen S und Z Felder sind die Start- und Zielfelder, die rosa Pfeile stellen die direkte Verbindung dar und die grauen Pfeile markieren die dazugehörigen Felder, die ich gerne ermitteln würde.

Ich dachte an die Verwendung von Winkelfunktionen in Kombination mit dem Satz von Pythagoras, wobei sich allerdings einige Probleme ergeben:

-Division durch Null bei bestimmten Winkeln, dabei handelt es sich aber um die oben genannten Spezialfälle, die auch anders lösbar sind.
-Lücken zwischen den ermittelten Feldern wegen Rundungsfehlern
-2 Felder auf gleicher Höhe bevor ein neues Feld kommt.

Mit einigen geschickt gestrickten Bedingungen sollte man alle diese Probleme bewältigen können, aber momentan fehlt mir dazu noch ein konkreter Ansatz.

Generell erschient mir dieser Weg sehr aufwändig und mit vielen Unannehmlichkeiten und ausnahmen behaftet zu sein.

Kennt jemand eine elegantere Lösung oder kann mir einen JS Ansatz zu meinem Weg zeigen.
Vielen Dank schonmal im Vorraus.

[Der Martin]

Moin Niko,

Ich habe eine beliebig große Tabelle [...] Wenn ich nun ein Start und ein Zielfeld gegeben habe, möchte ich die auf direktem Weg dazwischenliegenden Felder (bzw deren Koordinaten)ermitteln.

diese Aufgabenstellung ähnelt verdammt stark dem Algorithmus zum Zeichnen von Linien in einem Pixelraster.

Soweit kein Problem, sofern Start- und Zielfeld auf einer Höhe oder auf einer Horizontalen liegen. Auch wenn sie genau im 45° Winkel zueinander stehen sind die auf der Verbindungsgerade liegenden Felder leicht zu bestimmen.

Das sind Sonderfälle, die man eigentlich gar nicht gesondert betrachten muss.

Schwer wird es bei außerhalb dieser Spezialfälle liegenden Start- und Zielpunkten.

Nein. ;-)

Ich dachte an die Verwendung von Winkelfunktionen in Kombination mit dem Satz von Pythagoras, wobei sich allerdings einige Probleme ergeben:

Zusätzlich zu den von dir erwähnten mathematischen Problemen ergibt sich ein hoher Bedarf an CPU-Leistung durch die eifrige Verwendung von Multiplikationen, Divisionen und trigonometrischen Funktionen, die meist als Reihenentwicklung implementiert sind (auch in den FPUs).

Generell erschient mir dieser Weg sehr aufwändig und mit vielen Unannehmlichkeiten und ausnahmen behaftet zu sein.

Sag' ich doch. ;-)

Kennt jemand eine elegantere Lösung oder kann mir einen JS Ansatz zu meinem Weg zeigen.

Ich kann dir mal in Pseudocode meine Version aufzeigen, mit der ich vor vielen Jahren den DrawLine-Algorithmus für eine VGA-Grafikbibliothek realisiert habe. Das Teil war schneller als so manche kommerzielle Lösung, weil es nur am Anfang je eine Division für x und y brauchte und während des Ablaufs nur Additionen verwendete. Wenn man diese Rechnung jetzt noch in Integer-Festpunktarithmetik macht und dafür sorgt, dass der Nachkomma-Anteil deutlich mehr Bits hat als für die maximale x- oder y-Strecke nötig ist, sind auch Rundungsfehler noch kein Thema. Damals war 1024x768 die höchste Auflösung, die überhaupt in Frage kam, und ich hatte mich dann für 16bit als Nachkommaanteil entschieden. Das war reichlich, aber gut handhabbar (8bit wäre zu wenig gewesen).
Dadurch war auch eine Optimierung für die Sonderfälle (senkrechte, waagrechte oder 45°-Linie) vollkommen überflüssig. Start- und Zielpunkt seien (x1,y1) und x2,y2):

dx = x2-x1               Abstand in x-Richtung
   dy = y2-y1               Abstand in y-Richtung
   s = max(dx,dy)           Ermittle den größeren der beiden Werte
                            s ist damit die Anzahl zu zeichnender Pixel
   dx = dx/s                Ermittle Schrittweite in x-Richtung
   dy = dy/s                und in y-Richtung
   while (s)                Schleife über s Schritte
    { SetPixel(x1,y1)       ein Pixel bei (x1,y1) zeichnen
      x1 = x1+dx            x-Koordinate um ermittelte Schrittweite erhöhen
      y1 = y1+dy            dito für y
      s--                   Schleifenzähler abwärts zählen
    }
   SetPixel(x2,y2)          letztes Pixel zeichnen

Vielleicht kannst du aus diesem Ansatz was machen ...

So long,
 Martin

[Niko]

diese Aufgabenstellung ähnelt verdammt stark dem Algorithmus zum Zeichnen von Linien in einem Pixelraster.

Daran dachte ich auch, nur ist mir keine so elegante und kurze Beschreibung dafür eingefallen :D

Schwer wird es bei außerhalb dieser Spezialfälle liegenden Start- und Zielpunkten.

Nein. ;-)

Sehr gut!

Vielleicht kannst du aus diesem Ansatz was machen ...

Ja, das hilft mir ungemein, Danke. Nur was genau macht die max() Funktion und was gibt sie zurück?

[Der Martin]

Hallo Niko,

Vielleicht kannst du aus diesem Ansatz was machen ...
Ja, das hilft mir ungemein, Danke. Nur was genau macht die max() Funktion und was gibt sie zurück?

ging das aus dem Kommentar in dieser Zeile nicht hervor? In manchen Programmiersprachen gibt es die max()-Funktion, die das Maximum der übergebenen Argumente zurückgibt. Das meinte ich mit "Ermittle den größeren der beiden Werte".
In Javascript gibt es AFAIK eine solche Funktion nicht, also müsste man sie sich selbst basteln. Der Fragezeichen-Operator eignet sich prima dafür. So gibt etwa der Ausdruck

(a>b ? a : b)

elegant formuliert den größeren der beiden Werte a und b zurück.

Ciao,
 Martin

[Niko]

(a>b ? a : b)

Damit kann ich was anfangen, dankesehr.

[Timo "God's Boss" Reitz]

max()
In Javascript gibt es AFAIK eine solche Funktion nicht, also müsste man sie sich selbst basteln.

Doch, gibt es: http://de.selfhtml.org/javascript/objekte/math.htm#max@title=Math.max

[JürgenB]

Hallo Niko,

ich glaube, du suchst die Manhattan Norm. Siehe z.B. http://en.wikipedia.org/wiki/Norm_(mathematics).

Um sie zu bestimmen, zählst du die waagrechten und die senkrechten Schritte zusammen.

Gruß, Jürgen