Zadanie pochodzi z Mistrzostw Opola w Programowaniu Zespołowym:
Na powierzchni prostopadłościanu o zadanych wymiarach znajdują się 2 punkty, których współrzędne znamy. Punkty te można połączyć drogami leżącymi w całości na powierzchni prostopadłościanu. Znaleźć najkrótszą z tych dróg.
Ma ktoś może pomysł na jakiś algorytm?
[Algorytmy] Odległość punktów na prostopadłościanie
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
Re: [Algorytmy] Odległość punktów na prostopadłościanie
„Rozpłaszcz” bryłę i policz odległość euklidesową na płaszczyźnie. Jeżeli punkty są na sąsiednich ścianach, to jest jeden sposób rozpłaszczenia, jeżeli na przeciwległych, to cztery.
-
- Użytkownik
- Posty: 50
- Rejestracja: 31 gru 2017, o 11:32
- Płeć: Mężczyzna
- Lokalizacja: Bochnia
- Podziękował: 5 razy
- Pomógł: 15 razy
[Algorytmy] Odległość punktów na prostopadłościanie
Tak właśnie na początku zrobiłem, ale okazuje się, że dla sąsiadujących ścian najkrótsza droga wcale nie zawsze prowadzi tylko przez te dwie ściany. Przykładowo:
Wymiary prostopadłościanu to 900 w kierunku osi x, 600 w kierunku y i 300 w kierunku z, a punkty to
(900, 300, 299) i (300, 600, 0). Wówczas pierwszy z tych punktów znajduje się na przedniej ścianie, jeżeli ustawimy oś z do góry, a x w stronę obserwatora, natomiast drugi jest na tej ścianie po prawej stronie, no w zasadzie to na jej krawędzi. Wówczas najkrótsza droga prowadzi przez górną ścianę.
Wymiary prostopadłościanu to 900 w kierunku osi x, 600 w kierunku y i 300 w kierunku z, a punkty to
(900, 300, 299) i (300, 600, 0). Wówczas pierwszy z tych punktów znajduje się na przedniej ścianie, jeżeli ustawimy oś z do góry, a x w stronę obserwatora, natomiast drugi jest na tej ścianie po prawej stronie, no w zasadzie to na jej krawędzi. Wówczas najkrótsza droga prowadzi przez górną ścianę.
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
Re: [Algorytmy] Odległość punktów na prostopadłościanie
Hmm, no ale gdzie jest problem? Jeżeli punkt jest na krawędzi, to musisz rozpatrzyć go dwa razy, więc raz zaliczysz go do ściany po prawej i rozpłaszczysz w prawo, a za drugim razem zaliczysz go do ściany na górze i rozpłaszczysz w górę. W obu przypadkach najkrótsza droga euklidesowa przebiega przez dwie ściany - przednią i prawą/górną.
Nie upieram się, bo być może moja wyobraźnia płata mi figla, ale nie widzę luki. Tak naprawdę możesz zawsze rozpatrzyć wszystkie możliwe siatki prostopadłościanu, rozpłaszczyć je i znaleźć minimum z odległości.
Nie upieram się, bo być może moja wyobraźnia płata mi figla, ale nie widzę luki. Tak naprawdę możesz zawsze rozpatrzyć wszystkie możliwe siatki prostopadłościanu, rozpłaszczyć je i znaleźć minimum z odległości.