计算几何入门

• 计算几何入门
  • 一 向量
    • 1.叉积
      • a.定义
      • b.应用
  • 凸包
    • 寻找凸包
      • 算法1:Graham

一 向量

我认为唯一比较有用的东西是向量的叉积

1.叉积

a.定义

对于两个0起点开始，最终点为(a1,a2)和(b1,b2)的两个向量，其叉积为a1 * b2 - a2 * b1。

b.应用

可以判断两个向量的旋转方向：

假如A和B的叉积最终得到<0，那么说明A是逆时针旋转到B的，也可以说，B在A的左手边

若得到=0，那么这两个向量是共线的

若得到>0，那么A可以顺时针旋转得到B，也可以说，B在A的右手边

凸包

寻找凸包

算法1:Graham

算法流程：

1.找到一个在左下角的点（优先满足y坐标更小），令其为s

2.对于其他点，使用极角排序，对于极角相同的点离s更小的排在前面。

为了保证精确度，可以用以下代码排序

bool cmp(node p1,node p2)
{
    double tmp=check(dot[1],p1,dot[1],p2);
    if(tmp>0) 
		return 1;
    if(tmp==0&&dis(dot[1],p1)<dis(dot[1],p2)) 
		return 1;
    return 0;
}

其中check/tmp是叉积,dis为距离

3.维护一个栈，保证里面至少要有两个元素（s和dot[2])，对于剩下的n-2个点,尝试将其加入到栈中。

令栈首为A，栈次为B，将加入的为C。

要求AC构成的向量在BA的左侧，可以看以下代码：

for(int i=3;i<=n;i++){
	while(top>=2&&pan(s[top],s[top-1],dot[i])==1){
		top--;
	}
	top++;
	s[top]=dot[i];
} 

其中pan是：

bool pan(node x,node y,node k){//栈头点/栈次点/将要加入的点 ，返回是否要弹出栈头 
	if(check(k,x,y,x)>0){//左侧
		return 0;
	}
	else{
		return 1;//在一条线上的暂时视为删除 
	}
}