Drukowana wersja tematu
Forum PHP.pl _ PHP _ Algorytm Bresenham- potrzebuję pomocy.
Napisany przez: miccom 24.01.2022, 08:23:14
Cześć.
Mam taką oto funkcję oparta na algorytmie Bresenhama.
function bresenham(Tile $tileStart, Tile $tileEnd): http://www.php.net/array
{
$x1 = $tileStart->row;
$y1 = $tileStart->column;
$x2 = $tileEnd->row;
$y2 = $tileEnd->column;
$xBegin = $x1;
$yBegin = $y1;
$xEnd = $x2;
$yEnd = $y2;
$dots = [];
$dots[] = [$xBegin, $yBegin];
$steep = http://www.php.net/abs($y2 - $y1) > http://www.php.net/abs($x2 - $x1);
if ($steep) {
$tmp = $x1;
$x1 = $y1;
$y1 = $tmp;
$tmp = $x2;
$x2 = $y2;
$y2 = $tmp;
}
if ($x1 > $x2) {
$tmp = $x1;
$x1 = $x2;
$x2 = $tmp;
$tmp = $y1;
$y1 = $y2;
$y2 = $tmp;
}
$deltax = http://www.php.net/floor($x2 - $x1);
$deltay = http://www.php.net/floor(http://www.php.net/abs($y2 - $y1));
$error = 0;
$deltaerr = $deltay / $deltax;
$y = $y1;
$ystep = ($y1 < $y2) ? 1 : -1;
for ($x = $x1; $x < $x2; $x++) {
$dots[] = $steep ? [$y, $x] : [$x, $y];
$error += $deltaerr;
if ($error >= 0.5) {
$y += $ystep;
$error -= 1;
}
}
$dots[] = [$xEnd, $yEnd];
return $dots;
}
Kod służy do wyznaczania trasy a właściwie do rysowania linii między punktem A a punktem B na układzie współrzędnych.
Jednak nie działa tak jakbym chciał.
Od wskazanego punktu w PRAWO, PRAWA GÓRA, PRAWY DÓŁ odpowiednio pokazuje przejścia przez punkty w układzie współrzędnych.
Ale jeśli wykonuję rysowanie "do tyłu" to pokazuje mi odpowiednie punkty- ale zawsze rosnąco-- co przy rysowaniu w LEWO, LEWO GÓRA i LEWO DÓŁ powinno być na odwrót.
Jak zmodyfikować kod aby pokazywał mi odpowiednie pola?
Już daję przykłady:
Startuję z punktu [34,62]. 3 pól w prawo.
System pokazuje mi poszczególne kroki: route=[[34,62],[34,63],[34,64],[34,65]] i to jest git
Ale jeśli z tego samego punktu chcę rysować linię w lewo to system pokazuje mi punkty: route=[[34,59],[34,60],[34,61],[34,62]]
I same pola są oki- ale jak zmodyfikować kod aby pokazywał mi pola w kolejności malejącej jeśli rysuję w LEWO, LEWO GÓRA, LEWO DÓŁ? route=[[34,62],[34,61],[34,60],[34,59]]
Oto jest pytanie!
Napisany przez: trueblue 24.01.2022, 08:31:18
Odwrócić tablicę?
Ale czy na pewno to jest kwestia pokazanego kodu? Z tego co widzę, jako pierwszy do tablicy wpada właśnie punkt początkowy.
Napisany przez: miccom 24.01.2022, 08:33:44
Cytat(trueblue @ 24.01.2022, 08:31:18 )
Odwrócić tablicę?
Ale czy na pewno to jest kwestia pokazanego kodu? Z tego co widzę, jako pierwszy do tablicy wpada właśnie punkt początkowy.
No tak, i ostatni też wpada właściwie.
Ale te wewnątrz już są uporządkowane rosnąco ( co jest super w ruchu w PRAWO )- ale w LEWO już niekoniecznie
Odwrócić tablicę nie ma problemu- ale skąd system ma wiedzieć kiedy ma odwrócić tablicę a kiedy ma pokazać prawidłową ścieżkę ?
Tego nie potrafię mu przekazać
Napisany przez: trueblue 24.01.2022, 09:04:09
Nie widzę, aby pierwszy i ostatni wpadały właściwie.
Startujesz z [34,62] w lewo o 3 punkty i ten jest ostatni w tablicy, a pierwszy w tablicy jest ostatnim punktem ścieżki.
Wszystkie punkty są w odwrotnej kolejności.
Albo przed wyliczaniem zamień współrzędne, jeśli Y1>Y2.
Albo odwróć kolejność tablicy, jeśli punkt początkowy nie jest pierwszym elementem w tablicy.
Napisany przez: miccom 24.01.2022, 09:33:03
Przy tworzeniu tablicy bez algorytmu wrzucam pierwszy krok (
$dots[] = [$xBegin, $yBegin];
) i ostatni krok (
$dots[] = [$xEnd, $yEnd];
)
Przez to mogą być "nie po kolei".
Jeśli nie dodam tych punktów "ręcznie" to otrzymuję tylko pola pośrednie - co też nie jest złym rozwiązaniem bo dwa pola mogę domyślnie wstawić i też będzie.
Problem jednak jest z tym odwracaniem.
Cytat
Albo przed wyliczaniem zamień współrzędne, jeśli Y1>Y2.
Oki, ale Y'ki mogą być malejące a X'ksy rosnące
Hm.
Nie zrozumiałem co do mnie napisałeś
Napisany przez: trueblue 24.01.2022, 09:59:54
Z tego co widzę, to przy podaniu punktu startowego: 34,62 a końcowego: 34,59, wynikiem jest:
34,62
34,59
34,60
34,61
34,59
a nie to co podałeś w pierwszym poście:
34,59
34,60
34,61
34,62
W zależności od wartości Y1 i Y2 wystarczy wstawić koniec punkt początkowy, albo końcowy.
Nie unikniesz tego, że X1 może być większe od X2 - przecież linia może znaleźć się w każdej ćwiartce układu współrzędnych, a nie tylko w pierwszej, więc nie zawsze X1<X2 i jednocześnie Y1<Y2.
Napisany przez: miccom 24.01.2022, 10:06:23
No tak, pytanie dlaczego się zdublowały dwa elementy 34,59?
Napisany przez: gino 24.01.2022, 10:28:20
trochę to zagmatwane, ze studiów pamiętam, że algorytm Bresenhama jest trochę inny (chyba, że masz to zrobić po swojemu), ale jak Ci się przyda to masz:
Kod
function bresenham(int $x1, int $y1, int $x2, int $y2, bool $route): array
{
$dx = $x2-$x1;
$dy = $y2-$y1;
$e=$dx/2;
$bres = [$x1.';'.$y1];
for ($i=0; $i<$dx; $i++)
{
$x1 += 1;
$e -= $dy;
if($e<=0)
{
$y1 += 1;
$e += $dx;
array_push($bres, $x1.';'.$y1);
}
else
{
array_push($bres, $x1.';'.$y1);
}
}
if($route === true) return $bres;
else
return $bres = array_reverse($bres);
}
print_r(bresenhem(1,1,7,5, true));
print_r(bresenhem(1,1,7,5, false));
oczywiście to wszystko na szybkości, tablica jest na sztywno, kod jaki jest każdy widzi
ale na szybkości i przerobić to tak jak potrzebujesz to pikuś.
edit: ten kod jest dla warunków kiedy odcinek (x1,y1)-(x2,y2) tworzył z osią OX kąt w przedziale od 0 do 45° inne przypadki da się zrobić przez transformacje współrzędnych, ale musisz poczytać, bo dzisiaj nie mam głowy do tego
Napisany przez: miccom 24.01.2022, 10:38:05
Cytat(gino @ 24.01.2022, 10:28:20 )
trochę to zagmatwane, ze studiów pamiętam, że algorytm Bresenhama jest trochę inny (chyba, że masz to zrobić po swojemu), ale jak Ci się przyda to masz:
Generalnie to próbuję ustalić ścieżkę od punktu A do punktu B na układzie współrzędnych.
Mam układ z rozpisanymi wierszami,
Wierszy jest 11, kolumn 25.
I ta takim schemacie chcę ustalić jakie koordynaty znajdują się między polem np. [34,20] a [38,20].
Napisany przez: gino 24.01.2022, 10:48:31
Cytat
Generalnie to próbuję ustalić ścieżkę od punktu A do punktu B na układzie współrzędnych.
No i dobrze. I to opiera się na algorytmie Bresenhama.
Cytat
Mam układ z rozpisanymi wierszami,
Wierszy jest 11, kolumn 25.
A jakie to ma znaczenie ile jest kolumn a ile wierszy? To dalej traktujemy jak układ współrzędnych.
Napisany przez: trueblue 24.01.2022, 10:52:18
Cytat(miccom @ 24.01.2022, 10:06:23 )
No tak, pytanie dlaczego się zdublowały dwa elementy 34,59?
Nie dodawaj do tablicy punktów początkowych i końcowych, wyświetl wynik i dowiesz się.
Napisany przez: trueblue 24.01.2022, 11:09:18
Dla: 30,32 i 10,5, czyli lewo-dół, w tablicy jest punkt [10,5];
Napisany przez: miccom 24.01.2022, 11:25:29
Oki, to zrób symulację [34,62] do [36,60] , u mnie jest startowy ale końcowego nie ma ;/
wynik = [34,62],[35,61]
Jak zrobisz [34,62] do [36,59] to nie ma startowego
wynik = [36,59],[35,60],[35,61]
Jak zrobisz [34,62] do [32,60] to nie ma startowego.
wynik = [32,60],[33,61] i w tym przypadku chciałbym aby tablice były [33,61],[32,60]
Przez to planowąłem dodać ręcznie startowy i końcowy, a gdyby on się zdublował to przez funkcję multi_unique
public function multi_unique($array): http://www.php.net/array
{
foreach ($array as $k=>$na)
$new[$k] = http://www.php.net/serialize($na);
$uniq = http://www.php.net/array_unique($new);
foreach($uniq as $k=>$ser)
$new1[$k] = http://www.php.net/unserialize($ser);
return ($new1);
}
usuwam duplikaty.
I to mw. spełnia moje wymagania- poza faktem że tablice chciałbym odwrócone przy y2 > y1 ale nie wiem jak to zaprogramować ;/
Przed napisaniem postu wykonałem sporą ilości testów, może jeden czy da trafią się prawidłowe- ale przyznasz że to nie tak powinno działać?
Stąd mój post tutaj
Napisany przez: trueblue 24.01.2022, 11:35:26
A ja się odnoszę do tego:
Cytat(miccom @ 24.01.2022, 10:58:08 )
jak dam w lewo dół to nie ma ani początkowego, ani końcowego...
Co nie jest prawdą, zresztą powyżej to potwierdziłeś - albo brak początkowego, albo końcowego.
Problem tkwi w tym, że wstawiasz współrzędne dostarczone na początku algorytmu, pomimo, że algorytm może zamieniać współrzędne początkowe i końcowe.
Wystarczy dodać na końcu:
$dots[] = [$x2, $y2];
Napisany przez: miccom 24.01.2022, 12:56:27
Nie rozumiemy się
Start [34,62]
Meta [34,58]
Wynik: [34,58], [34,59], [34,60], [34,61], [62,34]
Pomijam fakt że ostatni powinien być [34, 62] ścieżka od 34,62 powinna być taka jak w wyniku ( czyli właściwe piksele podano ) ale powinna być odwrócona czyli [34, 62], [34,61], [34,60], [34,59], [34,58] więc algorytm niewłaściwie podstawia dane początkujące i końcowe ;/
Tylko jak się tego nauczyć aby napisać dobry algorytm?
Gdzie szukać pomocy?
Kto mi pomoże ?
Napisany przez: trueblue 24.01.2022, 13:58:42
Dodaj na końcu:
$dots[] = $steep ? [$y2, $x2] : [$x2, $y2];
Odwrócenia możesz dokonać sam, o czym pisałem wcześniej.
Napisany przez: miccom 24.01.2022, 15:12:05
Napisałem że odwrócenie to nie problem, pytanie w jaki sposób poinformować system kiedy należy odwrócić tablicę.
Napisany przez: trueblue 24.01.2022, 15:15:40
Przecież widzisz jaki wynik otrzymujesz - czy punkt początkowy jest na końcu tablicy, czy na początku.
Napisany przez: miccom 24.01.2022, 15:35:01
Dziękuję Trueblue.
No bez ciebie bym nie ogarnął.
Teraz działa ładnie
Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)