betway必威游戏先确定a点和b点

当前位置:betway必威平台 > betway必威游戏 > betway必威游戏先确定a点和b点
作者: betway必威平台|来源: http://www.bag139.com|栏目:betway必威游戏

文章关键词:betway必威平台,凸包

  概念:在一个实数向量空间V中,对于给定集合X,所有包含X的凸集的交集S被称为 X的凸包。X的凸包可以用X内所有点(X1,...Xn)的凸组合来构造;

  简单来说:给你一个点集Q,你可以把Q中的每个点想象成一块木板上的铁钉,而点集Q的凸包就是包围了所有铁钉的一条拉紧了橡皮绳所构成的形状;

  在构造之前,我们需要先对这些点进行排序,按照x轴从小到大排,x相等时按照y轴从小到大排;

  对于上凸包,我们先选中前两个点,然后判断接下来的点,如图,先确定a点和b点,然后判断c点可否加入,连接ab,ac,可以看到,ac在ab的顺时针方向,因此c点可以加进来,然后判断d点;

  利用上面的方法,可以看到bd在bc的逆时针方向,这个时候,我们就需要把c点删除掉了,因为显然去掉c点可以使凸包的面积更大。

  同样先选中前两个点,如图,可以看到,betway必威游戏betway必威游戏ac在ab的逆时针方向,这时可以把c点加入(与上凸包情况相反),接下来判断d点;

  如下图,可以看到bd在bc的顺时针方向,betway必威游戏此时删除c点选择d点可以得到更大的凸包;

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!