Potrzebuję metody dzielenia przestrzeni 3D na losowe kształty pól wyrównanych do osi. Na razie obecnie dzielę przestrzeń 2d na potrzeby testowania. Najbardziej natychmiastowe podejście, jakie wymyśliłem, to zdefiniowanie prostokąta o rozmiarze (1, 1), a następnie rekurencyjne podzielenie wszystkich istniejących prostokątów na dwa nierówne prostokąty na przemian między osią X i Y.
Problem tutaj jest oczywisty. Takie podejście skutkuje długimi liniami rozciągania (zaznaczonymi na czerwono)
To, co chciałbym, to coś bardziej organicznego (podałem przykład)
Zobacz, żadnych długich prostych linii od góry do dołu lub od lewej do prawej.
Jedynym ograniczeniem jest to, że mogę chcieć ograniczyć minimalny rozmiar prostokąta bez wpływu na ziarnistość rozmiarów. tzn. jeśli najmniejszy prostokąt ma 1 centymetr kwadratowy, to w sekundach najmniejsze pomieszczenie nie powinno wynosić 2 jednostek kwadratowych.
Idealnie więc algorytm powinien spełniać wszystkie trzy następujące ograniczenia:
- Prostokąty nie są nieskończenie małe.
- Rozmiary prostokątów nie są dyskretnym pomnożeniem najmniejszego rozmiaru prostokąta. tzn. jeśli najmniejszy rekt ma 3 jednostki kwadratowe niż większe rekt nie są ograniczone do 6, 9, 12 itd. jednostek kwadratowych, a zamiast tego mogą wynosić 3,2 lub 4,7 w tym przypadku).
- Algorytm działa w czasie wielomianowym (wymaga szybkiego obliczenia).