Witaj Gościu! ( Zaloguj | Rejestruj )

Forum PHP.pl

 
Reply to this topicStart new topic
> Algorytm Bresenham- potrzebuję pomocy.
miccom
post 24.01.2022, 08:23:14
Post #1





Grupa: Zarejestrowani
Postów: 493
Pomógł: 8
Dołączył: 7.07.2007
Skąd: Tychy

Ostrzeżenie: (0%)
-----


Cześć.
Mam taką oto funkcję oparta na algorytmie Bresenhama.

  1. function bresenham(Tile $tileStart, Tile $tileEnd): Array
  2. {
  3.  
  4. $x1 = $tileStart->row;
  5. $y1 = $tileStart->column;
  6.  
  7. $x2 = $tileEnd->row;
  8. $y2 = $tileEnd->column;
  9.  
  10. $xBegin = $x1;
  11. $yBegin = $y1;
  12. $xEnd = $x2;
  13. $yEnd = $y2;
  14. $dots = [];
  15. $dots[] = [$xBegin, $yBegin];
  16. $steep = abs($y2 - $y1) > abs($x2 - $x1);
  17.  
  18. if ($steep) {
  19. $tmp = $x1;
  20. $x1 = $y1;
  21. $y1 = $tmp;
  22. $tmp = $x2;
  23. $x2 = $y2;
  24. $y2 = $tmp;
  25. }
  26.  
  27. if ($x1 > $x2) {
  28. $tmp = $x1;
  29. $x1 = $x2;
  30. $x2 = $tmp;
  31. $tmp = $y1;
  32. $y1 = $y2;
  33. $y2 = $tmp;
  34. }
  35. $deltax = floor($x2 - $x1);
  36. $deltay = floor(abs($y2 - $y1));
  37. $error = 0;
  38. $deltaerr = $deltay / $deltax;
  39. $y = $y1;
  40. $ystep = ($y1 < $y2) ? 1 : -1;
  41.  
  42. for ($x = $x1; $x < $x2; $x++) {
  43. $dots[] = $steep ? [$y, $x] : [$x, $y];
  44. $error += $deltaerr;
  45. if ($error >= 0.5) {
  46. $y += $ystep;
  47. $error -= 1;
  48. }
  49. }
  50. $dots[] = [$xEnd, $yEnd];
  51.  
  52. return $dots;
  53. }


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 smile.gif

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!

Ten post edytował miccom 24.01.2022, 08:24:24


--------------------
Jeśli pomogłem- kliknij POMÓGŁ-przyda się ;)- jeśli piszę bzdury- pisz pod postami. Poprawię się.
PISZĘ POPRAWNIE PO POLSKU!
Go to the top of the page
+Quote Post
trueblue
post 24.01.2022, 08:31:18
Post #2





Grupa: Zarejestrowani
Postów: 6 761
Pomógł: 1822
Dołączył: 11.03.2014

Ostrzeżenie: (0%)
-----


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.


--------------------
Go to the top of the page
+Quote Post
miccom
post 24.01.2022, 08:33:44
Post #3





Grupa: Zarejestrowani
Postów: 493
Pomógł: 8
Dołączył: 7.07.2007
Skąd: Tychy

Ostrzeżenie: (0%)
-----


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 sad.gif

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ć sad.gif


--------------------
Jeśli pomogłem- kliknij POMÓGŁ-przyda się ;)- jeśli piszę bzdury- pisz pod postami. Poprawię się.
PISZĘ POPRAWNIE PO POLSKU!
Go to the top of the page
+Quote Post
trueblue
post 24.01.2022, 09:04:09
Post #4





Grupa: Zarejestrowani
Postów: 6 761
Pomógł: 1822
Dołączył: 11.03.2014

Ostrzeżenie: (0%)
-----


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.


--------------------
Go to the top of the page
+Quote Post
miccom
post 24.01.2022, 09:33:03
Post #5





Grupa: Zarejestrowani
Postów: 493
Pomógł: 8
Dołączył: 7.07.2007
Skąd: Tychy

Ostrzeżenie: (0%)
-----


Przy tworzeniu tablicy bez algorytmu wrzucam pierwszy krok (
  1. $dots[] = [$xBegin, $yBegin];
) i ostatni krok (
  1. $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 sad.gif

Hm.
Nie zrozumiałem co do mnie napisałeś sad.gif


--------------------
Jeśli pomogłem- kliknij POMÓGŁ-przyda się ;)- jeśli piszę bzdury- pisz pod postami. Poprawię się.
PISZĘ POPRAWNIE PO POLSKU!
Go to the top of the page
+Quote Post
trueblue
post 24.01.2022, 09:59:54
Post #6





Grupa: Zarejestrowani
Postów: 6 761
Pomógł: 1822
Dołączył: 11.03.2014

Ostrzeżenie: (0%)
-----


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.


--------------------
Go to the top of the page
+Quote Post
miccom
post 24.01.2022, 10:06:23
Post #7





Grupa: Zarejestrowani
Postów: 493
Pomógł: 8
Dołączył: 7.07.2007
Skąd: Tychy

Ostrzeżenie: (0%)
-----


No tak, pytanie dlaczego się zdublowały dwa elementy 34,59?


--------------------
Jeśli pomogłem- kliknij POMÓGŁ-przyda się ;)- jeśli piszę bzdury- pisz pod postami. Poprawię się.
PISZĘ POPRAWNIE PO POLSKU!
Go to the top of the page
+Quote Post
gino
post 24.01.2022, 10:28:20
Post #8





Grupa: Zarejestrowani
Postów: 319
Pomógł: 52
Dołączył: 18.02.2008

Ostrzeżenie: (0%)
-----


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 smile.gif 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

Ten post edytował gino 24.01.2022, 10:32:44
Go to the top of the page
+Quote Post
miccom
post 24.01.2022, 10:38:05
Post #9





Grupa: Zarejestrowani
Postów: 493
Pomógł: 8
Dołączył: 7.07.2007
Skąd: Tychy

Ostrzeżenie: (0%)
-----


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].



--------------------
Jeśli pomogłem- kliknij POMÓGŁ-przyda się ;)- jeśli piszę bzdury- pisz pod postami. Poprawię się.
PISZĘ POPRAWNIE PO POLSKU!
Go to the top of the page
+Quote Post
gino
post 24.01.2022, 10:48:31
Post #10





Grupa: Zarejestrowani
Postów: 319
Pomógł: 52
Dołączył: 18.02.2008

Ostrzeżenie: (0%)
-----


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.
Go to the top of the page
+Quote Post
trueblue
post 24.01.2022, 10:52:18
Post #11





Grupa: Zarejestrowani
Postów: 6 761
Pomógł: 1822
Dołączył: 11.03.2014

Ostrzeżenie: (0%)
-----


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ę.


--------------------
Go to the top of the page
+Quote Post
miccom
post 24.01.2022, 10:58:08
Post #12





Grupa: Zarejestrowani
Postów: 493
Pomógł: 8
Dołączył: 7.07.2007
Skąd: Tychy

Ostrzeżenie: (0%)
-----


Tak, doszedłem do tego.
Ale jeśli nie dodam ich- to albo są- albo ich nie ma i nie wiem dlaczego sad.gif

Jak dam linie w PRAWO to jest punkt początkowy i końcowy, ale w lewo jest już tylko końcowy ( bez początkowego ), jak dam w lewo dół to nie ma ani początkowego, ani końcowego...
Coś ten algorytm nie działa smile.gif ( mówię o kodzie który wkleiłem, bo algorytm Breshenhama na pewno działa:) ) sad.gif



--------------------
Jeśli pomogłem- kliknij POMÓGŁ-przyda się ;)- jeśli piszę bzdury- pisz pod postami. Poprawię się.
PISZĘ POPRAWNIE PO POLSKU!
Go to the top of the page
+Quote Post
trueblue
post 24.01.2022, 11:09:18
Post #13





Grupa: Zarejestrowani
Postów: 6 761
Pomógł: 1822
Dołączył: 11.03.2014

Ostrzeżenie: (0%)
-----


Dla: 30,32 i 10,5, czyli lewo-dół, w tablicy jest punkt [10,5];


--------------------
Go to the top of the page
+Quote Post
miccom
post 24.01.2022, 11:25:29
Post #14





Grupa: Zarejestrowani
Postów: 493
Pomógł: 8
Dołączył: 7.07.2007
Skąd: Tychy

Ostrzeżenie: (0%)
-----


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

  1. public function multi_unique($array): Array
  2. {
  3. foreach ($array as $k=>$na)
  4. $new[$k] = serialize($na);
  5. $uniq = array_unique($new);
  6. foreach($uniq as $k=>$ser)
  7. $new1[$k] = unserialize($ser);
  8. return ($new1);
  9. }
  10.  
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 smile.gif


--------------------
Jeśli pomogłem- kliknij POMÓGŁ-przyda się ;)- jeśli piszę bzdury- pisz pod postami. Poprawię się.
PISZĘ POPRAWNIE PO POLSKU!
Go to the top of the page
+Quote Post
trueblue
post 24.01.2022, 11:35:26
Post #15





Grupa: Zarejestrowani
Postów: 6 761
Pomógł: 1822
Dołączył: 11.03.2014

Ostrzeżenie: (0%)
-----


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:
  1. $dots[] = [$x2, $y2];



--------------------
Go to the top of the page
+Quote Post
miccom
post 24.01.2022, 12:56:27
Post #16





Grupa: Zarejestrowani
Postów: 493
Pomógł: 8
Dołączył: 7.07.2007
Skąd: Tychy

Ostrzeżenie: (0%)
-----


Nie rozumiemy się sad.gif

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 ?

Ten post edytował miccom 24.01.2022, 13:02:08


--------------------
Jeśli pomogłem- kliknij POMÓGŁ-przyda się ;)- jeśli piszę bzdury- pisz pod postami. Poprawię się.
PISZĘ POPRAWNIE PO POLSKU!
Go to the top of the page
+Quote Post
trueblue
post 24.01.2022, 13:58:42
Post #17





Grupa: Zarejestrowani
Postów: 6 761
Pomógł: 1822
Dołączył: 11.03.2014

Ostrzeżenie: (0%)
-----


Dodaj na końcu:
  1. $dots[] = $steep ? [$y2, $x2] : [$x2, $y2];


Odwrócenia możesz dokonać sam, o czym pisałem wcześniej.


--------------------
Go to the top of the page
+Quote Post
miccom
post 24.01.2022, 15:12:05
Post #18





Grupa: Zarejestrowani
Postów: 493
Pomógł: 8
Dołączył: 7.07.2007
Skąd: Tychy

Ostrzeżenie: (0%)
-----


Napisałem że odwrócenie to nie problem, pytanie w jaki sposób poinformować system kiedy należy odwrócić tablicę.


--------------------
Jeśli pomogłem- kliknij POMÓGŁ-przyda się ;)- jeśli piszę bzdury- pisz pod postami. Poprawię się.
PISZĘ POPRAWNIE PO POLSKU!
Go to the top of the page
+Quote Post
trueblue
post 24.01.2022, 15:15:40
Post #19





Grupa: Zarejestrowani
Postów: 6 761
Pomógł: 1822
Dołączył: 11.03.2014

Ostrzeżenie: (0%)
-----


Przecież widzisz jaki wynik otrzymujesz - czy punkt początkowy jest na końcu tablicy, czy na początku.


--------------------
Go to the top of the page
+Quote Post
miccom
post 24.01.2022, 15:35:01
Post #20





Grupa: Zarejestrowani
Postów: 493
Pomógł: 8
Dołączył: 7.07.2007
Skąd: Tychy

Ostrzeżenie: (0%)
-----


Dziękuję Trueblue.

No bez ciebie bym nie ogarnął.

Teraz działa ładnie smile.gif


--------------------
Jeśli pomogłem- kliknij POMÓGŁ-przyda się ;)- jeśli piszę bzdury- pisz pod postami. Poprawię się.
PISZĘ POPRAWNIE PO POLSKU!
Go to the top of the page
+Quote Post

Reply to this topicStart new topic
1 Użytkowników czyta ten temat (1 Gości i 0 Anonimowych użytkowników)
0 Zarejestrowanych:

 



RSS Wersja Lo-Fi Aktualny czas: 28.03.2024 - 11:09