Shortest-path tree-based method for calculating visible area with time- and memory-saving preprocessing

Shota Tabata

Environment and Planning B, 2025, vol. 52, issue 7, 1618-1632

Abstract: Visibility has extensive application in areas such as architecture, urban planning, and security. This study proposes a novel approximation method, called the shortest-path tree-based method (SPT-based method), for calculating the visible area using a random Delaunay network on a 2D plane. Various methods are available for calculating the visible area, including exact and approximation methods. However, it is difficult to calculate the visible area repeatedly in a space that has a vast number of obstacles while achieving efficient time and memory usage. The SPT-based method focuses on time- and memory-saving preprocessing. To achieve an efficient calculation of the visible area, we discretised a plane using a random Delaunay network and approximated the visible area using Dijkstra’s method. To evaluate the efficiency of the proposed method, we compared the calculation time, accuracy, and memory usage of the plane-sweep, ray-trace, brute-force, and SPT-based methods while considering the influence of the number of obstacles. This study provides valuable insights for researchers and practitioners for choosing the most suitable approach for their specific needs. Overall, the proposed method offers a time- and memory-efficient solution for calculating the visible area, making it suitable for a detailed analysis of the visual environment and providing a heuristic solution to the art gallery problem requiring repetitive calculations.

Keywords: Visible area; isovist; shortest-path tree; Dijkstra’s method; random Delaunay network (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.sagepub.com/doi/10.1177/23998083241302570 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:envirb:v:52:y:2025:i:7:p:1618-1632

DOI: 10.1177/23998083241302570

Access Statistics for this article

More articles in Environment and Planning B
Bibliographic data for series maintained by SAGE Publications ().