Kürzeste Verbindung zwischen 2 beliebigen Tabellenfeldern

[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