Abstand im hexagonalen Gitter

Jo1_a88223 · 12. Februar 2008 um 18:47

Hallo,

ich habe ein hexagonales Gitter des Typs „EastWest“, also wo die Reihen durchgängig sind und die ungeraden Reihen um kartesischen Koordinatensystem versetzt sind. Hier ein Beispiel für ein 5x5-Gitter:

(0,0) (1,0) (2,0) (3,0) (4,0)
 (0,1) (1,1) (2,1) (3,1) (4,1)
(0,2) (1,2) (2,2) (3,2) (4,2)
 (0,3) (1,3) (2,3) (3,3) (4,3)
(0,4) (1,4) (2,4) (3,4) (4,4)

Nur zum Verständnis: die Zelle (2,2) hat die Nachbarn (1,1),(2,1),(3,2),(2,3),(1,3),(1,2).

Nach meiner ersten Überraschung, dss das Problem nicht so trivial ist und nach meiner zweiten Überraschung, dass ich auch im Netz nichts hilfreiches finden kann, hier die Frage:

Wie berechne ich (möglichst einfach und schnell!) den Abstand zweier gegebener Zellen im Hexagonalen Gitter?

Beisp: Der Abstand zw. (0,0) und (3,2) ist 4 Zellen.

Danke schonmal!

LG
Jochen

Sebastian_Schmidt · 13. Februar 2008 um 11:20

Hallo.

ich habe ein hexagonales Gitter des Typs „EastWest“, also wo
die Reihen durchgängig sind und die ungeraden Reihen um
kartesischen Koordinatensystem versetzt sind. Hier ein
Beispiel für ein 5x5-Gitter:

(0,0) (1,0) (2,0) (3,0) (4,0)
(0,1) (1,1) (2,1) (3,1) (4,1)
(0,2) (1,2) (2,2) (3,2) (4,2)
(0,3) (1,3) (2,3) (3,3) (4,3)
(0,4) (1,4) (2,4) (3,4) (4,4)

Nach meiner ersten Überraschung, dss das Problem nicht so
trivial ist und nach meiner zweiten Überraschung, dass ich
auch im Netz nichts hilfreiches finden kann, hier die Frage:

Wie berechne ich (möglichst einfach und schnell!) den Abstand
zweier gegebener Zellen im Hexagonalen Gitter?

Wenn ich das richtig sehe, sollte es so gehen:
Punkte sind (x1, y1) und (x2, y2).
dx = |x2-x1|
dy = |y2-y1|

d = dy + max(dx - floor(dy/2), 0)

floor soll dabei eine Funktion zum Abrunden sein.

Das beruht auf der Beobachtung, dass für jeweils 2 Zeilen die Spalte ohne zusätzliche „Kosten“ um 1 geändert werden kann.

Beisp: Der Abstand zw. (0,0) und (3,2) ist 4 Zellen.

dx = 3
dy = 2
d = 2 + max(3 - floor(4/2), 0) = 4

Sebastian.

Jo1_a88223 · 13. Februar 2008 um 16:00

Hallo,

Danke für die Antwort.

Leider stimmt die Lösung nicht.
Sie passt für gerade Zeilen des Endpunktes und dann auch nur, wenn der Startpunkt links/oben liegt.

LG
Jochen

Jo1_a88223 · 13. Februar 2008 um 18:32

Hallo,

ich habe inzwischen eine Lösung gefunden. Ich muss 5 Fälle unterscheiden und muss die Information über die „Oddity“ beider Zeilen (von Start- UND Ziel-Zelle) berücksichtigen, dann klappt das.

LG
Jochen

Sebastian_Schmidt · 13. Februar 2008 um 19:30

Hallo.

Leider stimmt die Lösung nicht.
Sie passt für gerade Zeilen des Endpunktes und dann auch nur,
wenn der Startpunkt links/oben liegt.

Sicher?
Mal ein Beispiel mit ungeraden Zeilen:
P1 = (4,5), P2 = (3, 1)

dx = |x2-x1| = |4-7| = 3
dy = |y2-y1| = |1-5| = 4

d = dy + max(dx - floor(dy/2), 0)
d = 3 + max (3 - floor(4/2), 0) = 4

Oh, ich sehe gerade, es geht vermutlich schief, wenn ein Punkt auf einer geraden Zeile und einer auf der ungeraden ist:
P1 = (4,5), P2 = (3, 0)

dx = |x2-x1| = |4-7| = 3
dy = |y2-y1| = |0-5| = 5

d = dy + max(dx - floor(dy/2), 0)
d = 3 + max (3 - floor(5/2), 0) = 4

Man könnte die Formel so modifizieren:

d = dy + max(dx - floor(dy/2), 0) + dy mod 2
oder
d = dy + max(dx - floor(dy/2), 0) + (y1 + y2) mod 2
mod soll dabei für modulo stehen, also den Rest der Division.

Sebastian.

Ralf_f02edf · 13. Februar 2008 um 20:32

Wenn Du …
(Hi Jo…)

… die Lösung hier kurz vorstellen würdest, dann

(1) würde ich mich freuen, weil mich das interessiert,

(2) würden sich die anderen Leser und Denker dieses Threads sicherlich auch freuen, und

(3) hätte der nächste, der „im Netz“ nach einer Antwort auf dieses Problem googelt, ein Erfogserlebnis.

Also, laß’ hören

Gruß,
Ralf

Jo1_a88223 · 14. Februar 2008 um 15:57

Hi Ralf,

ich wagte nicht zu glauben, dass das tatsächlich noch irgendwen interessieren würde… sorry.

Natürlich hast Du recht, daher hier meine Lösung in Pseudocode:

 dy = Zielreihe - Startreihe
 dx = Zielspalte - Startspalte

 Wenn (Startreihe ungerade) und (Zielreihe gerade) dann 
 {
 verringere dx um 1
 }

 Wenn (|2dx| Startspalte) dann
 {
 Wenn (dy \> 0) dann
 {
 Ergebnis = dx + dy - dy div 2
 }
 Sonst
 {
 Ergebnis = dx - dy + dy div 2 
 }
 } 
 Sonst
 {
 Wenn (dyi\>0) dann
 {
 Ergebnis = -dx + dy - (dy+1) div 2
 }
 Sonst
 {
 Ergebnis = -dx - dy + (dy-1) div 2
 }
 }
 }

Die Funktion ‚a div b‘ meint den Ganzzahligen Anteil der Division a:b.

Ich hoffe, es ist mit diesen verschachtelten Wenn-Danns auch für Nichtprogrammierer noch verständlich.

LG
Jochen

Jo1_a88223 · 14. Februar 2008 um 16:00

Hallo,

Ich habe den neuen Lösungsvorschlag ausprobiert. Auch der funktioniert nicht. Ich habe übrigends inzwischen eine funktionierende Lösung, die ich Ralf oben im Thread gepostet habe.

Wenn Du aber eine elegantere/schnellere Lösung findest - nur zu! - ich bin gespannt.

LG
Jochen

Sebastian_Schmidt · 14. Februar 2008 um 17:17

Hallo.

Ich habe den neuen Lösungsvorschlag ausprobiert. Auch der
funktioniert nicht.

Hm, kannst du mir mal ein Beispiel geben, wo was falsches rauskommt. Ich stehe gerade offenbar irgendwie auf dem Schlauch, ich finde nämlich kein solches.

Ich habe übrigends inzwischen eine
funktionierende Lösung, die ich Ralf oben im Thread gepostet
habe.

Wenn Du aber eine elegantere/schnellere Lösung findest - nur
zu! - ich bin gespannt.

Ich denk nochmal ein bisschen drüber nach, irgendwie muss das ja hinzubekommen sein.

Sebastian.

Sebastian_Schmidt · 18. Februar 2008 um 11:12

Hallo.

So, jetzt habe ich eine Lösung gefunden. Glaube ich zumindest.
Zuersteinmal nummeriere ich die Felder anders. Ich nenne das Koordinatenpaar mal (a, b). Es gibt ja sechs Richtungen, in die man von einem Feld aus zum nächsten gelangen kann, diese 6 Felder haben folgende Koordinaten:
rechts: (a+1, b)
rechts unten: (a+1, b+1)
links unten: (a, b+1)
links: (a-1, b)
links oben: (a-1, b-1)
rechts oben: (a, b-1)

Dazu kommt dann die Betrachtung, wie der kürzeste Weg zwischen 2 Feldern aufgebaut sein muss.
Es ist offenbar am günstigsten, nur 2 der 3 möglichen Bewegungsrichtungen zu verwenden, um von einem zum anderen Punkt zu gelangen. Die 3 Bewegungsrichtungen bezeichne ich mit a-Achse (nur a ändert sich), b-Achse (nur b ändert sich) und ab-Achse (a und b ändert sich gleichmäßig).
Dann hat man folgende 3 Möglichkeiten, von einem Punkt zum anderen zu gelangen:

Bewegungen entlang der a-Achse und b-Achse
Bewegungen entlang der ab-Achse und der a-Achse
Bewegungen entlang der ab-Achse und der b-Achse

Der Startpunkt sei (a1, b1), der Zielpunkt (a2, b2). Das ist gleichbedeutend mit dem Abstand zwischen (0, 0) und (da, db), wobei da = a2-a1 und db = b2-b1. Mit diesen Koordinaten rechne ich im folgenden
Berechnen wir die Abstände für jede der 3 Möglichkeiten:

Offenbar müssen a und b auf 0 gebracht werden, daher:
d1 = |a| + |b|
a muss auf den Wert von b gebracht werden und dann beide gleichzeitig auf 0. Daher:
d2 = |b-a| + |b|
Analog zu 2. ist das dann d3 = |b-a| + |a|
Der kürzeste Abstand ist dann das Minimum dieser 3 Möglichkeiten, also
d = min(|a| + |b|, |b-a| + |a|, |b-a| + |b|)
d = min(|a| + |b|, |b-a| + min(|a|, |b|))

Jetzt braucht man nur noch eine Möglichkeit, um (a, b) aus den (x, y)-Koordinaten zu berechnen.
Offenbar ist b = y.
Für a gilt in den geraden Zeilen:
a = x + y/2
In den ungeraden Zeilen:
a = x + (y+1)/2
Zusammengefasst also: a = x + (y+1) div 2 (div sei die Ganzzahldivision)

Das sollte jetzt eigentlich hinkommen, kannst du ja mal ausprobieren.

Sebastian.

Ralf_f02edf · 18. Februar 2008 um 13:10

Danke owT