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.
AsanoT (1985) An efficient algorithm for finding the visibility polygon for a polygonal region with holes. IEICE TransactionsE68(9): 557–559.
2.
BattyM (2001) Exploring isovist fields: space and shape in architectural and urban morphology. Environment and Planning B: Planning and Design28(1): 123–150. DOI: 10.1068/b2725.
3.
BenediktML (1979) To take hold of space: isovists and isovist fields. Environment and Planning B: Planning and Design6(1): 47–65. DOI: 10.1068/b060047.
4.
BenediktMLMcelhinneyS (2019) Isovists and the metrics of architectural space. In ACSA 2019: BLACK BOX: Articulating Architecture’s Core in the Post-Digital Era. Pittsburg, PA, USA, 1–10. 27–30 March 2019.
BungiuFHemmerMHershbergerJ, et al. (2014) Efficient computation of visibility polygons. arXiv preprint. Available at:https://doi.org/10.48550/arXiv.1403.3905(accessed 22 November 2024).
7.
ChangDKParkJ-H (2011) Exploration of isovist fields to model 3D visibility with building facade. Architectural Research13(3): 19–29. DOI: 10.5659/AIKAR.2011.13.3.19.
8.
ChenavierNDevillersO (2018) Stretch factor in a planar Poisson-Delaunay triangulation with a large intensity. Advances in Applied Probability50(1): 35–56. DOI: 10.1017/apr.2018.3.
9.
ChmielewskiS (2021) Towards managing visual pollution: a 3D isovist and voxel approach to advertisement billboard visual impact assessment. ISPRS International Journal of Geo-Information10(10): 656. DOI: 10.3390/ijgi10100656.
10.
ChristensonM (2010) Registering visual permeability in architecture: isovists and occlusion maps in AutoLISP. Environment and Planning B: Planning and Design37(6): 1128–1136. DOI: 10.1068/b36076.
11.
DaltonRCDaltonNSMcElhinneyS, et al. (2022) Isovists in a grid: benefits and limitations. In: van NesAde KoningRE (eds) Proceedings of the 13th Space Syntax Symposium. Bergen, Norway, 551. 20–24 June 2022. DOI: 10.3929/ethz-b-000594112.
12.
DavisLSBenediktML (1979) Computational models of space: isovists and isovist fields. Computer Graphics and Image Processing11(1): 49–72. DOI: 10.1016/0146-664X(79)90076-5.
13.
DawesMJOstwaldMJ (2014) Prospect-refuge theory and the textile-block houses of Frank Lloyd Wright: an analysis of spatio-visual characteristics using isovists. Building and Environment80: 228–240. DOI: 10.1016/j.buildenv.2014.05.026.
14.
De BergMCheongOvan KreveldM, et al. (2008) Line segment intersection. In Computational Geometry Algorithms and Applications. 3rd edition. Heidelberg, Berlin: Springer, 19–43.
15.
De BergMCheongOvan KreveldM, et al. (2008) Polygon triangulation. In Computational Geometry Algorithms and Applications. 3rd edition. Heidelberg, Berlin: Springer, 45–61.
16.
De BergMCheongOvan KreveldM, et al. (2008) Delaunay triangulations. In Computational Geometry Algorithms and Applications. 3rd edition. Heidelberg, Berlin: Springer, 191–218.
17.
De BergMCheongOvan KreveldM, et al. (2008) Visibility graphs. In Computational Geometry Algorithms and Applications. 3rd edition. Heidelberg, Berlin: Springer, 323–333.
18.
De FilippiFCocinaGGMartinuzziC (2020) Integrating different data sources to address urban security in informal areas. The case study of Kibera, Nairobi. Sustainability12(6): 2437. DOI: 10.3390/su12062437.
19.
DijkstraEW (1959) A note on two problems in connexion with graphs. Numerische Mathematik1: 269–271. DOI: 10.1007/BF01386390.
20.
Fisher-GewirtzmanD (2017) The association between perceived density in minimum apartments and spatial openness index three-dimensional visual analysis. Environment and Planning B: Urban Analytics and City Science44(4): 764–795. DOI: 10.1177/0265813516657828.
21.
Fisher-GewirtzmanD (2018) Integrating ‘weighted views’ to quantitative 3D visibility analysis as a predictive tool for perception of space. Environment and Planning B: Urban Analytics and City Science45(2): 345–366. DOI: 10.1177/0265813516676486.
HonmaYKuritaOSuzukiA (2009) An analysis of urban landscapes with respect to solid angles based on computational geometry algorithms. Journal of Architecture and Planning74(643): 2035–2042, [In Japanese]. DOI: 10.3130/aija.74.2035.
24.
Hosseini AlamdariADaneshjooKYeganehM (2022) New algorithms for generating isovist field and isovist measurements. Environment and Planning B: Urban Analytics and City Science49(9): 2331–2344. DOI: 10.1177/23998083221083680.
25.
HowardAMatarićMJSukhatmeGS (2002) An incremental self-deployment algorithm for mobile sensor networks. Autonomous Robots13: 113–126. DOI: 10.1023/A:1019625207705.
26.
HuangC-FTsengY-C (2005) The coverage problem in a wireless sensor network. Mobile Networks and Applications10: 519–528. DOI: 10.1007/s11036-005-1564-y.
27.
ImaiKFujiiA (2007) A study on Voronoi diagrams with two-dimensional obstacles. Journal of the City Planning Institute of Japan42.3(3): 457–462, [In Japanese]. DOI: 10.11361/journalcpij.42.3.457.
28.
ImaiKFujiiA (2008) An approximate solution of restricted Weber problems with weighted regions. Journal of the City Planning Institute of Japan43.3(3): 85–90, [In Japanese]. DOI: 10.11361/journalcpij.43.3.85.
29.
InglisNCVukomanovicJCostanzaJ, et al. (2022) From viewsheds to viewscapes: Trends in landscape visibility and visual quality research. Landscape and Urban Planning224: 104424. DOI: 10.1016/j.landurbplan.2022.104424.
30.
JohanesMAtmodiwirjoP (2015) Visibility analysis of hospital inpatient ward. International Journal of Technology6(3): 400–409. DOI: 10.14716/ijtech.v6i3.1458.
31.
KimGKimAKimY (2019) A new 3D space syntax metric based on 3D isovist capture in urban space using remote sensing technology. Computers, Environment and Urban Systems74: 74–87. DOI: 10.1016/j.compenvurbsys.2018.11.009.
32.
KoutsolamprosPSailerKVaroudisT, et al. (2019) Dissecting visibility graph analysis: the metrics and their role in understanding workplace human behaviour. In Proceedings of the 12th International Space Syntax Symposium (12 SSS). Beijing, China, 9–11 July 2019.
33.
KrukarJManivannanCBhattM, et al. (2021) Embodied 3D isovists: a method to model the visual perception of space. Environment and Planning B: Urban Analytics and City Science48(8): 2307–2325. DOI: 10.1177/2399808320974533.
34.
LeeDT (1983) Visibility of a simple polygon. Computer Vision, Graphics, and Image Processing22(2): 207–221. DOI: 10.1016/0734-189X(83)90065-8.
35.
LeeJIkedaYHottaK (2019) Visibility heat map of 3D isovist. In Proceedings of the 24th International Conference of the Association for Computer-Aided Architectural Design Research in Asia (CAADRIA), Hong Kong, China, 341–350.
36.
MiyazakiS (2019) Development of system for 3D isovist graph analysis. Journal of Architecture and Planning84(765): 2369–2377, [In Japanese]. DOI: 10.3130/aija.84.2369.
37.
NubaniLWinemanJ (2022) Using isovists in measuring surveillance and expected guardianship in residential neighborhood property crimes. ISPRS International Journal of Geo-Information11(11): 544. DOI: 10.3390/ijgi11110544.
38.
OkabeABootsBSugiharaK, et al. (2000) Poisson Voronoi diagrams. In Spatial Tessellations Concepts and Applications of Voronoi Diagrams. 2nd edition. Chichester, England: Wiley, 291–410.
39.
OstwaldMJDawesMJ (2013) Using isovists to analyse architecture: methodological Considerations and new Approaches. The International Journal of the Constructed Environment3: 85–106. DOI: 10.18848/2154-8587/CGP/v03i01/37373.
40.
O’SullivanDTurnerA (2001) Visibility graphs and landscape visibility analysis. International Journal of Geographical Information Science15(3): 221–237. DOI: 10.1080/13658810151072859.
41.
RahimbakhshHKohansalMETarkashvandA, et al. (2022) Multi-objective optimization of natural surveillance and privacy in early design stages utilizing NSGA-II. Automation in Construction143: 104547. DOI: 10.1016/j.autcon.2022.104547.
42.
RanaS (2006) Isovist Analyst – an Arcview extension for planning visual surveillance. In Proceedings of ESRI International User Conference. Redlands, CA, USA, 7–11 August 2006.
43.
ShenYLawSKarimiK (2019) Measuring visibility to urban functions with Social Media data. In: DuanJ (ed) Proceedings of the 12th International Space Syntax Symposium (12 SSS). Beijing, China. 8–3 July 2019.
44.
SnopkováDDe CockLJuříkV, et al. (2023) Isovists compactness and stairs as predictors of evacuation route choice. Scientific Reports13: 2970. DOI: 10.1038/s41598-023-29944-8.
45.
SuleimanWJoliveauTFavierE (2013) A new algorithm for 3D isovists. In: TimpfSLaubeP (eds) Advances in Spatial Data Handling. Advances in Geographic Information Science Book Series. Berlin, Heidelberg: Springer. DOI: 10.1007/978-3-642-32316-4_11.
46.
TabataSAraiTHommaK, et al. (2019) The influence of walking environments on walking tracks through reproduction of desire paths. Journal of the City Planning Institute of Japan54(3): 1562–1569, [In Japanese]. DOI: 10.11361/journalcpij.54.1562.
47.
TabataSAraiTHonmaK, et al. (2023) Method for constructing cost-effective networks by mimicking human walking track superposition. Journal of Asian Architecture and Building Engineering22(2): 542–555. DOI: 10.1080/13467581.2022.2047056.
48.
TurnerA (2001) Depthmap A program to perform visibility graph analysis. In Proceedings of the 3rd International Space Syntax Symposium. Atlanta, GA, USA, 31.
49.
TurnerADoxaMO’SullivanD, et al. (2001) From isovists to visibility graphs: a methodology for the analysis of architectural space. Environment and Planning B: Planning and Design28(1): 103–121. DOI: 10.1068/b2684.
XiaG (2013) The stretch factor of the Delaunay triangulation is less than 1.998. SIAM Journal on Computing42(4): 1620–1659. DOI: 10.1137/110832458.
52.
XiangLPapastefanouGNgE (2021) Isovist Indicators as a means to relieve pedestrian psycho-physiological stress in Hong Kong. Environment and Planning B: Urban Analytics and City Science48(4): 964–978. DOI: 10.1177/2399808320916768.
53.
YinJCarswellJD (2013) Spatial search techniques for mobile 3D queries in sensor web environments. ISPRS International Journal of Geo-Information2(1): 135–154. DOI: 10.3390/ijgi2010135.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
