如何用Python编写求凸包和多边形面积的计算教程？

本文共计1745个文字，预计阅读时间需要7分钟。

Graham 扫描法（Graham's scan）和 Jarvis 步进法（Jarvis march）是两种计算凸包的算法。Graham 扫描法的时间复杂度为 O(nlgn)，而 Jarvis 步进法的时间复杂度为 O(nh)，其中 h 是凸包顶点的个数。这两种算法都基于逆时针顺序。

一般有两种算法来计算平面上给定n个点的凸包：Graham扫描法(Graham's scan)，时间复杂度为O(nlgn)；Jarvis步进法(Jarvis march)，时间复杂度为O(nh)，其中h为凸包顶点的个数。这两种算法都按逆时针方向输出凸包顶点。

Graham扫描法

用一个栈来解决凸包问题，点集Q中每个点都会进栈一次，不符合条件的点会被弹出，算法终止时，栈中的点就是凸包的顶点(逆时针顺序在边界上)。