ENUMERATION ALGORITHM OF 3D FLOORPLAN BASED ON REVERSE SEARCH METHOD
Shohei MATSUKAWA · Journal of Architecture and Planning (Transactions of AIJ) · 2017
A planer graph whose all faces (including the outer faces) are rectangles is called a 2D floor-plan. An algorithm to enumerate 2D floor-plan based on reverse search method has been proposed by Nakano. However, an algorithm to enumerate 3D floor-plan which is consisted of some small cuboids isn't known yet. In this paper, We propose an enumeration algorithm of 3D floor-plan based on reverse search method by extending Nakano's algorithm. A reverse search method is an algorithm to enumerate nodes on spanning tree T with root. If we can define root and parent-child relationship between 3D floor-plans well, we can search the 3D floor-plans by depth-first search on T without knowing T itself. In all spaces of arbitrary 3D floor-plan S, there is only one space with vertex G of which all X, Y, Z coordinates are maximum. We call this space “n-th space”. If we can remove the n-th space by compressing it along X+ or Y+ or Z+ axis direction, we can get a new 3D floor-plan with n-1 spaces as shown Fig. 3. We define the new 3D floor-plan as parent of S. If we repeat removing n-th space, it must be end up with the 3D floor-plan with one space. We call this 3D floor-plan R1 and define it as root. As above, we can define T of 3D floor-plan. In an opposite process, by pushing n-th space to 3D floor-plan, we propose an algorithm to generate all children of 3D floor-plan. By applying this algorithm recursively from R1, we can enumerate 3D floor-plan with n spaces. This algorithm is shown in Fig. 8. More detail of this algorithm are given in chapter 3. By comparing the numbers of 3D floor-plan between our algorithm and algorithms of precedence research, the algorithm in this paper is confirmed appropriate as shown in Table. 1, 2. Also the numbers of 3D floor-plan enumerated by our algorithm are shown in Table. 3. As shown in Fig. 4, there are 3D floor-plan in which it is impossible to remove n-th space. To find an algorithm to enumerate all 3D floor-plan is remained as an open problem.