散落的地图点怎样围出最紧的凸边界：机制演算第11例

如果用一根没有凹陷的橡皮筋围住所有位置，得到的边界由最外侧的一些点组成。内部点不会成为转角，同一条直边中间的点也可以省略。

本例只求二维凸包，输入点互不相同。先按横坐标再按纵坐标排序，分别构造下侧和上侧边界；连续三点不是严格左转时移除中间点，最后合并两条链，首点不重复写在末尾。

本例的输入和输出

十个输入点为[(-2, -1), (-1, -2), (0, 0), (0, 6), (1, 8), (5, 8), (6, 7), (7, -2), (8, 0), (10, -2)]。

凸包顶点按逆时针顺序：[(-2, -1), (-1, -2), (10, -2), (6, 7), (5, 8), (1, 8), (0, 6)] 每条有向边对应全部输入点的叉积： (-2, -1)→(-1, -2) | [0, 0, 3, 9, 12, 16, 16, 8, 11, 11] (-1, -2)→(10, -2) | [11, 0, 22, 88, 110, 110, 99, 0, 22, 0] (10, -2)→(6, 7) | [104, 99, 82, 58, 41, 5, 0, 27, 10, 0] (6, 7)→(5, 8) | [16, 16, 13, 7, 4, 0, 0, 8, 5, 5] (5, 8)→(1, 8) | [36, 40, 32, 8, 0, 0, 4, 40, 32, 40] (1, 8)→(0, 6) | [3, 6, 6, 0, 0, 8, 11, 22, 22, 28] (0, 6)→(-2, -1) | [0, 9, 12, 0, 3, 31, 40, 65, 68, 86] 凸包面积85，轴对齐包围盒面积120。

表格中的编号只标识当前例子的元素，不应把对象身份、数组下标与计算数值混为一谈。阅读时先核对输入和边界，再沿记录检查每一步；空结果表示规则下没有可用项，并不是默认返回数值零。

复核与适用条件

输出顶点应按逆时针顺序围成凸形，每个输入点都在所有边的左侧或边上。面积可以用相邻顶点的叉积和求出；包围盒面积通常更大，不能用它替代实际凸包面积。

凸包会填平凹口，也可能包含很大的空白区域，因此不适合直接代表所有不规则地形的碰撞范围。它提供一个外层包围形状，是否还需要更精细的检查取决于实际用途。

练习时先独立复算一小段，再检查整体结果是否满足文中条件。遇到差异应保留中间记录并定位第一处不一致，而不是只调整最后答案。更换输入或操作规则后，需要重新计算，原记录只对这一例负责。