Isovist graph generating method for structural expression of a floor plan

Abstract

This study explores enhancing spatial analysis by integrating Space Syntax with deep learning methods for images and graphs. While Space Syntax traditionally focuses on geometry and topology, it overlooks visual data like texture and color. As image content varies by location, capturing spatial context is essential, especially in irregular or open spaces where identifying central points is challenging. To address this, the study introduces the concept of an “isovist graph” - a spatial model that minimally covers a closed plane with isovists while preserving centrality and connectivity. A method is proposed to compute this model rigorously in discrete settings. Experiments show that exact solutions can be efficiently derived for many spatial cases, aligning with the intended objectives.

Keywords

space syntax isovist floor plan graph cover problem mathematical programing

Introduction

Basic space unitization methods such as convex spaces, axial maps, and isovists¹ have been widely applied in Space Syntax² to analyze spatial configurations at the scale of buildings and city blocks. However, image information such as texture, light, and color, which are visually more primitive, is outside the scope of Space Syntax. Even if the spatial composition, size, and shape are identical, the impression of a space can change significantly depending on the materials and lighting. Therefore, image-based information is essential for various types of spatial decision-making.

From the 1980s to the 2000s, when the Space Syntax method was developed and applied, the difficulty of obtaining image information as data and analyzing it seemed to be in the background. In recent years, omnidirectional cameras have become widespread, and the number of stock photos captured from various streets as street views has increased. With the recent development of deep learning technology, it has become easier to extract meaningful features from high-dimensional data in the form of images and to transform and compress images. In the field of urban analysis, the semantic segmentation of street-view images into basic spatial components, such as sky, buildings, and trees, is widely used to analyze their areas and spatial phenomena (e.g., walkability).³ In addition to streets, the stock of captured indoor images is also increasing,⁴ providing services such as virtual tours, and spreading to areas such as real estate.^5,6 In addition, a deep learning technique called a graph convolutional network has been developed to perform tasks such as regression and classification on the graph itself, which has multidimensional features such as nodes. Research has applied this technology to the analysis of houses^7,8 and streets,⁹ and the groundwork has been laid for analyzing complex graph structures in different ways.

An omnidirectional image is similar to a 3D isovist image; however, instead of depth information, it can be considered to be accompanied by general image information.¹⁰ Since the information in an image changes depending on where the image is taken, it is important to know where to take the image. Usually, images are captured at the center of a space with clear partitions, such as rooms; however, in a space with few partitions or an irregular system, the boundaries of the space may become unclear, making it difficult to define the center of the space. In addition, because a virtual tour enables the continuous navigation of a space by connecting the points where images are captured, it is necessary to consider connectivity. However, when creating a 3D model using camera position estimation and photogrammetry, it is easy to specify the shooting points relatively closely within the same space. However, because the main purpose of this research is to describe the structure of a space, it is preferable to have a minimum or close-to-minimum number of shooting points at a location (center) that is as representative of the space as possible.

Based on this background and awareness of the problem, this study defines an isovist graph as “a spatial model that covers a closed plane with a minimum or near-minimum number of isovist while ensuring centrality and connectivity,” and proposes a rigorous method to obtain it in a discrete problem setting. We propose a method for obtaining this rigorously in a discrete problem setting. This approach addresses limitations in prior isovist-based and axial map models, which often rely on approximate solutions and do not explicitly account for isovist centrality. A more detailed review of related studies and the positioning of this study is provided in Section 2. The proposed method was applied to multiple floor plans ranging from the architectural scale to the city block scale, and the solution time and obtained graphs were verified.

In the following sections, Section 2 describes the previous studies and the position of this research, and Section 3 presents the problem framework. Section 4 reports the concrete flow and formulation of the method. Section 5 verifies the method, Section 6 discusses the results, and Section 7 summarizes the study.

Related studies and positioning of this study

To clarify the novelty and methodological contribution of this study, this section reviews existing research in two main aspects: (1) spatial models used to represent visibility structures such as isovists, axial lines, and visibility graphs; and (2) solution methods for constructing or optimizing these spatial graphs. By organizing prior studies from these two perspectives, we highlight the theoretical and computational gaps that this study aims to address. Our method is then positioned accordingly, with a particular emphasis on its discrete treatment of isovists and its rigorous approach to solving the minimum coverage problem while considering centrality.

Spatial visibility models and their characteristics

Spatial visibility has been modeled in various ways depending on the target of analysis. This subsection outlines the key characteristics of isovist-based models and axial maps, highlighting differences in their spatial units, assumptions, and analytic purposes.

The concept of our isovist graph shares similarity with the function finding minimal set of isovists implemented in the Isovist_App.¹¹ While it can be said that the method is pioneering approach, it does not consider the centrality of isovist unlike our study. The definition of our isovist graph has many essential overlaps with the definition of an axial map in [2, pp. 91-92]. Hillier and Hanson² defined an axial map as the minimal set of straight lines that pass through all convex spaces and capture all axial links in the open space structure of a settlement. The idea of covering a plane with a finite number of connected unit spaces is common. However, axial maps are somewhat confusing concepts as entities. As highlighted by Batty and Rana,¹² axes are interpreted as coherent straight lines that move unimpeded in space; however, these are spatial units similar to aggregated road edges, making naive interpretation difficult. Therefore, when analyzing an axial map as a graph, the axes given as edges must be dual-transformed into nodes. In ordinary spatial analysis, various states at arbitrary observation points are observed and weighed. However, such a correspondence cannot be obtained for nodes given by a dual transformation, and measurement at the center of the line segment or an averaging process is required. However, an isovist is a simpler spatial unit than an axial map because it covers the entire area visible from a single point in all directions. On the other hand, our study differs from the present study¹² in that it uses isovists to generate the axial map described below and does not consider the centrality of isovists or the connection relationship between vantage points. Visibility graph analysis (VGA)¹³ is a well-known graph model based on the connection between an isovist’s vantage points. This method generates isovists on a grid, creates a visibility graph of them, calculates various graph features such as a clustered coefficient, and visualizes the features as an isovist field on the original raster. VGA is suitable for expressing the differences in detailed features in a space because it expresses the space as a detailed field. To simplify the visibility graph using VGA, a method of thinning by maximizing the modularity of the graph¹⁴ has been proposed, but it is difficult to obtain a complete coverage of the space by the thinned representative points. There are studies that generate graphs to move as a method of indoor navigation.^15–17 In order to create a navigation graph, it is necessary to standardize the spatial units in the preprocessing stage. In this case, it is often the case that the entire space divided by walls and doors is considered to be one spatial unit,^18,19 and there are cases where spatial units that are not necessarily visually integrated, such as L-shaped rooms, are included. On the other hand, in complex spaces, a method based on a triangular division has been proposed,²⁰ but this leads to the creation of visually redundant spatial units. Another similar field is the study of determining the location of the station points for 3D scan of buildings.^21,22 In these studies, the problem of finding the minimum number of points and their positions necessary to cover the entire target space is similar to that of this study, but since the main purpose is to scan buildings, the scope of an isovist is often limited and the centrality of the space is not taken into account.

Solution methods for constructing or optimizing these spatial graphs

This subsection reviews prior methods for constructing and optimizing spatial graphs based on visibility.

First, the function of Isovist_App uses a greedy algorithm to find the minimum isovist graph. However, the number of vantage points obtained is not guaranteed to be theoretically minimal. Next, we focus on the automatic generation of axial maps. As mentioned earlier, it was claimed that an axial map can be derived by leaving axial lines until all convex spaces are traversed and all axial lines that can be connected to other axial lines are connected without repetition. The method for deriving a linear representation of a spatial configuration relies on the prior definition of a convex partition of space. The problem of partitioning the minimum convex polygon of a polygon involves efficient algorithms for simple polygons without holes (e.g. Ref. 23). However, it is NP-hard in the case of holes, which are common in space.²⁴ Moreover, even given the optimal convex partitions, the problem of covering these convex polygons with the minimum number of axial lines is NP-hard because it can be attributed to the set cover problem.²⁵ In addition, from the viewpoint of mathematical programming, the axial map must be connected as a graph that adds cut and flow constraints, thereby making the solution more difficult. Despite these mathematical difficulties, there is a growing need for an objective method for generating axial maps, and Peponis et al.,²⁶ Batty and Rana,¹² and Turner²⁷ studied its automatic generation. First, Peponis et al. divided space by s-partition,²⁸ which divides space by wall extensions instead of convex regions, and then enumerated m-lines, which represent the diagonals of other wall surfaces, and ordered m-lines, in the order in which m-lines intersect more s-partitions. Tuner et al. improved Peponis’ method and proposed a heuristic called subset elimination to retain the necessary lines of sight. Batty and Rana divided the space into grids, found isovists at each point, and used some of them to cover the space. They then generate axial lines in these isovists according to criteria such as maximum length and repeat the process until there are no uncovered areas. This method gives the user the freedom to switch between multiple criteria and change the selection of isovists and axial lines; however, it does not guarantee the connectivity of the axial lines.

All the above algorithms were heuristic and did not guarantee the minimum number of necessary axial links in their problem setting. Jung and Kim²⁹ formulated Peponis’ problem of finding an axial map using integer programming (without considering cyclicity) and showed that an exact solution can be found. In their formulation, they defined the constraint that axial lines are connected to each other; however, the only connection constraint is that an axial line is connected to one or more other axial lines, such that, for example, if there is a set of four axial lines ${A, B, C, D}$ the resulting graph is allowed to separate into multiple connected components, such as ${A, B}, {C, D}$ , and so on. In general, the number of possible connectivity patterns of a graph grows exponentially with the number of its graph elements, making it difficult to explicitly formulate the connectivity constraints in terms of mathematical programming constraints, which require a complex formulation. One approach is to use network flows as constraints that are formulated to guarantee geographic connectivity, as in Shirabe.³⁰ Another study by Dehbi et al.²¹ used connectivity constraints to generate indoor navigation graphs. Although these graphs are guaranteed to be single-connected graphs, the complexity of their constraints makes it difficult to apply them to large problems. In this study, we demonstrated that the lazy-constraint method can be used to solve this problem more efficiently.

In summary, compared to previous studies, this study proposes a new model and problem setting, namely the isovist cover problem, considering centrality and connectivity. Furthermore, the solution method differs from related studies in that it devises an efficient and exact solution method that can be applied to axial map-solving, which is highly novel.

Problem framework

In this study, we assume that the class of polygons representing a connected plane is either simple or multiple connected polygons. We consider the problem of visually covering a plane using isovists generated from a finite number of vantage points. As it would be somewhat difficult to implement a geometrically rigorous calculation of the coverage, we generated observation points discretely and evaluated the coverage as an approximation by assuming that they were all visible from the isovist. In this case, in order to ensure the representation of the structure of the space, it is a constraint that the observation points are visually connected to each other. Considering a situation such as that used in filming, we aim to position the isovist’s vantage point at what we consider the center of the space. Let $P$ and $O$ be sets of candidate vantage points and observation points, respectively.

Definition of our isovist

Let us take as an example a plane with a T-shaped hole in a square region as shown in Figure 1(a). The polygon formed by connecting the visible observation points in sequence from the vantage point $p \in P$ is the isovist in this study. As shown in Figure 1(b), the usual isovist simply expresses the geometrical extent of the line of sight without depending on the observation points; however, the isovist in this study is a polygon composed of the periphery of the visibility graph connecting the visible observation points, and the area of the isovist is somewhat narrower (Figure 1(c)). To reduce this difference, it is necessary to narrow the interval between the generations of observation points.

Figure 1.

Target space and isovist.

Coverage

Next, the isovist coverage is explained. When the observation points are placed only at the endpoints of each line segment, as shown in Figure 2(a), the two monitoring points at the positions shown in the figure are sufficient to cover all the observation points. However, it can be seen that the upper part of the space is not covered by the isovist. Therefore, an observation point was added at the midpoint of each line segment, as shown in Figure 2(b). In this case, three observation points are required to cover all the observation points, and the corresponding isovist also shows that the space is completely covered. In this example, to fill the gaps in space, the observation points must be placed at the required density.

Figure 2.

Explanation of covering.

Connectivity

Connectivity has been introduced as a fundamental constraint for axial lines in the automatic generation of axial maps and is also introduced in this study because it is a prerequisite for analyzing space graphically. In this study, isovists were considered connected if their vantage points were directly visible to each other. In addition to visual connectivity, linear connectivity also exists. For example, if the connectivity of an axial map is the former, the connectivity of a segmentation map divided among road segments corresponds to the latter.³¹ It can be said that dynamic connectivity is a graphical representation of the topological property of space that indicates whether or not one spatial unit is continuously accessible from another, regardless of whether it is visually visible or not. If so, it is conceivable to express the isovist connectivity in terms of the isovist overlap, which is relatively easy to formulate and solve. However, we did not adopt this method because, combined with the omnidirectional nature of isovists, it connects to distant isovists that cannot be accessed without passing through other spatial elements. The limitations of the connectivity set used in this study and future directions are discussed later.

Centrality

The last key point is centrality, which is the goal of this research: to cover space with an isovist and structure the space in terms of its connectivity. To capture an omnidirectional image, it is desirable to capture the image at the center of each individual “space” as much as possible. The problem is how to define these “spaces” and their “centers.” Because isovists are a class of star-shaped regions that radiate from a viewpoint, the coherence of the entire region as a space is generally weak. Conversely, convex regions are a class of regions in which any two points within them are visible and can easily be a unit of a coherent space. An isovist is a broader region class than convex regions; therefore, we evaluated spatiality in terms of convex regions contained within the isovist. For our limited isovist, the convex hull is the maximal clique in the visibility graph formed by connecting the observation points (Figure 3(a)). However, because there are generally multiple maximal cliques, it is necessary to select the one that is representative of the isovist from among their names. Figure 3(b) shows an example of the three maximal cliques. First, cliques $p_{1}$ and $p_{2}$ contain a vantage point, but not $p_{3}$ , so the latter is excluded from the list of candidates. The first type of space that is easily recognized is a solid boundary,³² where the region is divided by a wall. Comparing clique $p_{1}$ and clique $p_{2}$ , the latter can be a more coherent unit of space because the ratio of the lengths of the walls that overlap the line segments that make up the clique is higher. To quantify this, we proposed an index that divides the number of vantage points constituting a clique by its circumference in the next section. If the space is to be divided into a small number of vantage points, the convex hull should be as large as possible. In other words, the clique area should be used as an index. Incidentally, Stamps³² concluded that the only two major attributes among the 25 indicators created by the Isovist are area and concavity. The cliques were ranked by the weighted sum of these two indices, and the clique with the largest sum was in the convex region of the isovist.

Figure 3.

Examples of derived process maximum cliques up to representative clique.

Finally, as shown in Figure 3(c), let $d i f f_{p}$ be the distance between a vantage point $p \in P$ of the isovist and the center of its representative clique. For an ideal isovist, the $d i f f_{p}$ is expected to be as close to zero as possible because the vantage point is at the center of the space.

Specific flow and formulation

Table 1 summarizes the variables used in the mathematical programming.

Table 1.

Symbols used in variable names.

Category	Symbol	Description
Set	$P$	Set of candidate vantage points in the plane
	$O$	Set of observation
	$V_{p}$	Set of vantage points visible from $p \in P$ (including self, $V_{p} \subset P$ )
	$W_{o}$	Set of vantage points visible from $o \in O$ ( $W_{o} \subset P$ )
	$E$	Set of edges formed by connecting $\forall q \in V_{p} ∖ {p}$ at $\forall p \in P$
	$G$	Visibility graph $G = (P, E)$
Set of lazy constraint	$P_{1}$	Valid set of vantage points ( $p \in P_{1} \subset P$ ) such that $x_{p} = 1$ in the solution candidates
	$G_{P_{1}}$	Induced subgraph of $G$ by $P_{1}$
	$C$	A connected component of $G_{P_{1}}$ with $C$ ( $C \in G_{P_{1}}$ )
	$N_{C}$	The set of visible and invalid candidate vantage points from the vantage points contained in $C$
Variable	$n$	The number of isovist vantage points
Variable	$x_{p}$	Whether $p \in P$ is a vantage point ( $x_{p} \in {0, 1}$ )
Constant	${d i f f}_{p}$	Euclidean distance between the vantage point $p \in P$ and the center of its representative clique

The main flow is as follows. The proposed method consists of steps 1-4. These are described in the following order.

Step 1: Placement of observation points and candidate vantage points

After loading the floor plan data, observation points were placed on the wall to evaluate the visibility of the entire space. The total number of observation points to be placed was assumed to be constant and expressed as $| O |$ . First, we place observation points at the endpoints of the line segments that make up the wall surface, and then place observation points on each line segment with as constant a spacing until the constant is satisfied (Figure 4(a)).

Figure 4.

Arrangement of observation and vantage points.

Next, the isovist candidate vantage points are placed in the space. Similarly, the total number of points was assumed to be constant and denoted as $| P |$ . Although isovists are often generated on a lattice, following Psarra and McElhinney,³³ we performed a preliminary experiment by uniformly arranging the candidate vantage points randomly in space, and found that vantage points close to m-lines were often selected. To improve the computational efficiency by eliminating unnecessary vantage points and because the visual connectivity of the vantage points is a constraint in this experiment, we decided to generate vantage points at the intersection of multiple m-lines (Figure 4(b)). However, in this case, points close to walls and points at nearby intersections are excluded or represented by a single point, respectively.

Step 2: Selection of isovist and maximum convex region

An isovist is generated by extracting the visible observation points for each candidate vantage point $p \in P$ and connecting them by straight lines in angular order from $p$ . Next, we create a visibility graph by connecting these observation points, enumerate the maximal cliques of this graph, and denote the set of maximal cliques as $M_{p}$ . Here, since our problem setting is discrete, if the maximal clique is a simple polygon with holes, we can assume a case where holes does not intersect with any of the edges are in the clique as illustrated in Figure 5. Such a maximum clique is excluded from $M_{p}$ . Among the enumerated maximal cliques, the maximal clique $m \in M_{p}$ with the maximum value of the weighted sum of the standardized wall fraction and area, as shown in the following equation, is adopted as the representative clique.

α \cdot std {(\frac{| O_{m} |}{p e l i m t e r_{m}})}_{p} + (1 - α) \cdot std {(a r e a_{m})}_{p}

(1)

Figure 5.

Example of a maximum clique with a hall.

In the above equation, $O_{m} \subset O$ is the set of observation points constituting $m$ , $p e l i m t e r_{m}$ and $a r e a_{m}$ are the side length and area of the polygon by m, respectively, $std {()}_{p}$ is the function to standardize the wall fraction and area of each maximal clique in $M_{p}$ , respectively, and $α \in [0.0, 1.0]$ is the weight between them. Finally, let ${d i f f}_{p}$ be the Euclidean distance between $p$ and the center of gravity of the convex region using its representative clique.

Step 3: Finding the minimum number of vantage points (Opt. 1)

The first is the number of isovists that can cover the plane while satisfying the isovist linkage constraints. For this purpose, we define the following mixed-integer quadratic constraint programming problem.

Minimize n

(2)

subject to \sum_{p \in P} x_{p} = n

(3)

\sum_{p \in W_{q}} x_{p} \geq 1, \forall q \in O

(4)

lazy constraint \sum_{p \in C} x_{p} - \sum_{p \in N_{C}} x_{p} \leq | C | - t_{C}, if | G_{P_{1}} | \geq 2, \forall C \in G_{P_{1}}

(5)

t_{C} = {\begin{cases} 1, & if N_{C} \cap N_{D} \neq \emptyset, \exists D \in G_{P_{1}} ∖ C \\ 2, & otherwise \end{cases} \begin{array}{l}  \end{array}, \forall C \in G_{P_{1}}

(6)

Equation (4) guarantees that any observation point is visible from one of the selected vantage points. Equation (5) is a lazy constraint that guarantees that the isovist graph is connected. Lazy constraints are a bottom-up method in which after finding a tentative solution, the tentative solution is checked to see if it is disconnected. If so, the necessary constraints are added successively to gradually strengthen the constraints. First, the set of vantage points for $x_{p} = 1$ is extracted from the optimization results and denoted as $P_{1} \subseteq P$ . Then, an induced subgraph $G_{P_{1}}$ induced by $P_{1}$ is extracted from the graph $G = (P, E)$ . Lazy constraint (5) is added when the number of connected components of $G_{P_{1}}$ is at least two, i.e., $G_{P_{1}}$ is disconnected. This constraint indicates that at least $t_{C}$ vantage point changes are required in the candidate set of vantage points (neighborhoods) adjacent to the connected components and their neighbors because the node combination of each connected component does not satisfy the constraint as it is. For an isolated connected component to be connected to others, at least one of the candidate vantage points in the neighborhood must be valid. However, under the constraint that the total number of vantage points is $n$ , it is necessary to disable the vantage points of the connected component near candidate vantage points as many times as possible. $t_{C}$ is a threshold value that takes one of the values shown in equation (6) depending on the conditions. For example, as shown in Figure 6, there is an induced subgraph consisting of three connected components ${C_{1}, C_{2}, C_{3}}$ in the space, and Let $N_{C_{1}}, N_{C_{2}}, N_{C_{3}}$ be their neighborhoods. In this case, $t_{C} = 2$ because it is necessary to validate one candidate vantage point in the neighborhood and invalidate one vantage point in the connected component. By contrast, $N_{C_{2}}$ and $N_{C_{3}}$ have a common set. In this case, $t_{C} = 1$ , because the set can be connected by making one of the candidate vantage points in the common set valid and one of the vantage points of one of the connected components undirected.

Figure 6.

Difference between connected components and neighborhoods.

Step 4: Select the isovist that occupies the center of the space (Opt. 2)

The following is a mathematical programming problem in which the number of vantage points is set to a value greater than or equal to the minimum n obtained in Opt. 1, and the isovist is chosen such that the vantage points are placed as much as possible in the center of the space while satisfying the connectivity constraints. The constraints are the same as in Opt. 1. In Opt. 2, $n$ increased as necessary because there were cases where the vantage point did not reach the center of each space with the minimum $n$ .

Minimize \sum_{p \in P} x_{p} \cdot d i f f_{p}

(7)

subject to \sum_{p \in P} x_{p} = n

(8)

\sum_{p \in W_{q}} x_{p} \geq 1, \forall q \in O

(9)

lazy constraint \sum_{p \in C} x_{p} - \sum_{p \in N_{C}} x_{p} \leq | C | - t_{C}, if | G_{P_{1}} | \geq 2, \forall C \in G_{P_{1}}

(10)

t_{C} = {\begin{cases} 1, if N_{C} \cap N_{D} \neq \emptyset, \exists D \in G_{P_{1}} ∖ C \\ 2, otherwise \end{cases}, \forall C \in G_{P_{1}}

(11)

Verification

Verification was performed using the following settings.

Floor plans and parameters

In this study, six floor plans of architectural and street scales were used, focusing on familiar spaces in this type of analysis (see Figure 7). Buildings 1,2,3²⁶ and the National Gallery²⁷ were used as well-formed spaces, and a short-term treatment facility for children with emotional disorders (Treatment Facility)³⁴ and Gassin² were used as irregular spaces. Table 2 lists the number of vantage and observation points in each space. The number of observation points in each space was approximately 1000 and they were placed as evenly as possible on the wall. The vantage point was generated at the intersection of the m-lines and one of the vantage points within 1/3 of the minimum side length of each space model was selected.

Figure 7.

Floor plans used in the verification.

Table 2.

Number of vantage points and observation points placed in each floor plan.

Name	$\| P \|$	$\| O \|$
Building 1	1359	1058
Building 2	488	1034
Building 3	1107	1008
National gallery	1923	1447
Treatment facility	1021	997
Gassin	1574	1050

Implementation of the method

The proposed system was implemented in Python 3.12 and integrated with Grasshopper, operating within Rhinoceros 3D version 8.0. Graph-theoretic operations, including clique extraction, were performed using the igraph library. Mathematical programming components were formulated through the Python API of Gurobi Optimizer (version 12.0.1). For the optimization process, the solver parameters were set with Params. MIPFocus = 2 to prioritize the identification of optimal integer solutions. A time limit of 10 min was imposed on each solution run to balance precision with computational efficiency. All computations were conducted on a Windows 11 Pro 24H2 system equipped with an Intel Core Ultra 285K processor, 192 GB of DDR5-5200 MHz memory.

Results

Opt. 2 shows the results for

α = 0.5

. Table 3 shows the minimum n obtained by Opt. 1, the number of n for which the number of vantage points was set to be appropriate according to the author’s subjective judgment in Opt. 2, and the time required to solve the problem. The gap is the error between the theoretical optimal solution and the solution found; a zero gap indicates that the optimal solution has been found. The solution times varied from case to case, but Opt. 1’s solution times were instantaneous or at most 30 s, except for two cases in which the optimal solution was not found within the time limit. Opt. 2, on the other hand, took at most 30 s, although this was partly due to the fact that

n

was increased (i.e., the concatenation constraint was more easily satisfied).

Table 3.

Summary of optimization results.

Floor plan	$n$		Gap (%)		Computational time (sec)
Floor plan	Opt. 1	Opt. 2	Opt. 1	Opt. 2	Opt. 1	Opt. 2
Building 1	15	17	0.0	0.0	13.5	32.8
Building 2	12	←	0.0	0.0	0.1	0.5
Building 3	6	←	0.0	0.0	0.4	0.8
National gallery	50	58	2.0	0.0	>600	42.4
Treatment facility	11	12	9.1	0.0	>600	35.3
Gassin	32	←	0.0	26.0	120.4	>600

For comparison, Appendix A1 shows the connection constraints with network flows and their computation results, which show that they are less efficient than the lazy constraints.

Figures 8 and 9 show the results of the placement of each plan view using Opt. 1 and Opt. 2 for each plane. In addition to the vantage points and edges connecting them, the visualization of the Opt. 1 results shows that the areas covered by isovists were colored to confirm that there was no coverage leakage. In the Opt. 2 visualization, the main clique for each isovist is shown. The following sections describe the floor plans.

Figure 8.

Optimization result 1 (upper row: Opt. 1, lower row: Opt. 2).

Figure 9.

Optimization result 2 (upper row: Opt. 1, lower row: Opt. 2).

Building one consists of a series of rectangular rooms, and the center of the space and the number of points required can be easily assumed. Fifteen points were the minimum number of points required by Opt. 1, but this did not place the rooms in the center of the space, but at the boundaries. Therefore, Opt. 2 set the number of points to 17 to match the number of rooms. As the vantage points must be visible, the vantage points in the lower-left room are placed at the boundary. The other rooms were placed in the center of the room.

Building two consisted of a relatively finely segmented space with ambiguous boundaries. Both examples show the minimum number of vantages’ points. Because they have the same number of vantage points, they are similar, except for the finer space on the right side.

Building three is loosely segmented from a wide space to a narrow space with few boundaries. Compared to Opt. 1, the narrow space had a point placed in the center.

The National Gallery is a segmented space, as shown in Building 1. There was a difference between the minimum number of vantage points and the appropriate number of vantage points. However, there are still places where the vantage points are not placed, such as the circular empty space on the right-hand side.

Treatment Facility has irregular systems and unclear boundaries. Because the vantage points tended to be located near the walls with the minimum number of units, we increased the number by one and performed Opt. 2. The impression is that the vantage points are arranged in a coherent spatial unit.

Gassin ran Opt. 2 with the minimum number of vantage points. The arrangement of the interior vantage points tends to be slightly different from Opt. 1.

The above results show that the minimum number of vantage points by Opt. 1 tended to be placed at the boundary, but by Opt. 2, the number of vantage points was placed at the center of the space by increasing the number of vantage points as necessary. However, the connection relation of the vantage points is often not that of the neighbors but that of the distant vantage points, which will be discussed in the next chapter.

Discussion

The following are discussed.

Difference in α

By setting α in Opt. 2, the convex hull representing the isovist can be set in consideration of the balance from a spatially closed convex hull to a convex hull with a large area. The previous results were obtained for $α = 0.5$ . Figure 10 shows what happens when $α \in {0.0, 0.5, 1.0}$ is changed, using Building 3 as an example. For $α = 0.0$ , the clique with the largest area is selected, and the center of the isovist tends to shift due to the presence of multiple cliques that extend far out from small rooms. On the other hand, $α = 1.0$ is the case where the clique with the largest amount of walls is selected, and the isovist’s vantage point tends to be placed in the center of small spaces, including Appendix A2. $α = 0.5$ is a result that balances these results overall.

Figure 10.

Differences in Opt. 2 results according to $α$ using building 3.

Connectivity

This section discusses the connectivity. The results showed a tendency to connect to distant vantage points. This result is somewhat unnatural from the viewpoint of spatial connectivity as perceived by humans. People may perceive spatial connectivity in a kinematic sense. In this study, the visual connectivity of the vantage points was used as a constraint. According to Turner et al. (year): However, as indicated by Batty and Rana,¹² in isovist coverings, the isovist region itself is always connected or adjacent according to the definition of the problem. This connectivity guarantees second-order visibility. As mentioned in Section 3, isovist regions themselves often intersect with distant isovist regions; therefore, expressing connectivity in this manner would result in an excessive degree of connectivity, as the isovist region itself would be connected to the distant isovist region. Alternatively, if orthodox convex partitioning is applied, for example, coverage and linear connectivity are satisfied. However, the results of Carranza and Koch³⁵ show that there is a tendency for excessive partitioning, such as the 114 partitions in Gassin. Because the main objective of this study was to propose a method for solving connectivity in a rigorous and efficient manner, the issue of connectivity remains. Future work is required to improve the proposed method to consider dynamic isovist connectivity in applications such as graph analysis.

Other limitations and future issues

In this study, monitoring points were placed discretely on the wall surface to simplify the implementation of the spatial analysis. isovist is geometrically determined by the location of the vantage point; therefore, if rigor is important, it is desirable to solve the covering problem under continuous conditions. To simplify the computation time, the vantage points are placed only at the intersection points on the m-line as a rule of thumb. The effect of this limitation on the results has not been fully verified and will need to be verified in conjunction with improvements to the model. In addition, the exact solution method has some computational limitations, and the development of an approximate solution method is necessary.

Conclusion

In this study, we proposed an isovist graph as a new concept of a spatial model that covers a plane with an isovist under the condition of connectivity, mainly for architectural and street-scale spaces, and proposed a fast exact solution method for the automatic generation of axial maps by devising the connectivity constraint, which has been difficult so far. We proposed a new method to solve the problem of how to generate an axial map automatically by devising linkage constraints and verified the method using six architectural and urban area models. Several plans can be solved in a short time by sampling data, devising constraint expressions for coupling conditions, such as delay constraints, and using the latest mathematical programming solvers. Although complex plans require more computation time, and in some cases, the optimal solution was not obtained, the optimality gap was demonstrated and could be used as a guide when creating heuristics in the future. The center of space is important for this method because it determines the point at which an omnidirectional image is captured. The vantage point could be placed close to the center of the space by setting α = 0.5. This study aimed to develop an isovist graphical model to analyze spatial configurations. However, the model cannot model local connectivity relations, such as lines of flow, because the connection relation of the vantage points is often such that distant vantage points are connected. In addition, the space was sampled discretely. Improvements in the representation of local connectivity and the discrete nature of spatial sampling are necessary for practical use in the future.

Footnotes

Acknowledgements

The authors would like to thank Associate Professor Sam McElhinney at UCA Canterbury for sharing information about Isovist_App.

ORCID iD

Atsushi Takizawa

Ethical approval

This study did not involve human participants or animals; therefore, ethical approval and informed consent were not required.

Funding

This work was supported by a JSPS Grant-in-Aid for Scientific Research (C) (grant number: 23K04161).

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Data Availability Statement

Data are available from the corresponding author upon reasonable request.*

Appendix

References

Benedikt

. To take hold of space: isovists and isovist fields. Environ Plann B 1979; 6(1): 47–65.

Hillier

Hanson

. The social logic of space. Cambridge University Press, 1984.

Koo

Guhathakurta

Botchwey

. How are neighborhood and street-level walkability factors associated with walking behaviors? A big data approach using street view images. Environ Behav 2022; 54(1): 211–241.

Lee

Kim

Shin

, et al. An AI-assisted approach for creating and archiving interior design references using 360-degree panoramic images. Archit Sci Rev 2024; 1–13. DOI:10.1080/00038628.2024.2445049.

Matterport . Matterport discover 2025. https://discover.matterport.com, accessed 28 April 2025.

RICOH . RICOH360 tours 2025. https://www.ricoh360.com/ja/tours/, accessed 28 April 2025.

Kitabayashi

Narahara

Yamasaki

. Graph neural network based living comfort prediction using real estate floor plan images. In: Proceedings of the 4th ACM international conference on multimedia in Asia (MMAsia 22), Tokyo, Japan, 13–16 December 2022, vol 34, pp. 1–5.

Takizawa

. Extracting real estate values of rental apartment floor plans using graph convolutional networks. Environ Plan B Urban Anal City Sci 2024; 51(6): 1195–1209.

Yue

, et al. Graph convolutional networks for street network analysis with a case study of urban polycentricity in Chinese cities. Int J Geogr Inf Sci 2024; 38(5): 931–955.

10.

Takizawa

Kinugawa

. Deep learning model to reconstruct 3D cityscapes by generating depth maps from omnidirectional images and its application to visual preference prediction. Des Sci 2020; 6: e28.

11.

McElhinney

The Isovist_App: a basic user guide, 2024, v1.7. https://research.uca.ac.uk/6585/1/Isovist_UserGuide_1-7.pdf, accessed 28 April 2025.

12.

Batty

Rana

. The automatic definition and generation of axial lines and axial maps. Environ Plann Plann Des 2004; 31(4): 615–640.

13.

Turner

Doxa

O’Sullivan

, et al. From isovists to visibility graphs: a methodology for the analysis of architectural space. Environ Plann Plann Des 2001; 28(1): 103–121.

14.

Hwang

. Network communities in the visibility graph: a new method for the discretization of space. In: Proceedings of the ninth international space syntax symposium, Seoul, Korea, 31 October to 3 November 2013. paper no. 045.

15.

Yang

Worboys

. Generation of navigation graphs for indoor space. Int J Geogr Inf Sci 2015; 29(10): 1737–1756.

16.

Zhou

Weibel

Richter

, et al. HiVG: a hierarchical indoor visibility-based graph for navigation guidance in multi-storey buildings. Comput Environ Urban Syst 2022; 93: 101751.

17.

Hamzei

De Cock

Tomko

, et al. Indoor view graph: a model to capture route and configurational information. Environ Plan B Urban Anal City Sci 2024; 51(9): 2213–2231.

18.

Liu

Wang

Fan

, et al. Research on map partitioning and preprocessing algorithms for global path planning. In: 4th international conference on electronic communication and artificial intelligence (ICECAI), Guangzhou, China, 12–14 May 2023, pp. 244–250.

19.

Han

Qiao

, et al. Navigation-oriented topological model construction algorithm for complex indoor space. ISPRS Int J GeoInf 2023; 12(6): 248.

20.

Wei

Zlatanova

. An indoor navigation approach considering obstacles and space subdivision of 2D plan. In: International archives of the photogrammetry, remote sensing and spatial information sciences. XXIII ISPRS Congress, 12–19 July 2016, Prague, Czech Republic, 2016, XLI-B4, pp. 339–346.

21.

Dehbi

Leonhardt

Oehrlein

, et al. Optimal scan planning with enforced network connectivity for the acquisition of three-dimensional indoor models. ISPRS J Photogrammetry Remote Sens 2021; 180: 103–116.

22.

Cabrera-Revuelta

Tavolare

Buldo

, et al. Planning for terrestrial laser scanning: methods for optimal sets of locations in architectural sites. J Build Eng 2024; 85: 108599.

23.

Chazelle

Dobkin

. Optimal convex decompositions. Machine Intelligence and Pattern Recognition. 1985; 2: 63–133. DOI:10.1016/B978-0-444-87806-9.50009-8.

24.

Lingas

. The power of non-rectilinear holes. In: Proc. 9th international colloquium of automata languages, and program, lecture notes computer science, Aarhus, Denmark, 12–16 July 1982, Springer-Verlag, pp. 369–383.

25.

Karp

RM.

Reducibility among Combinatorial Problems. In: Miller

Thatcher

Bohlinger

(eds). Complexity of Computer Computations. The IBM Research Symposia Series. Springer, Boston, MA. 1972, pp. 85–103. DOI: 10.1007/978-1-4684-2001-2_9.

26.

Peponis

Wineman

Bafna

, et al. On the generation of linear representations of spatial configuration. Environ Plann Plann Des 1998; 25(4): 559–576.

27.

Turner

Penn

Hillier

. An algorithmic definition of the axial map. Environ Plann Plann Des 2005; 32(3): 425–444.

28.

Peponis

Wineman

Rashid

, et al. On the description of shape and spatial configuration inside buildings: convex partitions and their local properties. Environ Plann B 1997; 24: 761–781.

29.

Jung

Kim

. A linear programming method for finding a minimal set of axial lines representing an entire geometry of building and urban layout. Applied Sciences 2020; 10(12): 4273.

30.

Shirabe

. A model of contiguity for spatial unit allocation. Geogr Anal 2005; 37(1): 2–16.

31.

Van Nes

Yamu

. Analysing linear spatial relationships: the measures of connectivity, integration, and choice. In: Van Nes

Yamu

(eds) Introduction to Space Syntax in Urban Studies. Springer, 2021, pp. 35–86.

32.

Stamps

. Isovists, enclosure, and permeability theory. Environ Plann Plann Des 2005; 32(5): 735–762.

33.

Psarra

McElhinney

. Just around the corner from where you are: probabilistic isovist fields, inference and embodied projection. Journal of Space Syntax 2014; 5(1): 109–132.

34.

Sou Fujimoto Architects . Short-term treatment facility for emotionally disturbed children, living wing. Shinkenchiku 2006; 81(10): 174–184.

35.

Carranza

Koch

. A computational method for generating convex maps using the medial axis transform. In: Proceedings of the ninth international space syntax symposium, Seoul, Korea, 31 October to 3 November 2013, paper no. 064.