Sage Journals: Discover world-class research

Abstract

When a person moves, the set of objects in their visual range changes. Hence, the set of objects perceived from a specific range of locations may be considered as a signature (possibly non-unique) of this region and be used for the localization of this person. In the case of fixed objects, the number of regions with a set of specific visible objects is limited. A verbal description containing references to elements of this set of visible objects could then be used to localize a person in the space. This paper proposes an approach for decomposing a space into regions that are characterized by such sets of visible objects. In our approach, at least a portion of partial surfaces of an object must be visible (beyond single points) to make part of the signature. Our method calculates two-dimensional visibility polygons for a portion of an object’s surface. Overlaying these polygons, we partition the space in regions of visibility signatures. The approach has been implemented, and we demonstrate how to represent space by qualitative locations using these visibility signatures. We further show how this representation can be used to locate a person within a space by a set of visible objects.

Keywords

Visibility polygon space decomposition qualitative localization isovist

Get full access to this article

View all access options for this article.

References

Aronov

Guibas

Teichmann

, et al. (2002) Visibility queries and maintenance in simple polygons. Discrete and Computational Geometry 27(4): 461–483.

Benedikt

(1979) To take hold of space: Isovists and isovist fields. Environment and Planning B: Planning and Design 6(1): 47–65.

Bose

Lubiw

Munro

(2002) Efficient visibility queries in simple polygons. Computational Geometry 23(3): 313–335.

Chen

Daescu

(1998) Maintaining visibility of a polygon with a moving point of view. Information Processing Letters 65(5): 269–275.

Chen

Wang

(2015) Weak visibility queries of line segments in simple polygons. Computational Geometry 48(6): 443–452.

Chvátal

(1975) A combinatorial theorem in plane geometry. Journal of Combinatorial Theory, Series B 18(1): 39–41.

Guibas

Motwani

Raghavan

(1995) The robot localization problem. In: Proceedings of 1st Workshop on Algorithmic Foundations of Robotics. Citeseer, pp.269–282.

Keil

(1985) Decomposing a polygon into simpler components. SIAM Journal on Computing 14(4): 799–817.

Kray

Kortuem

(2004) Interactive positioning based on object visibility. In: Brewster S and Dunlop M (eds) Mobile Human-Computer Interaction—MobileHCI 2004. Berlin: Springer, pp.276–287.

10.

Lien

Amato

(2006) Approximate convex decomposition of polygons. Computational Geometry 35(1): 100–123.

11.

Lynch

(1960) The Image of the City. Cambridge: MIT Press, vol. 11.

12.

Majic

Naghizade

Winter

, et al. (2020) RIM: A ray intersection model for the analysis of the between relationship of 2D spatial objects. International Journal of Geographical Information Science 35(5): 1–23.

13.

Nahar

Sahni

(1988) Fast algorithm for polygon decomposition. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 7(4): 473–483.

14.

O’Rourke

(1983) An alternate proof of the rectilinear art gallery theorem. Journal of Geometry 21(1): 118–130.

15.

O’Rourke

(1987) Art Gallery Theorems and Algorithms, Volume 57. Oxford: Oxford University Press.

16.

Richter

Winter

(2014) Landmarks. Springer Cham Heidelberg New York Dordrecht London 10: 973–978.

17.

Toussaint

Avis

(1981) An optimal algorithm for determining the visibility of a polygon from an edge. IEEE Transactions on Computers 30(12): 910–914.

18.

Turner

Doxa

O’Sullivan

, et al. (2001) From isovists to visibility graphs: A methodology for the analysis of architectural space. Environment and Planning B: Planning and Design 28(1): 103–121.

19.

Turner

Penn

(2002) Encoding natural movement as an agent-based system: An investigation into human pedestrian behaviour in the. Environment and Planning B: Planning and Design 29(4): 473–490.

20.

Van Kreveld

Schwarzkopf

de Berg

, et al. (2000) Polygon triangulation. In: Computational Geometry Algorithms and Applications. Berlin: Springer, pp.45–61.

21.

Wiener

Franz

Rossmanith

, et al. (2007) Isovist analysis captures properties of space relevant for locomotion and experience. Perception 36(7): 1066–1083.

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.

0.00 MB

0.44 MB