卷包裹法。
就是从最下,然后最左(注意顺序) 的点逐个找每个对于当前点最左的点。
找最左边点的方法:对于 当前已找到最左的点 和 当前的点 求叉积。如果叉积<0 就代表当前的点 比 当前已找到最左的点更左。
顺便说说叉积吧。
叉积的意义就是两个向量的叉积是两个向量所构成的平行四边形的有向面积。一定注意,叉积是有向的。
于是,叉积有了一些非常优良的性质。
1、叉积可以求面积。(定义...)
2、叉积可以判断两个向量的位置关系。(有向性)
我们主要用的是第二条性质。
如果两个向量叉积(a->b a->c)为正,代表c在b的顺时针方向。否则在逆时针方向。只能处理向量夹角<π/2 的情况。
但是我们的卷包裹法不会出现这种情况。因为我们找最左点时会过滤掉夹角>π/2。
求叉积公式:x1*y2-x2*y1