Witam !
Dostałem do rozwiązania następujące zadanie:
W przestrzeni trójwymiarowej zdefiniowany jest zbiór graniastosłupów, o poziomych podstawach, będących wielokątami dowolnymi. Graniastosłupy nie muszą być rozłączne. Dokonać wzajemnego podziału graniastosłupów w kierunku pionowym wzdłuż płaszczyzn zawierających ich ściany boczne (każde dwa graniastosłupy, których rzuty poziome na siebie nachodzą, powinny się wzajemnie rozcinać wzdłuż swoich ścian bocznych, nawet jeśli mają rozłączne zakresy wysokości). Dane wyjściowe powinny być uporządkowane tak, aby dla każdego obszaru na płaszczyźnie poziomej prezentowana była lista zakresów pionowych lezących nad nim graniastosłupów.
Generalnie mam zaproponować kilka metod i dokonać analizy tych metod.
Nie ustaliłem jeszcze dokładnych wymagań odnośnie rozwiązania danego zadania, ale wydaje mi się, że po treści wynika, że mamy do czynienia z graniastosłupami prostymi, których podstawy mogą być dowolnymi wielokątami, także wklęsłymi. Jednak, wydaje mi się, że jeśli mamy te zakresy wysokości, to zadanie sprowadza się do wyznaczenia części wspólnej tych rzutów poziomych graniastosłupów. Prosiłbym o weryfikację mojego pomysłu oraz także o wskazanie przydatnych algorytmów ( znalazłem drzewo BSP jako sugerowany algorytm do rozwiązania tego zadania oraz algorytm Weilera-Athertona do znajdowania części wspólnej wielokątów, ale nie jestem pewien czy to "słuszne" algorytmy do rozwiązania tego problemu).