Koordinaten von Hexagonen < Topologie+Geometrie < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:02 Di 04.12.2012 | | Autor: | JaykopX |
Ich habe ein Hexagonfeld angelegt: ![[]](/images/popup.gif) Skizze. Nun möchte ich den Abstand in Koordinaten für 2 gegebene Hexagonen Herausfinden. Dabei haben alle 6 Nachbarn[(0, -1); (1, -1); (1, 0); (1, 1); (0, 1); (-1, 0)] den Abstand 1 zum Hexagon (0, 0). Alle äußeren Nachbarn von genannten 6 Nachbarn haben den Abstand 2 zum Hexagon (0, 0), usw.
Wie berechne ich nun für zwei Hexagonen mit den Koordinaten [mm] (x_1, y_2), (x_1, y_2) [/mm] den Abstand?
Ich habe schon gemerkt, dass die Wahl des Koordinatensystems für dieses Problem nicht optimal ist, weil ich zwischen einer geraden und ungeraden Reihe unterscheiden muss, jedoch bietet das Koordinatensystem bei andernen Problemen Vorteile, weshalb ich es auch beibehalten möchte. Jemand einen Algorithmus/Formel parat?
Eine Konvertierungsformel von "meinen" Koordinatensystem in ein Koordinatensystem mit x- und y-Achse jeweils Parallell zur Kante eines Hexagons würde auch schon reichen.
Achtung: Die Maße in der Skizze sind nicht die eines Hexagons. Die Seiten eines Hexagons sind alle gleichlang und die Innenwinkel sind jeweils 120°!
Danke!
|
|
| |
|
> Ich habe ein Hexagonfeld angelegt:
> Skizze.
> Nun möchte ich den Abstand in Koordinaten für 2 gegebene
> Hexagonen Herausfinden. Dabei haben alle 6 Nachbarn[(0,
> -1); (1, -1); (1, 0); (1, 1); (0, 1); (-1, 0)] den Abstand
> 1 zum Hexagon (0, 0). Alle äußeren Nachbarn von genannten
> 6 Nachbarn haben den Abstand 2 zum Hexagon (0, 0), usw.
>
> Wie berechne ich nun für zwei Hexagonen mit den
> Koordinaten [mm](x_1, y_2), (x_1, y_2)[/mm] den Abstand?
>
> Ich habe schon gemerkt, dass die Wahl des
> Koordinatensystems für dieses Problem nicht optimal ist,
> weil ich zwischen einer geraden und ungeraden Reihe
> unterscheiden muss, jedoch bietet das Koordinatensystem bei
> andernen Problemen Vorteile, weshalb ich es auch
> beibehalten möchte. Jemand einen Algorithmus/Formel
> parat?
> Eine Konvertierungsformel von "meinen" Koordinatensystem
> in ein Koordinatensystem mit x- und y-Achse jeweils
> Parallell zur Kante eines Hexagons würde auch schon
> reichen.
>
> Danke!
Hallo JaykopX,
da du ein "normales" x-y-Koordinatensystem einführen
möchtest, würde ich vorschlagen, die ganzzahligen
"Hexagonalkoordinaten" mit u und v zu bezeichnen.
Ich musste die Skizze etwas genauer betrachten, um
nachzuvollziehen, wie diese Hexagonalkoordinaten zu
verstehen sind.
Schließlich bin ich auf folgende Umrechnungsformeln
gekommen:
1.) Umrechnung von (u,v) zu (x,y) :
$\ y:=\ [mm] -\,\frac{\sqrt{3}}{2}*v$
[/mm]
$\ x:=\ [mm] \begin{cases} u\ , & \mbox{falls } v\ \mbox{ gerade} \\ u-\frac{1}{2}\ , & \mbox{falls } v\ \mbox{ ungerade} \end{cases}$
[/mm]
2.) Umrechnung von (x,y) zu (u,v) :
$\ v:=\ [mm] -\,\frac{2}{\sqrt{3}}*y$
[/mm]
$\ u:=\ [mm] \begin{cases} x\ , & \mbox{falls } v\ \mbox{ gerade} \\ x+\frac{1}{2}\ , & \mbox{falls } v\ \mbox{ ungerade} \end{cases}$
[/mm]
Hast du nun also zwei Hexagone mit den Koordinaten
[mm] (u_1,v_1) [/mm] und [mm] (u_2,v_2) [/mm] , so rechnest du von diesen zunächst
zu [mm] (x_1,y_1) [/mm] und [mm] (x_2,y_2) [/mm] um und berechnest dann die
Distanz d mittels Pythagoras:
$\ d:=\ [mm] \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$
[/mm]
LG, Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:39 Mi 05.12.2012 | | Autor: | JaykopX |
Danke für die Antwort.
Leider liefert die Formel nicht das Ergebnis was ich haben wollte.
z.B. für u1(0, 0) und v1(2,1) sollte d=2 das Ergebnis sein,
die Formel liefert aber ~1,73.
u2(0, 0) und v2(3, 1) sollte d=3 sein ich bekomme aber ~2,65.
Nun habe ich es nicht mit weiteren Werten getestet, aber vieleicht reicht es schon zu runden, könnte aber sein das bei hohen abständen Falsche Ergebnisse entstehen. Ich denke auf jedenfall nochmal drüber nach und freue mich auf Feedback.
|
|
|
| |
|
> Danke für die Antwort.
> Leider liefert die Formel nicht das Ergebnis was ich haben
> wollte.
> z.B. für u1(0, 0) und v1(2,1) sollte d=2 das Ergebnis
> sein,
> die Formel liefert aber ~1,73.
> u2(0, 0) und v2(3, 1) sollte d=3 sein ich bekomme aber
> ~2,65.
>
> Nun habe ich es nicht mit weiteren Werten getestet, aber
> vieleicht reicht es schon zu runden, könnte aber sein das
> bei hohen abständen Falsche Ergebnisse entstehen. Ich
> denke auf jedenfall nochmal drüber nach und freue mich auf
> Feedback.
Hallo JaykopX,
ich weiß nicht, wie du bei deinen Beispielen auf die
Distanzen 2 bzw. 3 kommst.
Ich habe die Sechsecke als regelmäßige Sechsecke
aufgefasst. Eigentlich müssen wir ja nur die Mittel-
punkte der kleinen "Fliesen" betrachten. Diese bilden,
wenn man benachbarte Punkte verbindet, ein Gitter mit
Maschen in der Form von gleichseitigen Dreiecken der
Seitenlänge 1 . Ein solches Dreieck hat die Höhe [mm] h=\frac{\sqrt{3}}{2} [/mm] .
In deiner Skizze sieht es allerdings so aus, als ob die
Sechsecke nicht regelmäßig sein könnten - sie erscheinen
etwas zu schmal und zu hoch im Vergleich zu regelmäßigen
Sechsecken.
Was soll nun gelten ?
Du kannst ja mal nach deinem Konzept etwa die
x-y-Koordinaten deines Punktes mit u=3 und v=1
berechnen.
Nach meiner Rechnung komme ich auf $\ x=2.5$ und [mm] y=-\frac{\sqrt{3}}{2}
[/mm]
und dann eben auf die Distanz zum Nullpunkt von
[mm] \sqrt{7}\approx [/mm] 2.646
LG, Al-Chw.
|
|
|
| |
|
Hallo,
ich merke gerade noch, dass ein anderer Grund hinter
der Diskrepanz unserer Ergebnisse liegen könnte.
Was meinst du eigentlich mit der "Distanz" zweier
Fliesen (-Mittelpunkte) ?
Ich habe die Frage so aufgefasst, dass du die "echte"
euklidische Distanz meinst, welche man als die Länge
der geradlinigen Verbindungsstrecke zwischen den
Fliesenmittelpunkten bekommt.
Dein Hexagonfeld gleicht aber einem Spielbrett -
und deshalb meinst du vielleicht mit "Distanz" gar
nicht die euklidische Distanz, sondern so etwas
wie die Anzahl der Schritte (von einem Spielfeld
zu einem benachbarten Spielfeld), die du mit einer
Spielfigur mindestens machen musst, um von einem
Feld A zu einem anderen Feld b zu kommen.
Wenn es so gemeint war, braucht man natürlich
andere Ideen, um "Distanzen" zu berechnen.
LG, Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:00 Mi 05.12.2012 | | Autor: | JaykopX |
Ja, ich bin nicht auf der suche nach den echten Distanzen. Ich habe im Eingangspost von Abständen in Koordinaten gesprochen, damit meine ich den "Radius" der immer größer werdenen "Ringe" aus Hexagonen um einen Punkt. Im nullten Ring(Abstand 0) befindet sich 1 Hexagon, im ersten Ring(Abstand 1) sind 6 Hexagonen(Nachbarn des Hexagon aus Ring 1). Der zweite Ring(Abstand 2) hat 12 Hexagonen(äußeren Nachbarn des Ring 1), usw.. Auf dieser Skizze sind das jeweils die Hexagonen, die von den blauen Kreisen geschnitten werden.
Das heißt der Abstand kann nur ganzzahlig sein und es ist glaube ich sogar die minimal benötigte Anzahl der Schritte über die Kanten von einem Startfeld zu einem Endfeld.
|
|
|
| |
|
> Ja, ich bin nicht auf der suche nach den echten Distanzen.
> Ich habe im Eingangspost von Abständen in Koordinaten
> gesprochen, damit meine ich den "Radius" der immer größer
> werdenen "Ringe" aus Hexagonen um einen Punkt. Im nullten
> Ring(Abstand 0) befindet sich 1 Hexagon, im ersten
> Ring(Abstand 1) sind 6 Hexagonen(Nachbarn des Hexagon aus
> Ring 1). Der zweite Ring(Abstand 2) hat 12
> Hexagonen(äußeren Nachbarn des Ring 1), usw.. Auf dieser
> Skizze
> sind das jeweils die Hexagonen, die von den blauen Kreisen
> geschnitten werden.
>
> Das heißt der Abstand kann nur ganzzahlig sein und es ist
> glaube ich sogar die minimal benötigte Anzahl der Schritte
> über die Kanten von einem Startfeld zu einem Endfeld.
Naja, das mit diesen "Kreisen" ist schon ein bisschen problematisch.
Für gewisse genügend kleine Radien stimmt es zwar noch, dass
man jeweils durch alle Felder, die von (0/0) aus die gleiche
"Distanz" haben, auch einen Kreis legen kann, der sie alle
durchquert. Für größere "Distanzen" werden aber diese "Kreise"
eben immer "hexagonaler" und entfernen sich deutlich
von der Form eines wirklichen Kreises.
Du hast hier eine Art "Taxi-Metrik", aber eben nicht für
ein "Manhattan" mit quadratischen Blöcken, sondern für
eine Stadt mit einem Straßennetz in Form eines Dreiecksgitters.
Ich war schon dran, eine rechnerische Lösung zu ent-
werfen, muss dabei aber noch einen kleinen Fehler
(möglicherweise Rundungsproblem) beheben.
LG, Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:24 Mi 05.12.2012 | | Autor: | JaykopX |
Ich habe mir überlegt wie ich das mit dem Pythagoras vereinen kann.
Der kleinste Schritt horizontal wäre [mm] d_H=\bruch{3}{2*\wurzel{3}}= cos(30^\circ), [/mm] und der Kleinste Schritt vertikal wäre [mm] d_V=\bruch{3}{2}=3*sin(30^\circ). [/mm] Damit hätten die Nachbarn in Ring 1 die Koordinaten: [mm] (\pm d_H, \pm d_V); (\pm d_H, [/mm] 0). Und der Pythagoras für diese Koordinaten würde immer denselben Abstand [mm] d=\wurzel{3} [/mm] liefern.
|
|
|
| |
|
> Ja, ich bin nicht auf der suche nach den echten Distanzen.
> Ich habe im Eingangspost von Abständen in Koordinaten
> gesprochen, damit meine ich den "Radius" der immer größer
> werdenen "Ringe" aus Hexagonen um einen Punkt. Im nullten
> Ring(Abstand 0) befindet sich 1 Hexagon, im ersten
> Ring(Abstand 1) sind 6 Hexagonen(Nachbarn des Hexagon aus
> Ring 1). Der zweite Ring(Abstand 2) hat 12
> Hexagonen(äußeren Nachbarn des Ring 1), usw.. Auf dieser
> Skizze
> sind das jeweils die Hexagonen, die von den blauen Kreisen
> geschnitten werden.
>
> Das heißt der Abstand kann nur ganzzahlig sein und es ist
> glaube ich sogar die minimal benötigte Anzahl der Schritte
> über die Kanten von einem Startfeld zu einem Endfeld.
Hallo Jaykop,
ich habe nun meinen vorherigen kleinen Fehler (in
einem Programm für den TI Voyage 200) noch gefunden
und korrigiert.
Ich will das Prinzip der Berechnung erläutern:
II.) Wie man aus deinen (u,v) - Koordinaten eines
Feldes die kartesischen (x,y) - Koordinaten berechnen
kann, habe ich vorher schon erklärt.
Das Ergebnis ist stets ein (x,y) - Koordinatenpaar eines
Gitterpunktes in dem Gitter mit gleichseitigen
Dreiecken der Seitenlänge 1 als "Maschen".
II.) Nun betrachten wir die 3 Vektoren
[mm] $\vec{e}\ [/mm] =\ [mm] \pmat{1\\0}\qquad\vec{f}\ [/mm] =\ [mm] \pmat{\frac{1}{2}\\\frac{\sqrt{3}}{2}}\qquad\vec{g}\ [/mm] =\ [mm] \pmat{-\,\frac{1}{2}\\\frac{\sqrt{3}}{2}}$
[/mm]
Je 2 von ihnen können als Basisvektoren dienen, um das
Dreiecksnetz aufzuspannen.
Nun zerlegen wir den (kartesischen) Vektor [mm] \pmat{x\\y}
[/mm]
auf drei verschiedene Arten in Linearkombinationen,
nämlich:
1.) [mm] $\pmat{x\\y}\ [/mm] =\ [mm] \alpha*\vec{e}+\beta*\vec{f}$
[/mm]
2.) [mm] $\pmat{x\\y}\ [/mm] =\ [mm] \gamma*\vec{e}+\delta*\vec{g}$ [/mm]
3.) [mm] $\pmat{x\\y}\ [/mm] =\ [mm] \varepsilon*\vec{f}+\theta*\vec{g}$
[/mm]
Die Faktoren [mm] \alpha [/mm] , [mm] \beta [/mm] , .... , [mm] \theta [/mm] werden natürlich
stets ganzzahlig. Ihre Beträge geben an, wie viele Schritte
man jeweils in einer bestimmten Richtung gehen muss.
Die gesuchte "Hexa-Taxi-Distanz" d ist dann gegeben durch
[mm] $\mbox{\red{\LARGE{d\ :=\ \ \ min\,(\ |\alpha|\,+\,|\beta|\ ,\ |\gamma|\,+\,|\delta|\ ,\ |\varepsilon|\,+\,|\theta|\ )}}}$
[/mm]
Das sieht jetzt natürlich etwas kompliziert aus - aber sobald
es in ein Programm gepackt ist, muss das einen ja nicht
mehr kümmern.
Jedenfalls funktioniert jetzt mein entsprechendes Programm.
Ich denke aber, dass sich schon noch einiges ver-
einfachen bzw. zusammenfassen liesse.
LG und schönen Abend !
Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 02:58 Do 06.12.2012 | | Autor: | JaykopX |
Hallo und danke erstmal für deine Mühe.
Ich tue mich schwer mit der Lösung. Deshalb Schritt für Schritt:
1.) Ich berechne die kartesischen Koordinaten [mm] (x_{1, 2} [/mm] und [mm] y_{1, 2}) [/mm] für beide Hexagon koordinaten [mm] (u_{1,2} [/mm] und [mm] v_{1, 2}).
[/mm]
2.) Ich bilde den Differnezvektor von x und.
3.) Ich Zerlege den Diffrenzvektor und erhalte 6 Gleichungen mit 6 Unbekannten?
4.) Ich löse nach den Unbekannten [mm] (\alpha, \beta, [/mm] ...) auf.
5.) Ich bestimme d.
Ich habe auch an einer Lösung gearbeitet und mit c++ Umgesetz.
Sie funktioniert auch ein Einblick hier: Code. Wie man meine Lösung mathematisch formulieren könnte, mal sehen ob ich das noch mache, vieleicht schaut ja jemand drüber und macht es.
|
|
|
| |
|
> Hallo und danke erstmal für deine Mühe.
>
> Ich tue mich schwer mit der Lösung. Deshalb Schritt für
> Schritt:
> 1.) Ich berechne die kartesischen Koordinaten [mm](x_{1, 2}[/mm]
> und [mm]y_{1, 2})[/mm] für beide Hexagon koordinaten [mm](u_{1,2}[/mm] und
> [mm]v_{1, 2}).[/mm]
> 2.) Ich bilde den Differenzvektor von x und.
> 3.) Ich Zerlege den Differenzvektor und erhalte 6
> Gleichungen mit 6 Unbekannten?
> 4.) Ich löse nach den Unbekannten [mm](\alpha, \beta,[/mm] ...)
> auf.
> 5.) Ich bestimme d.
Zu Punkt 3:
Man bekommt natürlich nicht ein großes System mit 6
Unbekannten, sondern 3 kleine 2x2 - Systemchen, die
man z.B. mittels inversen Matrizen leicht lösen kann.
Ist zum Beispiel
[mm] $\pmat{x\\y}\ [/mm] =\ [mm] \alpha*\vec{e}+\ \beta*\vec{f}\ [/mm] =\ [mm] \alpha*\pmat{1\\0}+\ \beta*\pmat{\frac{1}{2}\\ \frac{\sqrt{3}}{2}}$
[/mm]
so erhält man:
[mm] $\alpha\ [/mm] =\ x-c*y$ und [mm] $\beta\ [/mm] =\ 2*c*y$
wobei $\ c\ =\ [mm] \frac{1}{\sqrt{3}}$
[/mm]
LG Al-Chw.
|
|
|
| |
|
Hallo JaykopX,
zum Schluss jetzt noch eine Bemerkung zu deinem
ursprünglichen Koordinatensystem. In deiner Zeichnung
liegen jeweils die Fliesen (u,v) zu einem gegebenen
konstanten Wert v auf waagrechten Linien.
Alle Fliesen mit einem gegebenen u-Wert liegen
aber nicht auf einer Geraden, sondern auf einer
Zickzack-Linie.
Das machte die Umrechnung zu gewöhnlichen kartesischen
Koordinaten etwas umständlich.
Einfacher wäre alles gewesen, wenn du dich gleich
entschlossen hättest, die Fliesen mit gegebenem
konstantem u-Wert auf eine Gerade zu legen. Diese
würde dann halt mit der Waagrechten einen 60°-Winkel
bilden, was dir wohl nicht so recht geheuer erschien ...
Mit einem solchen schiefwinkligen Koordinatensystem
würden die ganzen Rechnungen ganz erheblich
einfacher !
Und jetzt noch eine Frage zum Sinn des Ganzen:
Für welchen Zweck (ich vermute ein Brettspiel)
brauchst du denn die Berechnungen ?
LG, Al-Chw.
|
|
|
| |
|
Wenn man anstatt des "Zickzack-Systems" zur Beschreibung
der Koordinaten der Spielfelder einfach ein schiefwinkliges,
aber im Übrigen "normales" (lineares !) (u,v) - Koordina-
tensystem nimmt (seine beiden Basisvektoren [mm] \vec{e} [/mm] und [mm] \vec{f} [/mm] sind
Einheitsvektoren, nur bilden sie nicht wie im üblichen
kartesischen System einen rechten Winkel, sondern
einen 60° - Winkel), so wird die Berechnung von
"Hexagonal-Distanzen" ganz einfach.
Zunächst kann man aus den (u,v) - Koordinaten von
Anfangs- und Endpunkt den Verbindungsvektor
einfach als Differenzvektor berechnen (diese Eigenschaft
hat das Zickzack-System eben nicht !).
Dann kann man dem resultierenden Vektor seine
"Hex-Länge" so zuordnen:
$\ d(u,v)\ =\ [mm] min(\,|u|+|v|\ [/mm] ,\ |u+v|+|u|\ ,\ [mm] |u+v|+|v|\,)$
[/mm]
Also: Ade Pythagoras und Ade Quadratwurzeln !
Schlichte Betragsbestimmungen genügen.
Die Felder des "innersten Rings" um die (0,0) - Fliese
herum, also jene, die von dieser die Distanz 1 haben,
sind:
(1,0) , (0,1) , (-1,1) , (-1,0) , (0,-1) , (1,-1)
Einige Punkte mit "Distanz" 2 von (0,0) sind etwa:
(2,0) , (1,1) , (0,2) , (-1,2) , (-2,2) , (-2,1) , (-2,0) (etc.)
LG
Al-Chwarizmi
|
|
|
|
