[Algorytmy] Odległość punktów na prostopadłościanie

Blazo2000
Użytkownik
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

Post autor: Blazo2000 »

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?
Ostatnio zmieniony 15 sty 2019, o 18:57 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Afish
Moderator
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

Post autor: Afish »

„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.
Blazo2000
Użytkownik
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

Post autor: Blazo2000 »

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

Post autor: Afish »

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