如果用一根没有凹陷的橡皮筋围住所有位置,得到的边界由最外侧的一些点组成。内部点不会成为转角,同一条直边中间的点也可以省略。
本例只求二维凸包,输入点互不相同。先按横坐标再按纵坐标排序,分别构造下侧和上侧边界;连续三点不是严格左转时移除中间点,最后合并两条链,首点不重复写在末尾。
本例的输入和输出
十个输入点为[(-1, 5), (0, 0), (0, 2), (0, 6), (4, 3), (4, 5), (8, 0), (8, 9), (9, 7), (10, 1)]。
凸包顶点按逆时针顺序:[(-1, 5), (0, 0), (8, 0), (10, 1), (9, 7), (8, 9), (0, 6)] 每条有向边对应全部输入点的叉积: (-1, 5)→(0, 0) | [0, 0, 2, 6, 23, 25, 40, 49, 52, 51] (0, 0)→(8, 0) | [40, 0, 16, 48, 24, 40, 0, 72, 56, 8] (8, 0)→(10, 1) | [19, 8, 12, 20, 10, 14, 0, 18, 13, 0] (10, 1)→(9, 7) | [62, 61, 59, 55, 34, 32, 13, 4, 0, 0] (9, 7)→(8, 9) | [22, 25, 23, 19, 14, 12, 9, 0, 0, 4] (8, 9)→(0, 6) | [5, 48, 32, 0, 36, 20, 72, 0, 19, 70] (0, 6)→(-1, 5) | [0, 6, 4, 0, 7, 5, 14, 5, 8, 15] 凸包面积74,轴对齐包围盒面积99。
表格中的编号只标识当前例子的元素,不应把对象身份、数组下标与计算数值混为一谈。阅读时先核对输入和边界,再沿记录检查每一步;空结果表示规则下没有可用项,并不是默认返回数值零。
复核与适用条件
输出顶点应按逆时针顺序围成凸形,每个输入点都在所有边的左侧或边上。面积可以用相邻顶点的叉积和求出;包围盒面积通常更大,不能用它替代实际凸包面积。
凸包会填平凹口,也可能包含很大的空白区域,因此不适合直接代表所有不规则地形的碰撞范围。它提供一个外层包围形状,是否还需要更精细的检查取决于实际用途。
练习时先独立复算一小段,再检查整体结果是否满足文中条件。遇到差异应保留中间记录并定位第一处不一致,而不是只调整最后答案。更换输入或操作规则后,需要重新计算,原记录只对这一例负责。
