精华内容
下载资源
问答
  • 凸包问题

    2021-05-16 17:20:45
    文章目录凸包问题一、穷举法二、分治法三、使用步骤 凸包问题 问题描述:凸包(Convex Hull)是一个计算几何中的概念。在一个n维向量空间V中,对于给定集合X,所有包含X的凸集的交集S被称为X的凸包。在二维空间中,...


    凸包问题

    问题描述:凸包(Convex Hull)是一个计算几何中的概念。在一个n维向量空间V中,对于给定集合X,所有包含X的凸集的交集S被称为X的凸包。在二维空间中,凸包可想象为一个刚好包含所有点的凸多边形,即对于任意的一个点,要么这个点在这个凸多边形上,要么在凸多边形内。凸包问题是给定平面上一堆点集,要求输出位于凸包上的点。这个问题有很多种算法,如穷举法,分治法,Gift-Wrapping算法,Melkman算法,Graham扫描法,这里先介绍前三种算法。


    一、穷举法

    穷举法比较简单,由两个步骤组成:

    1. 将点集中的点两两配对,每对点分别计算一条直线
    2. 对于每条直线,检查剩余的 n-2 个点是否在直线的同一侧,如果是,再检查是否有点在这条直线上但不在这条线段上,如果没有,则这两个点都在凸包上。

    二、分治法

    分治法的思想是把一个大问题分成几个结构相似的子问题,然后再把子问题再分成几个更小的子问题……。这样我们就能用递归的方法,分别求这些子问题的解。最后把每个子问题的解“组装”成原来问题的解。分治法解决凸包问题的基本思想是根据在凸包上的点不断划分点集。具体算法如下:

    1. 把所有的点都放在二维坐标系里面。那么横坐标最小和最大的两个点 P1 和 Pn 一定是凸包上的点(如果有两个或以上横坐标最小的点,则这些点中最左边的点和最右边的点一定是凸包上的点此时取其中一个为P1即可)。直线 P1Pn 把点集分成了上下两部分,分别叫做上包和下包。
    2. 对上包:求距离直线 P1Pn 最远的点(如果有多个最远点,取其中一个即可),设为Pmax 。
    3. 作直线 P1Pmax 、PnPmax,把直线 P1Pmax 左侧的点当成是上包,把直线 PnPmax 右侧的点也当成是上包。对下包也作类似操作。
    4. 重复步骤 2、3。

    三、Gift-Wrapping算法

    这个算法依赖于一个发现:如果我们以凸包上的点建立一个极角坐标系,极轴的方向是前一个凸包点到这个凸包点的方向,那么该点连结其它所有点的极角中,下一个凸包上的点到该点极角最小。具体算法:随机选择一个点作为前一个点,然后首先找到最左边的点P0作为当前点,这个点必然在凸包上,然后计算与该点极角最小的点P1,找到P1后,将P1设为当前点,P0作为前一个点,这样就可以从P1开始,接着顺次找到P2,又以P2为当前点……直到回到P0为止。

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,496
精华内容 598
关键字:

凸包问题