Delaunay三角与凸包的转化关系：二维到三维示例

Delaunay三角剖分是一种在几何学和计算机图形学中广泛使用的网格划分技术，尤其对于三维空间中的复杂几何对象和区域分割至关重要。它最初由René Descartes在19世纪提出，但真正引起广泛关注是在20世纪80年代，Edelsbrunner和Seidel在研究Voronoi图和超平面的关系时发现其与凸包有深刻联系。这种联系体现在所谓的Lifting Map概念中，它揭示了d维空间中的Delaunay三角剖分与一维空间中的凸包存在一种转换关系。 Lifting Map的关键在于将d维空间中的点集提升到更高维度，例如，二维点集通过增加一个额外的坐标轴，形成三维空间中的点集。在这个过程中，每个原点的升高点不仅保留原有的坐标，还添加了一个新的坐标，使得原有的Delaunay三角形在新空间中可以映射为更复杂的几何形状的凸包。这个过程有助于理解Delaunay三角剖分如何影响和控制凸包的形状和特性。 在二维情况下，如果有一个点集在抛物面上，通过向垂直方向投射，我们可以观察到二维Delaunay三角剖分如何扩展形成三维空间中的凸包。这种关系对于理解Delaunay三角剖分的性质及其在实际应用中的约束条件至关重要，例如在地形建模、计算机辅助设计（CAD）以及地理信息系统（GIS）中，对特定点、线段和平面片的限制可能会影响剖分的质量和效率。 作者杨钦在本书中对二维平面和三维空间下的限定Delaunay三角剖分技术进行了深入研究，提出了一种新颖的算法，能够处理包括任意点、线段和平面片在内的复杂约束条件。这些算法不仅能够生成满足特定条件的Delaunay三角网格，还能有效控制网格的细化程度和质量，确保生成的网格结构既简洁又适应实际应用需求。 这本书是计算机科学和技术领域的重要参考资料，不仅适合科技人员，也适用于高等教育机构的学生和教师。它为理解Delaunay三角剖分的理论基础、算法设计和实际应用提供了详尽的指导，对于提高空间数据处理和几何建模能力具有重要意义。