计算几何算法：分治法解决凸包问题

"2015300005_黄晓阳_计算几何算法与应用大作业1" 这篇作业主要讨论了计算几何中的一个关键问题——凸包问题，并介绍了利用分治法来解决这一问题的基本策略。以下是详细的知识点解析： 1. 凸包问题概述： 凸包问题是指在给定的一组点集中找到一个最小的凸多边形，该多边形包含了所有的点。这个问题在计算机图形学、机器学习、优化等领域都有重要应用。在图1的示例中，凸包就像一个橡皮筋包裹住所有点形成的边界。 2. 分治法的基本原理： 分治法是一种解决复杂问题的常用策略，它将大问题分解为若干个规模较小、相互独立且与原问题结构相似的子问题，然后递归地解决这些子问题，最后将子问题的解合并得到原问题的解。这种方法通常适用于数据规模可划分，且子问题可以并行处理的情况。 3. 用分治法求解凸包问题策略： 在解决凸包问题时，首先将点集映射到二维坐标系中。通过找到x轴或y轴上的最大值和最小值点作为分割点，将点集分为两部分。例如，选取最大x值点P1和最小x值点P2，可以得到上下两个子集。然后，分别在每个子集中找出距离分割线最远的点，如P3和P4，通过连接这些点形成新的分割线，如图4所示。通过不断分割和排除已经被包围的点，递归地找到所有凸包顶点。 4. 算法伪代码： 算法CONVEXHULL(P)接收一个平面点集P作为输入，输出由CH(P)的所有顶点按顺时针顺序组成的列表。其基本步骤包括： - 首先根据x坐标对点集进行排序。 - 然后，使用分治法策略，递归地找到凸包上的点，逐步构建完整的凸包。 这个算法的核心在于递归地分割点集，每次分割都确保在新的子问题中减少需要考虑的点的数量，直到问题规模足够小以至于可以直接得出答案。在实际编程实现时，还需要考虑到特殊情况的处理，例如点集完全在一条直线上或点集为空等。 这个作业提供了关于凸包问题和分治法的理论介绍，以及一个基于分治的凸包算法的伪代码描述，对于理解计算几何中的凸包问题及其解决方法具有很好的教学价值。