In most applications, such as urbanism and architecture, randomly utilizing given spaces is certainly not favorable. This study proposes an explicit algorithm for utilizing the given spaces inside a rectangle with satisfactory results. In the literature, connectivity is not considered as a criterion for floor plan design, but it is deemed essential in architecture. For example, dining rooms are preferably connected to kitchens, toilets should be connected to many rooms, and each bedroom should be separated from the other rooms. This paper describes adjacency among spaces and proves that the obtained rectangular floor plan is one of the best ones in terms of connectivity. An architectural and mathematical object called extra spaces is introduced by the proposed algorithm and is subsequently examined in this work.
Floor plan ; Extra space ; Algorithm ; Adjacency
The floor plan is the most fundamental architectural diagram. Similar to a map, it is an aerial view of the arrangement of spaces in a building but with focus on the arrangement at a particular level (floor). In architectural terms, an arrangement has two basic elements. The first element is geometry (position). The position of spaces is always considered when organizing them. Examples of geometric arrangements are furniture organized in the most functional way, the famous Rubik׳s Cube, and the arrangement of squares in the golden rectangle. The second essential element is the topology (similarity) of spaces. Elements with similar shapes, reactions, functions, and orientations or directions are often grouped together. For example, noble gases in the periodic table are arranged based on the chemical properties they share. In designing a house, architects place the dining room and kitchen close together. In the context of the present study, a floor plan is an aerial view of the arrangement of spaces and extra spaces (waste spaces) in a building.
Given spaces as well as extra spaces are important in a floor plan. For example, houses require extra spaces, such as storerooms and balconies. Therefore, the problem addressed in this study is establishing a way to arrange a finite collection of rectangular spaces of various sizes inside a rectangular frame in an optimal manner as well as introducing necessary additional space for filling given certain geometric or topological constraints.
The rectangular frame in the aforementioned problem is referred to as a rectangular floor plan denoted by . The given spaces represent the different elements of a building, e.g., rooms, offices, kitchens, bathrooms, and toilets.
An algorithm is a step-by-step procedure or formula that is used to solve a problem. The literature describes several algorithms for constructing floor plans. Galle (1981) proposed an algorithm for generating rectangular plans on modular grids to provide a large number of possible solutions. Lai (1988) used graph theory for floor plan design in a study where the rectangular dualization problem was reduced to a matching problem on bipartite graphs. The dual graph of a plane graph G has a vertex corresponding to each face of G and an edge joining two neighboring faces for each edge in G . A plane graph can be embedded in the plane, i.e., it can be drawn in such a way that no edges cross each other. A plane graph is termed rectangular if each of its edges is oriented in either the horizontal or the vertical direction, each of its regions has exactly four sides, and the whole graph can fit a rectangular enclosure. A bipartite graph is a graph whose vertices can be divided into two independent sets, A and B , such that every edge (a , b ) connects either a vertex from A to B or a vertex from B to A . Stiny (2013) proposed the construction of floor plans using shape grammar. Shape grammar is a procedure for generating different geometric shapes. Terzidis (2007–08) developed a computer program called autoPLAN that generates architectural plans for the boundary and adjacency matrix of a given site.
Since ancient times, architectural forms composed of mathematical and geometrical relationships have generated great interest (Dabbour, 2012 ). In the present study, we propose an algorithm for the construction of a rectangular floor plan and use mathematical tools to prove that the obtained floor plan is optimally connected.
In this section, we provide an algorithm for constructing a rectangular floor plan called the spiral-based rectangular floor plan, which is denoted by . A with n given spaces is termed as of order n and is denoted by .
The golden ratio, one of the keystones of sacred geometry, is related to the Fibonacci sequence, which is a numerical series where the next number is the sum of the previous two numbers (Dabbour, 2012 ). We use the Fibonacci sequence to obtain a “spiral-based sequence” that calculates the width and height of a spiral-based rectangular floor plan. Using this sequence, the width and height of are calculated as follows:
If li and hi are the width and height, respectively, of Ri and if Li and Hi are the width and height, respectively, of , then the spiral-based sequence is given numerically as follows:
Here, L0 =0, and H0 =0.
The concept of a spiral-based sequence is shown in Figure 1 , where the shaded rectangles represent the extra spaces, and the white rectangles represent the given spaces.
Calculating the width and height of a rectangular floor plan.
In Figure 1 (a), i =2. Therefore, we compute L2 and H2 . Here, , and .
In Figure 1 (b), a new space is added to the obtained . Hence, i =3, L3 =L2 +l3 =l2 +l3 , and .
In Figure 1 (c), i =4, , and .
In this algorithm, we draw the given spaces one by one. If the composition of the drawn spaces is rectangular with width Li and height Hi after drawing each space Ri , then we draw the next space. Otherwise, we draw an extra space to obtain a rectangular composition with width Li and height Hi .
Here, we consider three kinds of rectangles. Each type of rectangle is determined by its position, which in turn is determined by the upper left vertex. The size of the rectangle is determined by its width and height.
The first kind of rectangle is the new space Ri drawn at Stage i of the construction process and whose position and size are denoted by and the given pair , respectively. represents a point on a Cartesian plane, as depicted in Figure 2 . The Cartesian plane consists of a set of two perpendicular lines intersecting each other at origin (0,0). The horizontal line is the x -axis, and the vertical line is the y -axis. The location of any point on the Cartesian plane is denoted by an ordered pair (x ,y ), where x is the horizontal distance from the origin, and y is the vertical distance from the origin.
Cartesian plane for the position of rectangles.
The second kind of rectangle is extra space Ei , which may be empty. We denote its position by and its size by the pair . In , an extra space is a rectangle generated by the difference in either the widths or the heights of the spaces.
The last kind of rectangle is the new rectangular composition . Its position also depends on i and is denoted by . The size of is the pair .
The steps for constructing are as follows:
Step 1: All the given spaces are arranged in the order of increasing areas, i.e., we start with the space that has the smallest area; the space with the greatest area is placed last.
Step 2: The process starts with i =0, with all numbers set to 0. The first space is then placed to the left of (0,0). For example, we draw R1 with width l1 and height h1 at position , as shown in Figure 3 .
Placing the first space.
Step 3: R2 is drawn above R1 in such a way that its lower left vertex is the upper left vertex of , as shown in Figure 4 (a).
Placing the second space above the first space.
Given the difference between l1 and l2 , three cases are possible. An extra space is drawn if either l2 >L1 or l2 <L1 because the composition of spaces in both cases is not rectangular. To obtain , an extra space t is drawn, as shown in Figure 4 (b).
In general, if , then , i.e., Ri is drawn to the left of in such a way that its upper right vertex is the upper left vertex of .
If , then , and . An extra space is drawn below Ri and to the left of .
If , then , and . An extra space is drawn below and to the right of Ri .
Step 4: R3 is drawn to the right of in such a way that its upper left vertex is the upper right vertex of .
Placing the third space to the right of the second space.
In general, if , then , i.e., Ri is drawn above in such a way that its lower left vertex is the upper left vertex of .
If , then , and . Here, an extra space is drawn to the right of Ri and above .
If , then , and . Here, an extra space is drawn to the right of and below Ri .
Step 5: R4 is drawn below such that its upper left vertex is the lower left vertex of .
The construction of R4 with an extra space t is shown in Figure 6 . In this figure, l2 =l1 and H2 =h3 are assumed; however, other possible scenarios also exist.
Placing the fourth space below the third space.
In general, if , then , i.e., Ri is drawn to the right of in such a way that its upper left vertex is the upper right vertex of .
If , then , and . Here, an extra space is drawn below Ri and to the right of .
If , then , and . Here, an extra space is drawn below and to the left of Ri .
Step 6: R5 is drawn to the left of in such a way that its upper right vertex is the upper left vertex of .
R5 with an extra space t is shown in Figure 7 . For demonstration purposes, l2 =l1 , H2 =h3 , and L3 =l4 are taken into consideration, but other possible cases also exist.
Placing the fifth space to the left of the fourth space.
In general, if , then , i.e., Ri is drawn below in such a way that its upper left vertex is the lower left vertex of .
If , then , and . Here, an extra space is drawn to the right of Ri and below .
If , then , and . Here, an extra space is drawn to the right of and above Ri .
Step 7: Repeat Steps 3–6 until all the spaces are arranged.
The steps of this algorithm clearly show that the spaces are arranged along a spiral, hence the name “spiral-based algorithm.” For an enhanced understanding of this algorithm, we use the following example. Consider five different spaces with the following widths and heights:
BR – bedroom (3×4), KIT – kitchen (6×4), BA – bathroom (2×3), WC (1.5×1.5), and LR – living room (5×8).
Step-by-step construction of a spiral-based rectangular floor plan for the given spaces.
In a rectangular floor plan, an extra space adjacent to the outside is considered a terrace; otherwise, it is a circulation. A terrace is an outdoor living space or a storeroom, and a circulation refers to the way people move through and interact within a house. The circulations and terraces are marked in Figure 8 . In this figure, the extra spaces in some sub-figures have been initially considered as terraces, but they have been marked subsequently as circulations.
Seven additional spiral-based rectangular floor plans can be obtained by slightly changing the spiral-based algorithm (Section 2.2 ) as follows:
Seven different spiral-based rectangular floor plans.
A wall is one side of a rectangle. If W is a wall with side length j , a sub-wall of W is a properly connected part of W . Hence, a closed interval of length k is strictly included in W , i.e., 0<k <j . Two rectangles are adjacent if they share a wall or a sub-wall. Figure 10 illustrates the concept of adjacency for rectangles A and B. In Figure 10 (a) and (c), A and B share a wall; in Figure 10 (b), A and B share a sub-wall; in Figure 10 (d), A and B share neither a wall nor a sub-wall. Hence, in Figure 10 , A is adjacent to B in cases a, b, and c but not in case d.
Four cases that define adjacency among rectangles.
The adjacency graph of a rectangular floor plan is a simple undirected graph obtained by representing each space as a vertex and then drawing an edge between any two vertices if the corresponding spaces are adjacent (Gross, 2006 ). The adjacency graph of the spiral-based rectangular floor plans obtained in Figure 8 ; Figure 9 is shown in Figure 11 .
Graph of the eight spiral-based rectangular floor plans.
The degree of connectivity of a rectangular floor plan is defined by the adjacency among the different spaces and is given in terms of the connectivity of the corresponding adjacency graph. Therefore, the connectivities of different rectangular floor plans are compared based on the connectivities of the corresponding adjacency graphs.
Several measures can be used to compare the connectivity of two graphs (Rodrigue et al., 2006 ). In this study, we consider the number of edges as a measure of connectivity. If two connected adjacency graphs have the same number of vertices, then the adjacency graph with many edges is considered to be closely connected.
Let n be the number of spaces in a rectangular floor plan or the number of vertices in the corresponding graph. For a , the number of edges in the corresponding graph when n >3 is equal to 3n –7 ( Shekhawat, 2013 ; Theorem 3.13); this theorem has been proven mathematically. In Figure 10 , n =5; hence, the number of edges is equal to 3n –7=3×5–7=8. For any , the number of edges in the corresponding graph when n >3 is always less than 3n −6 ( Shekhawat, 2013 ; Theorem 3.24); this theorem has also been proven mathematically.
Based on the results above, we can deduce that any graph of a rectangular floor plan cannot have more than 3n –7 edges and that the graph of a spiral-based rectangular floor plan has exactly 3n –7 edges. Therefore, the spiral-based rectangular floor plan is one of the best rectangular floor plans in terms of connectivity.
A spiral-based rectangular floor plan starts from the smallest space, i.e., the smallest space is always at the center of a floor plan. In a house, toilets are among the smallest spaces, and users want these rooms to be in the center and connected to a maximum number of spaces. Moreover, the position of extra spaces indicates the position of the doors.
In this work, we constructed eight different spiral-based rectangular floor plans that offer a number of choices to users. The results revealed that spiral-based rectangular floor plans are the best in terms of connectivity. For our future work, we can use the concept of spiral-based rectangular floor plans to construct other floor plans of different shapes.
A number of extra spaces are known to exist in a rectangular floor plan. As far as applications are concerned, extra spaces are valuable, but their sizes must be reduced. In the future, we will find methods for reducing the sizes of extra spaces to maintain connectivity and the number of extra spaces.