Przybliżanie linii prostej na siatce heksagonalnej

Holden22 · Post autor: **Holden22** » 4 sie 2015, o 16:36

Cześć wszystkim, mam oryginalny problem.

Mam siatkę heksagonalną. Wybieram dowolne dwa pola (nazywane A i B) i łączę je odcinkiem. Teraz muszę znaleźć, przez które pola siatki heksagonalnej ta linia będzie przebiegać, innymi słowy muszę wybrać pola, które będą najlepszym przybliżeniem tego odcinka.
[Problem powstał w procesie tworzenia gry planszowej - gra jest oparta na siatce heksagonalnej, a w tej grze m. in. strzela się z łuku - musimy wiedzieć, przez które pola przeleci strzała]

Przykłady na rysunku:

Od lewej, pierwszy wybór jest trywialny, dlatego, że można bezpośrednio połączyć te dwa pola linią prostą.
Środkowy przykład również jest prosty, przybliżając linię prostą należy wybrać którekolwiek z zielonych pól, nie ma znaczenia które - oba są tak samo dobre.
Przykład po prawej już jest trudny. Punkty A i B są daleko od siebie, odcinek je łączący nie przechodzi przez osie symetrii sześcianów, bez precyzyjnych pomiarów nie wiadomo które pola są przecinane przez odcinek a które nie, etc.

Potrzebuję znaleźć metodę, dzięki której można jednoznacznie, szybko, łatwo, na papierze, bez narzędzi, wyznaczyć "czerwone" pola, dla dowolnych A i B. Czy macie jakieś pomysły? Czy to w ogóle da się zrobić? Jak się do tego zabrać?

Pozdrawiam serdecznie; będę wdzięczny za wszelkie wskazówki.

Medea 2 · Post autor: **Medea 2** » 4 sie 2015, o 21:57

Pierwsza myśl: połącz punkty linią i pomaluj na czerwono (chociaż możesz nawet na żółto i na niebiesko) te pola, które odcinają dużą część sześcianu. Dlaczego chcesz wyznaczać to na papierze? Nie możesz użyć jakiegoś przybliżenia? No tak, chodzi o grę planszową.

Ewentualnie możesz wskazać najkrótszą ścieżkę (w tym przypadku: siedem w dół, dwa w prawo-dół) i "stabularyzować" wyniki. Co prawda wtedy gra nie będzie wymagała żadnego dodatkowego narzędzia, tylko opasłej knigi opisującej mechanikę

Poczytaj o

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

.

Holden22 · Post autor: **Holden22** » 4 sie 2015, o 22:45

Bresenham line algorithm to brzmi jak dokładnie coś, co próbuję zrobić! - tylko że potrzebuję to zrobić bez komputera, na kartce papieru, i w prosty i szybki sposób (bez obliczeń matematycznych).

Jasne, wskazanie najkrótszej ścieżki jest proste, można łatwo policzyć liczbę pól, ale tor lecącej strzały musi być jak najbardziej linią prostą. No i wybór odpowiednich pól musi być jednoznaczny.

Medea 2 · Post autor: **Medea 2** » 4 sie 2015, o 22:51

W takim razie... ja się poddaję. Powiem na zakończenie, że dla sześciokątów też algorytm istnieje, ale... Zresztą, sam zobacz.

Kod: Zaznacz cały

http://zvold.blogspot.com/2010/01/bresenhams-line-drawing-algorithm-on_26.html

Holden22 · Post autor: **Holden22** » 4 sie 2015, o 23:01

Dzięki za naprowadzenie na ten algorytm, nigdy o nim nie słyszałem wcześniej, a może się okazać pomocny!