凸包问题是指在n个点中，寻找一个凸多边形，使所有的点在凸多边形的边界或者内部。这是一个很有意思的计算机图形学问题，一种常用的解法是Graham扫描法，运行时间为O(nlgn)。
笔者拿processing语言对整个算法过程进行了模拟，上动态图：
注意processing拿左上为(0,0)原点，与一般数学的原点位置不同。
从动态图上可以看出整个算法分三个部分：
1、寻找y轴最小的点，如果y轴位置是相同的，那个找x轴位置最小的，称之为基准点。
2、计算1中找到基准点与其他点的极角(即过此2点的直线与x轴正方向的夹角，代码中以弧度表示)，将这些点按极角的大小正序排列。
3、进行基准点与2中点的连线迭代，对新连线的点计算其是否符合凸多边形的定义，如果不满足舍弃此点。判断的方法是计算三点组成线段的叉乘，值为正表示满足条件。
以下是python的算法实现
# -*- coding: utf-8 -*-
import math
#获取基准点的下标
def get_leftbottompoint(p):
k = 0
for i in xrange(1, len(p)):
if p[i]['y'] < p[k]['y'] or (p[i]['y'] == p[k]['y'] and p[i]['x'] < p[k]['x']):
k = i
return k
#叉乘计算方法
def multiply(p1, p2, p0):
return (p1['x'] - p0['x']) * (p2['y'] - p0['y']) - (p2['x'] - p0['x']) * (p1['y'] - p0['y'])
#获取极角，通过求反正切得出，考虑pi / 2的情况
def get_arc(p1, p0):
# 兼容sort_points_tan的考虑
if (p1['x'] - p0['x']) == 0:
if ((p1['y'] - p0['y'])) == 0:
return -1;
else:
return math.pi / 2
tan = float((p1['y'] - p0['y'])) / float((p1['x'] - p0['x']))
arc = math.atan(tan)
if arc >= 0:
return arc
else:
return math.pi + arc
#对极角进行排序
def sort_points_tan(p, k):
p2 = []
for i in xrange(0, len(p)):
p2.append({"index": i, "arc": get_arc(p[i], p[k])})
p2.sort(key=lambda k: (k.get('arc', 0)))
p_out = []
for i in xrange(0, len(p2)):
p_out.append(p[p2[i]["index"]])
return p_out
def graham_scan(p):
k = get_leftbottompoint(p)
p_sort = sort_points_tan(p, k)
p_result = [None] * len(p_sort)
p_result[0] = p_sort[0]
p_result[1] = p_sort[1]
p_result[2] = p_sort[2]
top = 2
for i in xrange(3, len(p_sort)):
#叉乘为正则符合条件
while (top >= 1 and multiply(p_sort[i], p_result[top], p_result[top - 1]) > 0):
top -= 1
top += 1
p_result[top] = p_sort[i]
for i in xrange(len(p_result) - 1, -1, -1):
if p_result[i] == None:
p_result.pop()
return p_result
#测试
ps = [{"x": 2, "y": 2}, {"x": 1, "y": 1}, {"x": 2, "y": 1}, {"x": 1.5, "y": 1.5}, {"x": 1, "y": 2}, {"x": 3, "y": 1.5},
{"x": 1.5, "y": 1.2}, {"x": 0.5, "y": 2}, {"x": 1.5, "y": 0.5}]
print graham_scan(ps)