Python 凸包算法

#-*- coding:utf-8 -*-
‘‘‘
凸包问题是指在n个点中，寻找一个凸多边形，使所有的点在凸多边形的边界或者内部。这是一个很有意思的计算机图形学问题，一种常用的解法是Graham扫描法，运行时间为O（nlgn）。
维基百科地址：https://en.wikipedia.org/wiki/Graham_scan
笔者拿processing语言对整个算法过程进行了模拟，上动态图：
![processing语言模拟Graham扫描法]（“模拟Graham扫描法“）
注意processing拿左上为（00）原点，与一般数学的原点位置不同。
从动态图上可以看出整个算法分三个部分：
**1、寻找y轴最小的点，如果y轴位置是相同的，那个找x轴位置最小的，称之为基准点。**
**2、计算1中找到基准点与其他点的极角（即过此2点的直线与x轴正方向的夹角，代码中以弧度表示），将这些点按极角的大小正序排列。**
**3、进行基准点与2中点的连线迭代，对新连线的点计算其是否符合凸多边形的定义，如果不满足舍弃此点。判断的方法是计算三点组成线段的叉乘，值为正表示满足条件。**
叉乘维基百科地址：https://zh.wikipedia.org/zh-cn/%E5%90%91%E9%87%8F%E7%A7%AF
‘‘‘

import sys
##sys.path.append（“.“）
##sys.path.append（“..“）
##sys.path.append（“../..“）
import math
import time
import random

#获取基准点的下标
def get_leftbottompoint（p）:
    k = 0
    for i in range（1 len（p））: