Visibility Algorithms in the Plane
Visibility Algorithms in the Plane
复制标题
DOI：
10.1017/cbo9780511543340.010
复制
发表时间：
2007-03
期刊：
影响因子：
3.3
通讯作者：
S. Ghosh
中科院分区：
文献类型：
--
作者：
S. Ghosh
人类观察者可以毫不费力地识别存在于环境中的几何对象的可见部分。然而，即使对于高速计算机，从涉及数千个对象的视点计算对象的可见部分也是耗时的任务。为了解决这样的可见性问题，已经设计了有效的算法。这本书提出了一些在两个维度的可见性算法。具体来说，点的可见性，弱可见性，最短路径，可见性图，链接路径，和可见性查询的基本算法都进行了讨论。通过引理和定理，还建立了几个几何性质。超过300个数字和数百个练习，这本书是理想的研究生和研究人员在计算几何领域。它也将是有用的参考研究人员工作的算法，机器人技术，计算机图形学和几何图论，和一些算法从书中可以使用的第一门课程在计算几何。
A human observer can effortlessly identify visible portions of geometric objects present in the environment. However, computations of visible portions of objects from a viewpoint involving thousands of objects is a time-consuming task even for high-speed computers. To solve such visibility problems, efficient algorithms have been designed. This book presents some of these visibility algorithms in two dimensions. Specifically, basic algorithms for point visibility, weak visibility, shortest paths, visibility graphs, link paths, and visibility queries are all discussed. Several geometric properties are also established through lemmas and theorems. With over 300 figures and hundreds of exercises, this book is ideal for graduate students and researchers in the field of computational geometry. It will also be useful as a reference for researchers working in algorithms, robotics, computer graphics, and geometric graph theory, and some algorithms from the book can be used in a first course in computational geometry.