[Algorytmy] Podział graniastosłupów w kierunku pionowym

[xyz_zyx]

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

[Afish]

Może jakiś rysunek? Co w sytuacji gdy jeden graniastosłup jest wewnątrz drugiego?

[xyz_zyx]

Przyznam się szczerze, że jeszcze od prowadzącego nie otrzymałem odpowiedzi na to pytanie (oczywiście je zadałem). Moim zdaniem, w treści jest dość wyraźnie napisane, że interesują nas tylko cięcia pionowe, więc odpadają niby te cięcia przechodzące wzdłuż podstaw (czyli w Twoim przypadku otrzymalibyśmy ten "mniejszy" graniastosłup, ale o wysokości tego graniastosłupa, w którym się zawiera). Oczywiście, wydaje mi się to dość ułomne, dlatego jutro o to się dopytam.-- 6 gru 2016, o 22:08 --Po spotkaniu z prowadzącym projekt, wychodzi na to, jak myślałem czyli ten problem sprowadza się do znalezienia części wspólnej rzutów poziomych (czyli podstaw) poszczególnych graniastosłupów. W przypadku cięć naszych graniastosłupów, bierzemy tylko te pionowe cięcia, a jakby rolę tych poziomych cięć przejmą te zakresy wysokości dla poszczególnych obszarów.
Na omawianych przykładzie:
Oznaczenia:
a - wysokość, na jakiej zaczyna się mały sześcian
b - wysokość, na której kończy się mały sześcian
c - wysokość dużego sześcianu
Powiedzmy, że mamy jeden większy sześcian (który załóżmy że leży na naszej płaszczyźnie poziomej) oraz mniejszy sześcian, który jest w tym dużym (jest jakoś w nim zawieszony, jest nad płaszczyzną poziomą). Znajdujemy część wspólną ich rzutów poziomych i dokonujemy podziału wzdłuż ścian bocznych tego małego. I gdy po dokonaniu tego podziału, patrząc od góry i traktując te sześciany jako przezroczyste, najedziemy na obszar odpowiadający tego małemu sześcianowi to powinno nam się pokazać informacja, że na tym obszarze mamy 3 zakresy wysokości: od 0 do a; od a do b; od b do c. To nam wskazuje, że dla obszaru odpowiadającego podstawie małego sześcianu, przestrzeń została podzielona na 3 części.

Oczywiście, przepraszam za ten zbyt nienaukowy opis przedstawienia tego przykładu, ale szczerze mówiąc prowadzący przedstawił mi to po prostu wizualnie i ruchowo, więc łatwiej to wtedy było zrozumieć.

O co bym prosił, to prostu o podanie algorytmów, które pomogłyby mi do wyznaczenia części wspólnej dowolnej dwóch dowolnych wielokątów (także wklęsłych).