100种算法【Python版】第37篇—— Jarvis March算法
本文目录
- 1 算法说明
- 2 计算凸包的示例
- 3 python代码
- 4 算法应用
1 算法说明
Jarvis March算法，通常被称为“礼品包装”算法，是由R. L. Jarvis在1973年提出的。它的名称来源于礼品包装的过程：想象你将一个礼物放在桌子上，并用绳子围绕它，绳子最终形成的形状就是礼物的凸包。这个算法的设计目标是简单直观，通过逐步包围点集来构建凸包，适合小规模数据集和教学使用。
算法的原理
Jarvis March算法的核心思想是通过逐步选择边界点来构建凸包。具体步骤如下：
- 选择起始点：从所有点中选择一个起始点，通常是y坐标最小的点（如果有多个，选择x坐标最小的点）。
- 寻找下一个点：从当前点出发，遍历所有其他点，选择一个能形成凸包边界的下一个点。
- 重复步骤：将选中的点作为新的当前点，继续寻找下一个点，直到回到起始点。
该算法保证每一步都能找到下一个边界点，从而逐步构建出完整的凸包。
算法的完整流程
- 初始化：选择一个点作为起始点（y坐标最小的点）。
- 设置当前点：将当前点设置为起始点。
- 循环：
- 找到当前点的下一个点（