凸包
凸包
参考：博客
凸包问题是指在n个点中，寻找一个凸多边形，使所有的点在凸多边形的边界或者内部。
首先，x轴最大最小点都在凸包边界上，y轴最大最小点都在凸包边界上。面试官提醒可以使用扫描法，就是假设使用一根绳子绕逆时针方向旋转，被绕到的都在凸包边界上。
思路简单清晰，但是在具体实现方面遇到了困难。
问题：
- 怎么模拟绕的过程
- 如何找到绕线的起始点；
- 即如何找到绕线的时候碰到的第一个点；
- 怎么判断这个点在不在凸包里面；
方法：
- 第一个点可以选择最大最小点，这个相对简单；
- 绕线的时候，线与x轴的夹角是从小到大变化的；所以当新加入一个点的时候，需要计算这个点到所有点的极角并排序；
- 可以使用三个点构成的两条线段的叉乘来判断；
极角排序：
用来确定点的处理顺序
叉乘判断三角形方向
利用矢量叉积判断是逆时针还是顺时针，参考 博客
设A(x1,y1),B(x2,y2),C(x3,y3),则三角形两边的矢量分别是：
AB=(x2-x1,y2-y1), AC=(x3-x1,y3-y1)
则AB和AC的叉积为：(2*2的行列式)
|x2-x1, y2-y1|
|x3-x1, y3-y1|
值为：\((x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)\)
利用右手法则进行判断：
- 如果AB*AC>0,则三角形ABC是逆时针的
- 如果AB*AC<0,则三角形ABC是顺时针的
- 如果…… =0，则说明三点共线，
伪代码：
参考两位大神的博客:
- https://my.oschina.net/pangyuke/blog/754603 ，在判断的时候有一点小问题；
- https://blog.csdn.net/john_bian/article/details/85221039
import math
def get_leftbottom_point(p):
k = 0
for i in range(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'])
def cal_arc(p1,p0):
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(p,k):
p2 = []
for i in range(len(p)):
p2.append({"indx":i,"arc":cal_arc(p[i],p[k])})
p2.sort(key=lambda x: x.get("arc",0))
p_out = []
for i in range(len(p2)):
p_out.append(p[p2[i]["indx"]])
return p_out
def graham_scan(p):
k = get_leftbottom_point(p)
p_sort = sort_points(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 range(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 range(len(p_result)-1,-1,-1):
if p_result[i] == None:
p_result.pop()
return p_result
if __name__=="__main__":
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},{"x":1.5,"y":1.5}]
print(graham_scan(ps))1、机器学习相关
2、老梁
3、神经网络与机器学习 笔记—基本知识点（下）
4、（转）Monte Carlo method 蒙特卡洛方法
5、macbook使用美化工具在屏幕展示出常查信息