R语言实现最小凸包算法

#R语言实现最小凸包算法（Graham扫描法）

p=co_db[which.min(co_db$Y),] #initial p as the start point

#1 order point set by its angular (from min to max)
co_db$cos.theta=(co_db$X-p$X)/sqrt((co_db$X-p$X)^2+(co_db$Y-p$Y)^2)
co_db_ordered=co_db[order(co_db$cos.theta,decreasing = T),]

co_db_ordered$theta.order=1:nrow(co_db_ordered)

p=filter(co_db_ordered,cos.theta=='NaN')
co_db_ordered=filter(co_db_ordered,cos.theta!='NaN')
p[2:3,]=co_db_ordered[1:2,]
p=p_i
top=nrow(p)
cross_vector=function(p0,p1,c){#即进行判断的点总是有两个来自于P点集，一个来自于co_db_ordered点集
  (c$X-p0$X)*(p1$Y-p0$Y)-(p1$X-p0$X)*(c$Y-p0$Y)
}
for (i in 3:(nrow(co_db_ordered))){
   while(cross_vector(p[top-1,],p[top,],co_db_ordered[i,])>0){
     p[top,]=p[top-1,]
     top=top-1
   }
   p[top+1,]=co_db_ordered[i,]
   top=top+1
 }
 p=p[top,]#由于实际上并不是用堆栈的方式生成的数据，所以会出现最后p数据框里的点多于最小凸包里的顶点的情况。这是我们就一定要用top取出实际上的最小凸包的所有顶点。