Abstract
Given a polygonal domain (or polygon with holes) in the plane, we study the problem of computing the visibility polygon of any query point. As a special case of visibility problems, we also study the ray-shooting problem of finding the first point on the polygon boundaries that is hit by any query ray. These are fundamental problems in computational geometry and have been studied extensively. We present new algorithms and data structures that improve the previous results.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Agarwal, P., Sharir, M.: Ray shooting amidst convex polygons in 2D. Journal of Algorithms 21(3), 508–519 (1996)
Aronov, B., Guibas, L., Teichmann, M., Zhang, L.: Visibility queries and maintenance in simple polygons. Discrete and Computational Geometry 27(4), 461–483 (2002)
Bar-Yehuda, R., Chazelle, B.: Triangulating disjoint Jordan chains. International Journal of Computational Geometry and Applications 4(4), 475–481 (1994)
Bose, P., Lubiw, A., Munro, J.: Efficient visibility queries in simple polygons. Computational Geometry: Theory and Applications 23(3), 313–335 (2002)
Chazelle, B., Edelsbrunner, H., Grigni, M., Gribas, L., Hershberger, J., Sharir, M., Snoeyink, J.: Ray shooting in polygons using geodesic triangulations. Algorithmica 12(1), 54–68 (1994)
Chazelle, B., Guibas, L.: Visibility and intersection problems in plane geometry. Discrete and Computational Geometry 4, 551–589 (1989)
Chen, D.Z., Wang, H.: A nearly optimal algorithm for finding L 1 shortest paths among polygonal obstacles in the plane. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 481–492. Springer, Heidelberg (2011)
Chen, D.Z., Wang, H.: Computing the visibility polygon of an island in a polygonal domain. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 218–229. Springer, Heidelberg (2012)
Guibas, L., Hershberger, J., Leven, D., Sharir, M., Tarjan, R.: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica 2(1-4), 209–233 (1987)
Hershberger, J., Suri, S.: A pedestrian approach to ray shooting: Shoot a ray, take a walk. Journal of Algorithms 18(3), 403–431 (1995)
Inkulu, R., Kapoor, S.: Planar rectilinear shortest path computation using corridors. Computational Geometry: Theory and Applications 42(9), 873–884 (2009)
Inkulu, R., Kapoor, S.: Visibility queries in a polygonal region. Computational Geometry: Theory and Applications 42(9), 852–864 (2009)
Kapoor, S., Maheshwari, S., Mitchell, J.: An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane. Discrete and Computational Geometry 18(4), 377–383 (1997)
Lee, D., Preparata, F.: Euclidean shortest paths in the presence of rectilinear barriers. Networks 14(3), 393–410 (1984)
Lu, L., Yang, C., Wang, J.: Point visibility computing in polygons with holes. Journal of Information and Computational Science 8(16), 4165–4173 (2011)
Nouri, M., Ghodsi, M.: Space–query-time tradeoff for computing the visibility polygon. In: Deng, X., Hopcroft, J.E., Xue, J. (eds.) FAW 2009. LNCS, vol. 5598, pp. 120–131. Springer, Heidelberg (2009)
Pocchiola, M.: Graphics in flatland revisited. In: Gilbert, J.R., Karlsson, R. (eds.) SWAT 1990. LNCS, vol. 447, pp. 85–96. Springer, Heidelberg (1990)
Pocchiola, M., Vegter, G.: Pseudo-triangulations: Theory and applications. In: Proc. of the 12th Annual Symposium on Computational Geometry, pp. 291–300 (1996)
Pocchiola, M., Vegter, G.: Topologically sweeping visibility complexes via pseudotriangulations. Discrete and Computational Geometry 16(4), 419–453 (1996)
Pocchiola, M., Vegter, G.: The visibility complex. International Journal of Computational Geometry and Applications 6(3), 279–308 (1996)
Zarei, A., Ghodsi, M.: Query point visibility computation in polygons with holes. Computational Geometry: Theory and Applications 39(2), 78–90 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, D.Z., Wang, H. (2013). Visibility and Ray Shooting Queries in Polygonal Domains. In: Dehne, F., Solis-Oba, R., Sack, JR. (eds) Algorithms and Data Structures. WADS 2013. Lecture Notes in Computer Science, vol 8037. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40104-6_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-40104-6_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40103-9
Online ISBN: 978-3-642-40104-6
eBook Packages: Computer ScienceComputer Science (R0)