【读书笔记】算法漫步 第14章

问题13 凸包计算

凸包计算问题：在平面上给定一组点，如何生成一个包含全部点的最小凸包。

凸包是满足如下条件的多边形：连接多边形中任意两点（包括边界上的点）的直线段完全位于多边形内部（包括边界）。最小是指：在保持凸多边形性质不变的前提下，若缩小该图形，则给定的点中至少有一个位于外部。

凸包（Convex Hull）是一个计算几何（图形学）中的概念。

理解凸包算法需要解析几何和计算几何的数学知识。计算机不过是实现这些算法罢了。

本章首先介绍了一个蛮力算法，穷举所有线段，判断其余n-2是否在线段的同一个半平面中。

然后介绍一个效率较高的贪心算法，利用点的坐标之间的关心，结合计算几何的数学知识，然后用上，尝试，纠错，排序加栈等算计知识，提高极大提升求解效率。

【作者感受】

凸包计算在各种算法书中必有。是一个结合数学和算法设计两类知识的代表性问题，非常能体现出计算机专业的特色。

凸包计算，在很多算法竞赛中，都有题目。

当然，图形计算中有大量的问题需要用到凸包计算，凸包算法是计算几何领域最早的成果之一。