Algorithm for constructing an optimally connected rectangular floor plan

Published Date
Received 10 October 2013, Revised 5 December 2013, Accepted 18 December 2013, Available online 4 July 2014.

Author
Krishnendra Shekhawat. Author links open the author workspace.Opens the author workspaceOpens the author workspace

Department of Mathematics, University of Geneva, Geneva 1211, Switzerland

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

1. Introduction

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 $R^F$. 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.

2. Constructing a rectangular floor plan

In this section, we provide an algorithm for constructing a rectangular floor plan called the spiral-based rectangular floor plan, which is denoted by $R_S^F$. A $R_S^F$ with n given spaces is termed as $R_S^F$ of order n and is denoted by $R_S^F(n)$.

2.1. Spiral-based sequence

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 $R_S^F$ are calculated as follows:

a)

For odd i, i.e., after drawing the 1st, 3rd, … spaces, the width of the obtained rectangular floor plan $R_S^F(i)$ is the sum of the widths of $R_S^F(i-1)$ and the ith space Ri, and the height of $R_S^F(i)$ is the sum of the maximum heights of Ri and $R_S^F(i-1)$.

b)

For even i, i.e., after drawing the 2nd, 4th, … spaces, the width of $R_S^F(i)$ is the sum of the maximum widths of $R_S^F(i-1)$ and Ri, and the height of $R_S^F(i)$ is the sum of the heights of $R_S^F(i-1)$ and Ri.

If li and hi are the width and height, respectively, of Ri and if Li and Hi are the width and height, respectively, of $R_S^F(i)$, then the spiral-based sequence is given numerically as follows:

For i=1, 3, 5,…,

$L_i=L_{i-1}+l_i,H_i=\max (H_{i-1},h_i).$

For i=2, 4, 6,…,

$L_i=\max (L_{i-1},l_i),H_i=H_{i-1}+h_i.$

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.

1. Download full-size image

Figure 1

In Figure 1(a), i=2. Therefore, we compute L2 and H2. Here, $L_2=\max (L_1,l_2)=\max (l_1,l_2)=l_2$, and $H_2=H_1+h_2=h_1+h_2$.

In Figure 1(b), a new space is added to the obtained $R^F(2)$. Hence, i=3, L3=L2+l3=l2+l3, and $H_3=\max (H_2,h_3)=\max (h_1+h_2,h_3)=h_1+h_2$.

In Figure 1(c), i=4, $L_4=\max (L_3,l_4)=\max (l_2+l_3,l_4)=l_4$, and $H_4=H_3+h_4=h_1+h_2+h_4$.

2.2. Spiral-based algorithm for obtaining a rectangular floor plan

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 $R_S^F(i)$ 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 $(x_i,y_i)$ and the given pair $(l_i,h_i)$, respectively. $(x_i,y_i)$ 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.

1. Download full-size image

Figure 2

The second kind of rectangle is extra space Ei, which may be empty. We denote its position by $(t_i,u_i)$ and its size by the pair $({\lambda }_i,{\mu }_i)$. In $R_S^F$, 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 $R_S^F(i)$. Its position also depends on i and is denoted by $(X_i,Y_i)$. The size of $R_S^F(i)$ is the pair $(L_i,H_i)$.

The steps for constructing $R_S^F$ 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 $(x_1,y_1)$, as shown in Figure 3.

1. Download full-size image

Figure 3

Step 3: R2 is drawn above R1 in such a way that its lower left vertex is the upper left vertex of $R_S^F(1)$, as shown in Figure 4(a).

1. Download full-size image

Figure 4

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 $R_S^F(2)$, an extra space t is drawn, as shown in Figure 4(b).

In general, if $i\equiv 1(\mathrm{mod}4)$, then $(x_i,y_i)=(X_{i-1}-l_i,Y_{i-1}),(X_i,Y_i)=(x_i,y_i)$, i.e., Ri is drawn to the left of $R_S^F(i-1)$ in such a way that its upper right vertex is the upper left vertex of $R_S^F(i-1)$.

If $h_i<H_{i-1}$, then $(t_i,u_i)=(x_i,y_i+h_i)$, and $({\lambda }_i,{\mu }_i)=(l_i,H_{i-1}-h_i)$. An extra space is drawn below Ri and to the left of $R_S^F(i-1)$.

If $h_i>H_{i-1}$, then $(t_i,u_i)=(X_{i-1},Y_{i-1}+H_{i-1})$, and $({\lambda }_i,{\mu }_i)=(L_{i-1},h_i-H_{i-1})$. An extra space is drawn below $R_S^F(i-1)$ and to the right of Ri.

Step 4: R3 is drawn to the right of $R_S^F(2)$ in such a way that its upper left vertex is the upper right vertex of $R_S^F(2)$.

The positioning of R3 with extra space t is shown in Figure 5. Illustrating all possible cases is not feasible. Hence, Figure 5 assumes that l2=l1.

1. Download full-size image

Figure 5

In general, if $i\equiv 2(\mathrm{mod}4)$, then $(x_i,y_i)=(X_{i-1},Y_{i-1}-h_i),(X_i,Y_i)=(x_i,y_i)$, i.e., Ri is drawn above $R_S^F(i-1)$ in such a way that its lower left vertex is the upper left vertex of $R_S^F(i-1)$.

If $l_i<L_{i-1}$, then $(t_i,u_i)=(x_i+l_i,y_i)$, and $({\lambda }_i,{\mu }_i)=(L_{i-1}-l_i,h_i)$. Here, an extra space is drawn to the right of Ri and above $R_S^F(i-1)$.

If $l_i>L_{i-1}$, then $(t_i,u_i)=(X_{i-1}+L_{i-1},Y_{i-1})$, and $({\lambda }_i,{\mu }_i)=(l_i-L_{i-1},H_{i-1})$. Here, an extra space is drawn to the right of $R_S^F(i-1)$and below Ri.

Step 5: R4 is drawn below $R_S^F(3)$ such that its upper left vertex is the lower left vertex of $R_S^F(3)$.

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.

1. Download full-size image

Figure 6

In general, if $i\equiv 3(\mathrm{mod}4)$, then $(x_i,y_i)=(X_{i-1}+L_{i-1},Y_{i-1}),(X_i,Y_i)=(X_{i-1},Y_{i-1})$, i.e., Ri is drawn to the right of $R_S^F(i-1)$ in such a way that its upper left vertex is the upper right vertex of $R_S^F(i-1)$.

If $h_i<H_{i-1}$, then $(t_i,u_i)=(x_i,y_i+h_i)$, and $({\lambda }_i,{\mu }_i)=(l_i,H_{i-1}-h_i)$. Here, an extra space is drawn below Ri and to the right of $R_S^F(i-1)$.

If $h_i>H_{i-1}$, then $(t_i,u_i)=(X_{i-1},Y_{i-1}+H_{i-1})$, and $({\lambda }_i,{\mu }_i)=(L_{i-1},h_i-H_{i-1})$. Here, an extra space is drawn below $R_S^F(i-1)$ and to the left of Ri.

Step 6: R5 is drawn to the left of $R_S^F(4)$ in such a way that its upper right vertex is the upper left vertex of $R_S^F(4)$.

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.

1. Download full-size image

Figure 7

In general, if $i\equiv 0(\mathrm{mod}4)$, then $(x_i,y_i)=(X_{i-1},Y_{i-1}+H_{i-1}),(X_i,Y_i)=(X_{i-1},Y_{i-1})$, i.e., Ri is drawn below $R_S^F(i-1)$ in such a way that its upper left vertex is the lower left vertex of $R_S^F(i-1)$.

If $l_i<L_{i-1}$, then $(t_i,u_i)=(x_i+l_i,y_i)$, and $({\lambda }_i,{\mu }_i)=(L_{i-1}-l_i,h_i)$. Here, an extra space is drawn to the right of Ri and below $R_S^F(i-1)$.

If $l_i>L_{i-1}$, then $(t_i,u_i)=(X_{i-1}+L_{i-1},Y_{i-1})$, and $({\lambda }_i,{\mu }_i)=(l_i-L_{i-1},H_{i-1})$. Here, an extra space is drawn to the right of $R_S^F(i-1)$ 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).

The construction of the spiral-based rectangular floor plan with the following spaces is shown in Figure 8, where Figure 8(i) indicates the required $R_S^F(5)$.

1. Download full-size image

Figure 8

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.

2.3. Seven additional spiral-based rectangular floor plans

Seven additional spiral-based rectangular floor plans can be obtained by slightly changing the spiral-based algorithm (Section 2.2) as follows:

(1)

By considering the anticlockwise movement as a replacement for the clockwise movement (e.g., refer to Figure 9[a])

1. Download full-size image

Figure 9

(2)

By interchanging the positions of R1 and R2 in the above step and then following the clockwise movement (e.g., refer to Figure 9[b])

(3)

By considering the anticlockwise movement in the above step (e.g., refer to Figure 9[c])

(4)

By positioning R1 and R2 side by side in the spiral-based algorithm and then following the clockwise movement (e.g., refer to Figure 9[d])

(5)

By considering the anticlockwise movement in the above step (e.g., refer to Figure 9[e])

(6)

By interchanging the positions of R1 and R2 in Step 4 and then following the clockwise movement (e.g., refer to Figure 9[f])

(7)

By considering the anticlockwise movement in the above step (e.g., refer to Figure 9[g])

In Figure 9, we consider the same spaces as those in the example in Section 2.2.

3. Connectivity of a rectangular floor plan

3.1. Adjacency among the spaces

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.

1. Download full-size image

Figure 10

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 Figures 8 and 9 is shown in Figure 11.

1. Download full-size image

Figure 11

3.2. Optimally connected rectangular floor plan

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 $R_S^F(n)$, 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 $R^F(n)$, 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.

4. Conclusion and future work

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.

Keywords

Floor plan

Extra space

Algorithm

Adjacency

References

References

Dabbour, 2012

DabbourGeometric proportions: the underlying structure of design process for Islamic geometric patternsFront. Archit. Res. (2012), pp. 382-383

Galle, 1981

GalleAn algorithm for exhaustive generation of building floor plansCommun. ACM, 24 (12) (1981), pp. 813-825

Gross, 2006

Yellen GrossGraph Theory and Its Applications(second ed.), Chapman & Hall/CRC, Boca Raton (2006)

Lai, 1988

Leinwand LaiAlgorithms for floorplan design via rectangular dualizationIEEE Trans. Comput. Aided Des., 7 (12) (1988), pp. 1278-1289

Rodrigue et al., 2006

Rodrigue, Comtois, SlackThe Geography of Transport SystemsRoutledge, New York (2006)

Shekhawat and Rectangle, 2013

Shekhawat, Rectangle Tilings, Connectivity and Associated Covariants, Thèse no. 4570, 2013, Section de Mathématiques, Université de Genève, Genève.

Stiny

StinyShape (Talking about Seeing and Doing)The MIT Press, Cambridge (2013)

Terzidis, 2007–08

TerzidisAutoPLAN: a stochastic generator of architectural plans from a building programform\cdotZ Jt. Study J. (2007–08), pp. 84-85

Peer review under responsibility of Southeast University.

Copyright © 2014 Higher Education Press Limited Company. Production and hosting by Elsevier B.V.

For further details log on website :
http://www.sciencedirect.com/science/article/pii/S2095263514000375