艺术画廊问题与三角剖分：计算流体力学中的关键策略

"《看守与三角剖分——计算流体力学与传热学》一书的第三章探讨了多边形三角剖分在艺术画廊问题中的应用，也就是所谓的"画廊看守"问题。章节内容主要围绕以下几个关键知识点展开： 1. 艺术画廊问题：这是个经典的计算机图形学问题，旨在确定在给定的一个二维平面多边形（简单多边形，无自交且封闭）画廊内，最少需要安装多少台摄像机，并确定它们的理想位置，以确保整个画廊内的任何一点都在至少一台摄像机的视野范围内。 2. 看守与三角剖分：在这里，摄像机的角色比喻为“看守”，其位置对应于多边形内的一个点。三角剖分是指将一个多边形划分为若干互不重叠的小三角形的过程。这个过程对于确定摄像机覆盖区域至关重要，因为只要从任一点到摄像机的视线路径完全位于多边形内部，该点就被认为是被“看守”到的。 3. 简单多边形模型：为了简化问题，作者假设画廊可以用平面简单多边形模型表示，这样的模型避免了复杂的内部结构，便于摄像机布局的计算。 4. 算法与技术：涉及到了计算几何中的核心算法，如线段求交、子区域划分的叠合、布尔运算等，这些都是三角剖分过程中可能用到的基础技术。此外，还有诸如单调块划分、单调多边形的三角剖分等高级技巧，这些技术在实际应用中能够提高效率并优化解决方案。 5. 实际应用：章节不仅限于理论，还展示了这些理论在实际问题中的应用，例如铸造中的几何、数据库查询的正交区域查找、点定位算法以及光线跟踪中的排列与对偶等。 通过这一系列的阐述，读者可以深入理解多边形三角剖分在解决实际问题中的关键作用，以及它在计算流体力学与传热学等领域的潜在应用。同时，章节中的习题设计也有助于读者巩固所学知识，并提升解决实际问题的能力。"