计算几何:凸包

给定一个点集,凸包是能够包围所有点的最小凸多边形。对于凸包,有以下的主要性质:1)所有顶点均在任何一条凸包边所在直线的一侧。如果逆时针遍历凸包的边,则对每条边,所有点均在其左侧。2)从任一点出发,沿逆时针前进总是向左转,沿顺时针前进总是向右转。

利用凸包的性质来求凸包。首先将点排序,优先按x排序再按y排序。第一个点直接加入,加下来若栈中点数目小于2直接加入;若大于2,则计算新点相对于栈里最上层边的方向,若是右转或同一直线,则将栈中最上层点踢出去继续判断。完善凸包的上半部分,从n开始向前遍历,过程同上。

需要注意的是,要求凸包必须有一个以上的点,否则会RE。求凸包的结果,栈中点是逆时针排列的。

vector<point> convex(point *ps,int n){
  sort(ps,ps+n);
  int k=0;
  vector<point> qs(2*n);
  for(int i=0;i<n;i++){
    while(k>1&&((qs[k-1]-qs[k-2])^(ps[i]-qs[k-1]))<=0) k--;
    qs[k++]=ps[i];
  }
  for(int i=n-2,t=k;i>=0;i--){
    while(k>t&&((qs[k-1]-qs[k-2])^(ps[i]-qs[k-1]))<=0) k--;
    qs[k++]=ps[i];
  }
  qs.resize(k-1);
  return qs;
}

 

上一篇:location对象


下一篇:axios