#-*-?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））:
???????