分类：多边形面积

2020
09-27

Python求凸包及多边形面积教程

一般有两种算法来计算平面上给定n个点的凸包：Graham扫描法(Graham'sscan)，时间复杂度为O(nlgn)；Jarvis步进法(Jarvismarch)，时间复杂度为O(nh)，其中h为凸包顶点的个数。这两种算法都按逆时针方向输出凸包顶点。Graham扫描法用一个栈来解决凸包问题，点集Q中每个点都会进栈一次，不符合条件的点会被弹出，算法终止时，栈中的点就是凸包的顶点(逆时针顺序在边界上)。算法步骤如下图：importsysimportmathimporttimeimportr... 继续阅读 >