Na płaszczyźnie dany jest zbiór prostokątów współosiowych (przeszkód) (prostokąty współosiowe są równoległe do jakiejś prostej). Chcemy możliwie efektywnie wyznaczać ścieżki łączące zadane pary punktów i nie kolidujące z prostokątami. Kryteria jakości dotyczące ścieżek to długość i liczba załamań. Jakieś pomysły?
Starałem się wykorzystać metodę zamiatania powierzchni ale nie wiem co dokładnie mam w niej sprawdzać/zapamiętywać...
A nie wystarczy Dijkstra z założeniem że waga "prostej" ścieżki jest np. 1 a waga załamanej 2?
x (rogi prostokątów oraz punkty startowy i docelowy) , usuwasz duplikaty, sortujesz je, dokładnie pomiędzy każdą sąsiednia parą wstawiasz dodatkowy.y.x,y z powyższych dwóch list która staje się węzłami grafu.Jeżeli chcesz "chodzić" również po przekątnej to trzeba podkorygować algorytm.
_13th_Dragon mozesz troche rozpisac swoj pomysl zeby troche rozjasnic??
Co rozumiesz przez "worzysz siatkę z x,y z powyższych dwóch list która staje się węzłami grafu."? Że element z najmniejszym x łączę z elementem o najmniejszym y?
czy dany x z kazdym y?
Masz listę X oraz listę Y. Listę punktów tworzysz na zasadzie każdy x z każdym y
"dokładnie pomiędzy każdą sąsiednia parą wstawiasz dodatkowy" - pomiędzy już posortowane punkty?
W jakim celu te punkty połówkowe? A co jeśli wstawi 2 punkty pomiędzy?
Zrób z połówkowaniem, jak program będzie gotów to zakomentujesz ten jeden wiersz i zobaczysz różnicę, za długo opisywać.
Możesz nawet 100 wsadzić ale złożoność wzrasta kwadratowo.
Nie tworzą się wtedy schodki?