二维空间中的可视性算法概览

"《平面中的可见性算法》是一本深入探讨二维空间中可见性问题解决方法的书籍。书中涵盖了从简单多边形到带有洞的多边形的各种可见性算法，包括点可见性、弱可见性、最短路径、可见性图理论、链接路径以及路径查询等相关主题。全书包含超过300个图表和数百个练习题，适合计算机图形学、计算几何、机器人学以及几何图论领域的研究生和研究人员阅读，也可作为相关领域研究者的参考书。作者Subir Kumar Ghosh是计算机科学领域的教授。" 本书首先介绍了可见性的基本概念，包括对可见性的定义、多边形的分类、渐近复杂度分析、三角剖分以及艺术画廊问题。接着，详细阐述了点可见性问题，包括在简单多边形和有孔多边形中计算点的可见性，并提出了线性时间复杂度的算法。此外，还讨论了识别从一点可见的简单多边形的方法。 接下来，作者探讨了弱可见性和最短路径问题。弱可见性是指视线可以部分穿过物体，而不会被完全阻挡。书中提到了弱可见性的特征、计算简单多边形中弱可见性以及有孔多边形中弱可见性的算法。同时，还介绍了如何构建最短路径树，并讨论了在不同类型的可见性多边形中计算最短路径的方法。 LR-可见性（Left-Right可见性）是另一个重要的主题，它涉及视线从左到右的连续可见性。书中详细描述了LR-可见性的特性，以及如何在LR-可见性多边形中行走和计算最短路径。此外，还讲解了利用LR-可见性计算最短路径树的算法。 可见性图是表示物体间可视关系的图论工具。书中介绍了如何构建简单多边形和有孔多边形的可见性图，以及最坏情况和输出敏感的算法。此外，还讨论了凸孔和非凸孔的切线可见性图的计算。 在可见性图理论部分，书中研究了识别简单多边形的可见性图的必要条件和测试方法，以及特殊类别的可见性图的特征。此外，还涉及了一些顶点-边可见性图的性质，以及最大团和最大隐藏顶点集的计算。 链接路径是另一种形式的路径，它允许视线部分被物体遮挡。书中讲述了如何在简单和有孔多边形中找到最小链接路径，并计算链接中心和半径。此外，还讨论了在凸多边形和非凸多边形之间找到最小嵌套多边形的方法。 最后，路径查询部分涵盖了射线射击查询、点在多边形内的可见性查询，以及在简单多边形内两点间的最短路径和链接路径查询。这些查询算法的时间复杂度在不同情况下有所不同。 《平面中的可见性算法》提供了丰富的理论知识和实用算法，对于理解并解决二维空间中的复杂可见性问题具有很高的价值。无论是学术研究还是实际应用，这本书都提供了一个全面且深入的资源。