计算几何：直线排列与对偶分析

"计算流体力学与传热学 陶文全" 本文主要讨论的是计算几何领域中的一个重要概念——排列（Arrangement），这是在处理直线、曲线等几何对象时经常遇到的数据结构。排列是由一系列直线或曲线在平面上的交点划分出的区域，每个区域都由边界线和顶点定义。陶文全教授在此基础上讲述了如何构建和操作这种数据结构，特别是如何高效地处理直线的排列。 在描述中提到了第8章的内容，即“排列与对偶：光线跟踪超采样”。其中第8.3节聚焦于“直线的排列”。直线的排列构建通常涉及以下几个步骤： 1. 构造包围框：首先需要创建一个包围框B(L)，这个包围框要足够大以包含所有直线L中的顶点。这个过程可以在O(n^2)的时间内完成。 2. 初始化双向链接边表结构：构建一个数据结构来表示由B(L)内的直线A(L)所限定的子区域划分。这是一个用于存储边、顶点和面的双向链接列表。 3. 逐线处理：对于每一条直线li，找到它与现有排列（当前的子区域划分）的边界相交的位置。这些交点会将原有的面f分割成两个新的面。 4. 面的分割：当找到交点时，将面f分割成两个新面，并为新产生的边和顶点创建相应的记录。同时更新原有记录的指针，确保它们正确指向新生成的元素。 5. 循环处理：直到所有直线都处理完毕，整个排列就被构造出来了。这个过程的时间复杂度与面的复杂度线性相关。 算法CONSTRUCTARRANGEMENT(L)概述了这个过程，它是一个递增式的算法，逐步添加直线并更新排列。算法的运行时间分析显示，构造包围框和初始化子区域划分的时间复杂度相对较低，而主要的时间消耗在于遍历每条直线并处理其与现有排列的交点。 计算几何是一门广泛的学科，涵盖了多个专题，如线段求交、多边形三角剖分、线性规划、正交区域查找和点定位等。在邓俊辉翻译的《计算几何——算法与应用》这本书中，作者们详细阐述了这些主题，并提供了相关算法的实现和分析，帮助读者深入理解计算几何的基本原理和应用。 该书的其他章节还涉及了如专题图叠合（用于计算线段的交点）、多边形的三角剖分（用于简化多边形处理）、线性规划（在几何问题中的应用）、kd-树和区域树（用于高维数据的快速查找）以及Voronoi图（用于确定点到几何对象的最近距离）等内容。这些工具和方法在计算机图形学、地理信息系统、机器人路径规划等领域都有广泛应用。