《计算几何理论》PPT课件.ppt

《《计算几何理论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《计算几何理论》PPT课件.ppt（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第11章章 计算几何计算几何1.计算几何概述计算几何概述2.计算几何的基本问题计算几何的基本问题3.凸包及其应用凸包及其应用4.求线段集的两两交点求线段集的两两交点1.计算几何概述计算几何概述v计算几何采用了介于代数与几何之间的方式解决几何问题。计算几何采用了介于代数与几何之间的方式解决几何问题。它利用几何特性辅助简单的代数运算解决几何问题，既能它利用几何特性辅助简单的代数运算解决几何问题，既能精确求解，有提高了算法效率，并且不失几何的优美特性精确求解，有提高了算法效率，并且不失几何的优美特性v解析几何是一个选择。解析几何把所有的几何问题转换成解析几何是一个选择。解析几何把所有的几何问题转换

2、成纯粹的代数问题，而代数问题是可以用计算机解决的纯粹的代数问题，而代数问题是可以用计算机解决的v用解析几何借助计算机处理几何问题存在着两大缺陷用解析几何借助计算机处理几何问题存在着两大缺陷：1）方程解的情况复杂，例如）方程解的情况复杂，例如Ax+By+C=0；2）存在着浮点存在着浮点误差积累误差积累2.计算几何的基本问题计算几何的基本问题2.1 叉积叉积2.2 点积点积2.3 线段交点线段交点2.4 多边形的凸凹性判断多边形的凸凹性判断2.5 多边形内外判断多边形内外判断2.6 多边形的面积多边形的面积2.7 多边形的重心多边形的重心2.1 叉积叉积2.1.1 叉积的直观意叉积的直观意义义(x

3、b,yb)(xa,ya)Obac要判断向量要判断向量b是否在右手螺旋意义下处于是否在右手螺旋意义下处于a之后，在之后，在第一象限可以判断它们的斜率：第一象限可以判断它们的斜率：上式可以化为上式可以化为xayb-xbya 0.这个判断依据在整个平这个判断依据在整个平面上有效。面上有效。xayb-xbya 0时，向量时，向量a和和b呈右手系呈右手系xayb-xbya 0时，向量时，向量a和和b呈左手系呈左手系xayb-xbya=0时，向量时，向量a和和b共线共线2.1.2 叉积的几何意义叉积的几何意义(xb,yb)(xa,ya)bacv叉积是两个向量所构成的平行四边形的叉积是两个向量所构成的平行四

4、边形的有向有向面积面积v当两个向量呈右手系时，有向面积为正值当两个向量呈右手系时，有向面积为正值v当两个向量呈左手系时，有向面积为负值当两个向量呈左手系时，有向面积为负值O问题：已知三角形三问题：已知三角形三个顶点的坐标，怎样个顶点的坐标，怎样求其面积？求其面积？2.1.3 叉积与正弦函数的联系叉积与正弦函数的联系vOab的面积是的面积是(1/2)*|a|*|b|*sin v(1/2)*|a|*|b|*sin =(1/2)*a bv sin =a b/(|a|*|b|)v这里的这里的 是区分正负号的是区分正负号的(xb,yb)(xa,ya)bacO2.1.4 二维叉积和三维叉积二维叉积和三维叉

5、积v叉积的本质是一个向量，这个向量垂直于求叉积的叉积的本质是一个向量，这个向量垂直于求叉积的两个向量所在平面，大小是叉积的绝对值两个向量所在平面，大小是叉积的绝对值v二维情况的叉积向量平行于二维情况的叉积向量平行于z轴，因此可以用正负号轴，因此可以用正负号表示方向表示方向2.2 点积点积2.2.1 点积的定义点积的定义两个向量为：两个向量为：定义两个向量的点积为：定义两个向量的点积为：2.2.2 点积的性质点积的性质v两个向量的点积是标量两个向量的点积是标量v点积的变化与向量模的变化成正比。也点积的变化与向量模的变化成正比。也就是说，可以把向量标准化后再求点积，就是说，可以把向量标准化后再求点

6、积，然后再乘上某个系数，就可以得到原来向然后再乘上某个系数，就可以得到原来向量的点积量的点积v上述两个性质对于二维、三维、任意维上述两个性质对于二维、三维、任意维的情况结论是一样的的情况结论是一样的2.2.3 点积的几何解释点积的几何解释v一般用向量的点积表示两个向量的接近程度、相一般用向量的点积表示两个向量的接近程度、相似程度或相反程度。如果两个向量的模固定，那么，似程度或相反程度。如果两个向量的模固定，那么，当两个向量方向一致时，向量的点积值是正数并且当两个向量方向一致时，向量的点积值是正数并且最大；当两个向量方向相反时，两个向量的点积是最大；当两个向量方向相反时，两个向量的点积是负数且最

7、小负数且最小v当两个向量垂直时，两个向量的点积为当两个向量垂直时，两个向量的点积为0。这也。这也是向量垂直的判断方式。科学研究中，当发现两个是向量垂直的判断方式。科学研究中，当发现两个向量垂直时，一般认为它们是没有关系向量垂直时，一般认为它们是没有关系2.2.4 点积与余弦函数的关系点积与余弦函数的关系v通常用这个公式求解两个向量的夹角通常用这个公式求解两个向量的夹角v上面的公式对高维情形仍然成立上面的公式对高维情形仍然成立2.3 线段交点线段交点2.3.1 判断线段相交和求交点坐标判断线段相交和求交点坐标v判断线段相交和求线段交点是解决判断线段相交和求线段交点是解决几何问题的基础和基本手段几

8、何问题的基础和基本手段v这两个操作在几何问题中大量应用这两个操作在几何问题中大量应用v而判断线段是否相交是更常见的问而判断线段是否相交是更常见的问题，在很多情况下只是判断线段是否题，在很多情况下只是判断线段是否相交，而不是求其交点相交，而不是求其交点2.3.2 线段的规范相交和非规范线段的规范相交和非规范相交相交（1）（2）（3）（4）（5）（1）是规范相交，其它是非规范相交。非规范相交）是规范相交，其它是非规范相交。非规范相交的情况还有很多。通常只考虑规范相交的情况还有很多。通常只考虑规范相交2.3.3 线段的相交问题的解析几线段的相交问题的解析几何做法何做法v判断线段相交的解析几何做法通常

9、是：判断线段相交的解析几何做法通常是：1）根据）根据两条线段的端点列出两条线段所在直线的方程；两条线段的端点列出两条线段所在直线的方程；2）联立方程求方程组的解；）联立方程求方程组的解；3）根据解的存在情）根据解的存在情况判断它们所在直线有无交点；况判断它们所在直线有无交点；4）如果有交点，）如果有交点，判断交点是否都在两条线段的内部判断交点是否都在两条线段的内部v解析几何做法存在很多特殊情况难以统一处理：解析几何做法存在很多特殊情况难以统一处理：例如，例如，1）线段与坐标轴平行；）线段与坐标轴平行；2）两条线段平行）两条线段平行v解析几何做法存在着计算误差，尤其在做除法运解析几何做法存在着计

10、算误差，尤其在做除法运算时算时2.3.4 利用叉积判断线段相交利用叉积判断线段相交v两条线段两条线段AB和和CD规范相交等价于：规范相交等价于：A和和B分分属线段属线段CD所在直线的两侧；所在直线的两侧；C和和D分属线段分属线段AB所在直线的两侧所在直线的两侧v判断判断A和和B是否在线段是否在线段CD所在直线的两侧可以所在直线的两侧可以判断向量判断向量CD和和CA的叉积是否与向量的叉积是否与向量CD与与CB的的叉积符号相反叉积符号相反ABCD2.3.5 利用点积判断线段非规范利用点积判断线段非规范相交的状况相交的状况v非规范相交的情况有很多种，但它们有一个共性：至少存非规范相交的情况有很多种，

11、但它们有一个共性：至少存在一条线段的某个端点在另一条线段所在的直线上在一条线段的某个端点在另一条线段所在的直线上v这时的相应叉积是这时的相应叉积是0。上图中向量。上图中向量AB和向量和向量AC的叉积为的叉积为0v此时可以用向量此时可以用向量CA和向量和向量CB的点积判断的点积判断C是否在线段内部：是否在线段内部：点积是正数则在线段外部；点积等于点积是正数则在线段外部；点积等于0则与点则与点A或或B重合；点重合；点积为负数则在线段内部积为负数则在线段内部v如果点积等于如果点积等于0，则比较坐标就可以知道，则比较坐标就可以知道C与与A重合还是与重合还是与B重合；如果点积小于重合；如果点积小于0，则

12、继续计算向量，则继续计算向量AC和和AB的点积就的点积就可以知道可以知道C在线段在线段AB哪一端的延长线上哪一端的延长线上ABCD2.3.6 利用叉积求线段的交点利用叉积求线段的交点ABCD如果通过叉积计算的方式判断出两条线段规范相交，如果通过叉积计算的方式判断出两条线段规范相交，那么并不需要用解析几何的方式求两条线段的交点。那么并不需要用解析几何的方式求两条线段的交点。可以利用已经求得的叉积计算交点的坐标：可以利用已经求得的叉积计算交点的坐标：P2.4 多边形的凸凹性判断多边形的凸凹性判断2.4.1 平面上多边形的定义平面上多边形的定义v一个多边形就是二维平面上被一系列一个多边形就是二维平面

13、上被一系列首尾相接的线段围成的区域首尾相接的线段围成的区域v令令P0,P1,Pn-1为平面上的为平面上的n个点，个点，E0=P0P1,E1=P1P2,E En=Pn-1 P0为为n条条线段。这线段。这n条线段围成一个多边形当且仅条线段围成一个多边形当且仅当任何两条相邻的线段有且仅有一个交当任何两条相邻的线段有且仅有一个交点点2.4.2 多边形分类多边形分类v如果多边形任意两条不相邻的边没有公共交点，则称这个多边如果多边形任意两条不相邻的边没有公共交点，则称这个多边形为简单多边形；否则称为复杂多边形形为简单多边形；否则称为复杂多边形v但一类特殊的复杂多边形称为临界多边形，在性质上更接近于但一类特

14、殊的复杂多边形称为临界多边形，在性质上更接近于简单多边形简单多边形P1P2P7P4P5P6P3P1P2P3P4P1P2P3P4P5P6简单多边形复杂多边形临界多边形2.4.3 凸多边形判断凸多边形判断v判断方式判断方式1：对于多边形的任何一条边：对于多边形的任何一条边e，整整个多边形（或多边形的所有其它边）都在个多边形（或多边形的所有其它边）都在e的的一侧一侧v判断方式判断方式2：如果：如果D是（任意维）凸图形，则是（任意维）凸图形，则这个论断与下面的判断等价：这个论断与下面的判断等价：v其它判断方式其它判断方式2.5 多边形内外判断多边形内外判断2.5.1 交点法交点法P1P2P3P4判断某

15、点与无穷远处一点的判断某点与无穷远处一点的连线同各条边的交点。如果连线同各条边的交点。如果相交次数为奇数，则该点在相交次数为奇数，则该点在形内；否则，该点在形外形内；否则，该点在形外X2.5.2 交点法的特殊情况处理交点法的特殊情况处理-平移法平移法P1P2P3P4P1P2P3P4P1P2P3P4XXX或者2.5.3 环顾法环顾法P1P6P4P2P3P5XP1P6P4P2P3P5Xv如果某点在多边形内部，则由它发出的射线按照多边形的如果某点在多边形内部，则由它发出的射线按照多边形的边的方向环顾一周，其夹角积累为边的方向环顾一周，其夹角积累为2；v如果某点在多边形外部，则由它发出的射线按照多边形

16、的如果某点在多边形外部，则由它发出的射线按照多边形的边的方向环顾一周，其夹角积累为边的方向环顾一周，其夹角积累为0v通过叉积计算夹角的正负，通过点积计算角度大小通过叉积计算夹角的正负，通过点积计算角度大小2.5.4 环顾法的特殊情况处理环顾法的特殊情况处理环顾法有环顾法有3种情况：种情况：（1）X位于一条边上位于一条边上（2）X位于一个顶点位于一个顶点（3）X在延长线上在延长线上如果碰到情况（如果碰到情况（1）和（）和（2），则问题已解），则问题已解决，退出；决，退出；如果碰到情况（如果碰到情况（3），不需要考虑这条边构），不需要考虑这条边构成的夹角成的夹角2.6 多边形的面积多边形的面积2.

17、6.1 多边形面积的计算公式多边形面积的计算公式P1P2P3P4P5P6v这个结果可以看成坐标原这个结果可以看成坐标原点与各条边构成的点与各条边构成的n个三角个三角形的形的有向有向面积之和面积之和v不管坐标原点是否在多边不管坐标原点是否在多边形的内部还是外部形的内部还是外部2.6.2 多边形面积计算公式的几多边形面积计算公式的几何解释何解释OABC2.6.3 多边形面积计算公式的推多边形面积计算公式的推广广这个公式对凹多边形仍然成立：P1P2P3P4P5P62.7 多边形的重心多边形的重心2.7.1 三角形的重心三角形的重心由三个点由三个点(x1,y1),(x2,y2),(x3,y3)构成的三

18、角构成的三角形的重心的坐标是：形的重心的坐标是：2.7.2 猜想猜想n边形的重心边形的重心猜想由猜想由n个点个点(x1,y1),(x2,y2),(xn,yn)构构成的多边形的重心的坐标是：成的多边形的重心的坐标是：2.7.3 n边形的重心边形的重心P1P2P3P4P5P6v上面公式失效的原因是面积代表的重量并不均匀分上面公式失效的原因是面积代表的重量并不均匀分布在各个顶点上（如果重量均匀分布在各个顶点上，布在各个顶点上（如果重量均匀分布在各个顶点上，则上面公式成立）则上面公式成立）v可以先求出各个三角形的重心和面积，然后对它们可以先求出各个三角形的重心和面积，然后对它们按照权重相加按照权重相加

19、C1C2C3C43.凸包及其应用凸包及其应用3.1 凸包的相关定义和性质凸包的相关定义和性质3.1.1 凸包的直观解释凸包的直观解释3.1.2 凸包的形式化定义凸包的形式化定义3.1.3 极点及其性质极点及其性质3.1.1 凸包的直观解释凸包的直观解释打包裹收紧橡皮圈3.1.2 凸包的形式化定义凸包的形式化定义一个平面上点集的凸包指的是包含它的最小凸一个平面上点集的凸包指的是包含它的最小凸图形或最小凸区域图形或最小凸区域3.1.3 极点及其性质极点及其性质v凸包上的顶点（共线中点除外，例如下图中凸包上的顶点（共线中点除外，例如下图中的的P点）称为极点点）称为极点v极点不能被凸包中任意其它点凸表

20、示极点不能被凸包中任意其它点凸表示v凸包上的顶点是原点集中的点凸包上的顶点是原点集中的点P3.2 凸包的求解方法凸包的求解方法3.2.1 卷包裹法卷包裹法3.2.2 Graham-Scan算法算法3.2.3 分治法分治法(Quick Hull算法算法)3.2.4 增量法增量法3.2.1 卷包裹法卷包裹法3.2.1.1 卷包裹法的基本思想卷包裹法的基本思想v假设有一根无限长的绳子。绳子的端点在最假设有一根无限长的绳子。绳子的端点在最下面的点上（如果有多个最下面的点，则选择下面的点上（如果有多个最下面的点，则选择这些点中最左边的一个）这些点中最左边的一个）v以逆时针方向绕动绳子，根据最初碰到的点，

21、以逆时针方向绕动绳子，根据最初碰到的点，确定多条线段确定多条线段v直至回到起始点直至回到起始点3.2.1.2 卷包裹法的单步执行卷包裹法的单步执行ABv假设当前的线段是假设当前的线段是AB，则需要在则需要在B与其它各点的连线与其它各点的连线中找到最中找到最“右手右手”的方向。的方向。v可以把每一条射线与其它可以把每一条射线与其它n-2条射线比较，没步这样条射线比较，没步这样做的效率是做的效率是O(n2)v也可以通过计算各射线与射线也可以通过计算各射线与射线AB的夹角的方式，这的夹角的方式，这样做的效率是样做的效率是O(n)，但存在计算误差但存在计算误差v可以直接利用叉积求各条射线的相对关系，从

22、而求可以直接利用叉积求各条射线的相对关系，从而求“最右最右”射线，这样做的效率是射线，这样做的效率是O(n)，不存在计算误差不存在计算误差3.2.1.3 卷包裹法的步骤卷包裹法的步骤1)选择所有点中最下面的点，如果有多个，则选选择所有点中最下面的点，如果有多个，则选择最下面的点中最左边的一个，所选择的点是择最下面的点中最左边的一个，所选择的点是凸包的第一个点凸包的第一个点2)以水平向右的方向作为初始射线方向，选择第以水平向右的方向作为初始射线方向，选择第一条最一条最“右边右边”的射线作为当前射线，第一条的射线作为当前射线，第一条射线经过凸包的第二个点射线经过凸包的第二个点3)以当前射线为基准，

23、选择其以当前射线为基准，选择其“左边左边”最靠近该最靠近该射线的一条射线，从而找到了凸包的一个点。射线的一条射线，从而找到了凸包的一个点。把这条射线作为当前射线，这个过程一直继续，把这条射线作为当前射线，这个过程一直继续，直至回到第一个点直至回到第一个点3.2.1.4 卷包裹法的特殊情况卷包裹法的特殊情况ABCDv如果所选下一条射线中包含两个点，则可以在选如果所选下一条射线中包含两个点，则可以在选择下一条射线的时候不是仅仅求某个择下一条射线的时候不是仅仅求某个“最右边最右边”的的射线，而是求所有射线，而是求所有“最右边最右边”的射线，并记录的射线，并记录“最最右边右边”射线的数量，把射线上的所

24、有点归为凸包的射线的数量，把射线上的所有点归为凸包的点点v同一条射线上的点是可以排序的同一条射线上的点是可以排序的v事实上，有的问题并不要求输出共线的所有点，事实上，有的问题并不要求输出共线的所有点，而需要线上最两端的点而需要线上最两端的点3.2.1.5 卷包裹法的复杂度分析卷包裹法的复杂度分析v选择最下面点的时间复杂度是选择最下面点的时间复杂度是O(n)v每一步都要在最多每一步都要在最多n-2条射线中通过条射线中通过叉积计算和比较寻找最叉积计算和比较寻找最“右边右边”的射的射线，这个时间复杂度是线，这个时间复杂度是O(n)v卷包裹法共需要最多卷包裹法共需要最多n步，因此其综步，因此其综合的时

25、间复杂度是合的时间复杂度是O(n2)3.2.2 Graham-Scan算法算法3.2.2.1 试探性凸包试探性凸包P1P2P3P4P5P6P1P2P1P2P3P1P2P3P4P1P2P3P4P5P1P2P3P4P5P6P1P2P3P4P5P6P1P2P3P4P6P1P2P3P4P6试探性凸包用一个栈维持点的选择和放弃试探性凸包用一个栈维持点的选择和放弃3.2.2.2 预处理后的性能分析预处理后的性能分析v前面叙述的是前面叙述的是Graham-Scan算法的一部分：算法的一部分：所有点已经排序的前提下的所有点已经排序的前提下的Graham-Scan算法算法v每个点至多进栈一次，至多退栈一次每个点

26、至多进栈一次，至多退栈一次v一个点一旦退栈，就再也不可能进栈一个点一旦退栈，就再也不可能进栈v综合起来看，在得到所有点序的基础上，算综合起来看，在得到所有点序的基础上，算法共执行法共执行2n次，算法复杂度是次，算法复杂度是O(n)3.2.2.3 极角序极角序v把凸包问题中的各个点排序后，得到一个简单把凸包问题中的各个点排序后，得到一个简单多边形，然后才能采用多边形，然后才能采用Graham-Scan算法算法v可以用可以用arctan2函数求得各个点的极角，然后排函数求得各个点的极角，然后排序。但这样做会有浮点误差，且计算极角的运算序。但这样做会有浮点误差，且计算极角的运算量大，没有用到几何特性

27、，也没有深入使用排序量大，没有用到几何特性，也没有深入使用排序算法算法v满足全序关系，就能排序，无需算值满足全序关系，就能排序，无需算值3.2.2.4 共线问题解决共线问题解决vGraham-Scan算法执行过程中会碰到多算法执行过程中会碰到多点共线的情况点共线的情况v此时的一个解决办法是每次取三个点，此时的一个解决办法是每次取三个点，如果三者共线，则去掉中间的点如果三者共线，则去掉中间的点3.2.2.5 水平序水平序1234567v放弃极角规定的序，采用直角坐标规定的序：放弃极角规定的序，采用直角坐标规定的序：纵坐标作为第一序，横坐标作为第二序纵坐标作为第一序，横坐标作为第二序v使用水平序的

28、好处是：使用水平序的好处是：i.使得排序算法中的比较运算量大大降低使得排序算法中的比较运算量大大降低ii.起始点更容易发现起始点更容易发现iii.解决了共线的问题解决了共线的问题3.2.2.6 Graham-Scan算法步骤总结算法步骤总结1)使用极角序或直角坐标序为凸包问题的所使用极角序或直角坐标序为凸包问题的所有点排序有点排序2)寻找初始点寻找初始点3)利用一个栈结构，从初始点出发，循环地利用一个栈结构，从初始点出发，循环地把下一个点纳入到凸包中，把极点保存在把下一个点纳入到凸包中，把极点保存在栈结构中，把非极点弹出栈结构栈结构中，把非极点弹出栈结构4)遇到初始点时算法终止，并按照顺序输出

29、遇到初始点时算法终止，并按照顺序输出栈中的所有元素作为凸包的极点栈中的所有元素作为凸包的极点3.2.2.7 Graham-Scan算法的时算法的时间复杂性分析间复杂性分析vGraham-Scan算法的时间复杂性取决于两算法的时间复杂性取决于两部分：对凸包问题点的排序操作和对已排序部分：对凸包问题点的排序操作和对已排序点的选择点的选择v排序操作的时间复杂度是排序操作的时间复杂度是O(nlogn)，而选而选择极点操作的时间复杂度是择极点操作的时间复杂度是O(n)vGraham-Scan算法的时间复杂度是算法的时间复杂度是O(nlogn)3.2.3 分治法分治法(Quick Hull算法算法)3.2

30、.3.2 Quick Hull算法的基本算法的基本思想思想v寻找最低点寻找最低点a和最高点和最高点b，以以a和和b之间的连之间的连线为界把所有点分割成左右两部分线为界把所有点分割成左右两部分v左右两部分分别求凸包，然后合并凸包左右两部分分别求凸包，然后合并凸包abcd3.2.3.3 点的分割点的分割v以以a和和b之间的连线为界，分割所有的点成为两之间的连线为界，分割所有的点成为两部分的时间复杂度是部分的时间复杂度是O(n)v线段线段ab的极点的极点c可以把右边的点分成三部分：一可以把右边的点分成三部分：一个三角形和两个小问题个三角形和两个小问题abcd3.2.3.4 凸包合并凸包合并v左右两部

31、分形成的凸包的合并异常简单：直接左右两部分形成的凸包的合并异常简单：直接求并，去掉重复的求并，去掉重复的a和和b即可即可v右边三角形与另外一个凸包的合并是线性的，右边三角形与另外一个凸包的合并是线性的，最终是最终是a和和c分别与右下角凸包的某两个顶点相连分别与右下角凸包的某两个顶点相连abcd3.2.3.5 Quick Hull算法的时间算法的时间复杂度分析复杂度分析vQuick Hull算法的时间复杂度是算法的时间复杂度是O(nlogn)的的v如果凸包问题的点在所给区域上均匀分布，如果凸包问题的点在所给区域上均匀分布，则该算法的时间复杂度是线性的则该算法的时间复杂度是线性的3.2.4 增量法

32、增量法3.2.4.1 增量法求凸包的原理增量法求凸包的原理v增量法求凸包的思路是：从三个点构成的凸增量法求凸包的思路是：从三个点构成的凸包包-三角形开始，每次向已有的凸包中增加三角形开始，每次向已有的凸包中增加一个点一个点v如果新增点在当前凸包之内，则忽略它；否如果新增点在当前凸包之内，则忽略它；否则，新点和原凸包共同构成一个新的凸包则，新点和原凸包共同构成一个新的凸包v增量法求凸包的两个核心问题是：判断一个增量法求凸包的两个核心问题是：判断一个点是否在凸包内部；凸包外的一个点如何和点是否在凸包内部；凸包外的一个点如何和原来的凸包快速地合并成一个新的凸包原来的凸包快速地合并成一个新的凸包3.2

33、.4.2 判断点在凸包内外的方法判断点在凸包内外的方法v如果某个点在凸图形某条边的外侧，如果某个点在凸图形某条边的外侧，则它一定在凸图形的外侧则它一定在凸图形的外侧v如果一个点在凸图形某条边的内侧，如果一个点在凸图形某条边的内侧，而该点在凸图形的外侧，那么所有边一而该点在凸图形的外侧，那么所有边一定可以分成连续的两部分：该点在一部定可以分成连续的两部分：该点在一部分边的内侧，在另一部分边的外侧分边的内侧，在另一部分边的外侧v由于由于P1P和和P1P2构成的夹角单调变化，构成的夹角单调变化，因此可以用二分的方式找到临界的边因此可以用二分的方式找到临界的边v当一个点在第一条边的内侧时，可以当一个点

34、在第一条边的内侧时，可以用二分的方法判断该点是不是在所有边用二分的方法判断该点是不是在所有边的内侧的内侧P1P2P3.2.4.3 凸包扩展的方法凸包扩展的方法P1P2P4P5P6P3Pv凸包外一点凸包外一点P到凸包的切线发生在这样的点处：这到凸包的切线发生在这样的点处：这个点相连的两条边与个点相连的两条边与P的转角相反。例如，边的转角相反。例如，边P6-P1与边与边P6-P呈右手系，而边呈右手系，而边P1-P2与边与边P1-P呈左手系呈左手系v根据夹角单调变化的特点，可以用二分的方式发根据夹角单调变化的特点，可以用二分的方式发现切点，时间复杂度是现切点，时间复杂度是O(nlogn)3.2.4.

35、4 增量法求凸包的时间复增量法求凸包的时间复杂度分析杂度分析v判断一个点是否在凸包之内的时间复杂度判断一个点是否在凸包之内的时间复杂度是是O(logn)v寻找一对切点的时间复杂度是寻找一对切点的时间复杂度是O(logn)v综合起来，增量法求凸包的时间复杂度是综合起来，增量法求凸包的时间复杂度是O(nlogn)v增量法求凸包算法的时间复杂度得到了求增量法求凸包算法的时间复杂度得到了求解凸包问题时间复杂度的下界，是最优算法解凸包问题时间复杂度的下界，是最优算法3.3 凸包的应用凸包的应用3.3.1 合金制造问题合金制造问题3.3.2 求对踵点求对踵点3.3.3 求点集的直径求点集的直径3.3.4

36、求最小外接矩形求最小外接矩形3.3.5 点集分割点集分割3.3.6 凸包应用总结凸包应用总结3.3.1 合金制造问题合金制造问题3.3.1.1 合金制造问题描述合金制造问题描述v原材料是一些不同含量的金原材料是一些不同含量的金-银合金，数量无限制银合金，数量无限制v问题问题1：给出一种金银合金比例，问能不能通过已：给出一种金银合金比例，问能不能通过已有原材料制造出来这种比例的合金？有原材料制造出来这种比例的合金？v问题问题2：如果能够制造，怎样配比原材料？：如果能够制造，怎样配比原材料？v问题问题3：对于给定的原材料，能够制造的合金范围：对于给定的原材料，能够制造的合金范围怎样？怎样？3.3.

37、1.2 一维情况一维情况含金量低A含金量高Bv新合金产品的含金量必须在线段新合金产品的含金量必须在线段AB上才能制上才能制造，否则不能制造造，否则不能制造v如果新的合金材料的含金量是如果新的合金材料的含金量是C，而而A和和B的的配比分别是配比分别是 和和1-，那么可以这个公式计算配，那么可以这个公式计算配比：比：C=A+(1-)B3.3.1.3 二维情况二维情况v如果合金是由金银构成的，则能够生如果合金是由金银构成的，则能够生成的新合金的金银比例在所有的合金比成的新合金的金银比例在所有的合金比例点形成的凸包之中，包括边和极点例点形成的凸包之中，包括边和极点v给定凸包内的一个点作为新产品的金给定

38、凸包内的一个点作为新产品的金银比例，可以用任何一个极点与该点建银比例，可以用任何一个极点与该点建立连线，该连线一定与某条边交于内部立连线，该连线一定与某条边交于内部或端点或端点v如果交于端点，则按照一维的情况运如果交于端点，则按照一维的情况运算，如果交于内部，则先计算交点的比算，如果交于内部，则先计算交点的比例，再按照一维的情况计算交点所在线例，再按照一维的情况计算交点所在线段的两个顶点的比例段的两个顶点的比例3.3.1.4 高维情况高维情况v当合金中的金属种类超过当合金中的金属种类超过2个时，合金问题出现个时，合金问题出现高维情况高维情况v三维的凸图形是凸多面体三维的凸图形是凸多面体v更高维

39、的凸图形的性质与低维图形性质类似更高维的凸图形的性质与低维图形性质类似v三维要计算合金比例，先计算某个极点与所给三维要计算合金比例，先计算某个极点与所给点连线与某个面的交点，再从面到线，再从线到点连线与某个面的交点，再从面到线，再从线到点，逐一计算比例。注意：在这个过程中，某个点，逐一计算比例。注意：在这个过程中，某个顶点可能重复用到，需要累加其比例顶点可能重复用到，需要累加其比例3.3.2 求对踵点求对踵点定义：如果一条直线定义：如果一条直线L通过凸多边形通过凸多边形P的一个顶点，的一个顶点，且多边形在这条直线的一侧，则称且多边形在这条直线的一侧，则称L是是P的支撑线的支撑线定义：通过两条平

40、行支撑线的凸多边形定义：通过两条平行支撑线的凸多边形P上的任何两上的任何两点，叫做对踵点对（点，叫做对踵点对（AntiPodal Pair）P1L1L2P2P5L5P4L4P33.3.3 求点集的直径求点集的直径3.3.3.1 问题描述问题描述v定义：给出平面上的定义：给出平面上的n个点构成的点集，它们两两个点构成的点集，它们两两距离的最大值称为这个点集的直径距离的最大值称为这个点集的直径v平面点集直径是能够覆盖这些点的圆的最小直径平面点集直径是能够覆盖这些点的圆的最小直径v可以用穷举的方式计算平面点集的直径，但时间可以用穷举的方式计算平面点集的直径，但时间复杂度太高：复杂度太高：O(n2)3

41、.3.3.2 问题转化问题转化定理：平面点集定理：平面点集Z的直径等于的直径等于Z的凸包中的凸包中两两极点距离的最大值两两极点距离的最大值依据这个定理，可以把求平面点集直径的依据这个定理，可以把求平面点集直径的问题转化成问题转化成“求凸包求凸包”和和“发现凸包极发现凸包极点两两距离最大值点两两距离最大值”两个问题两个问题凸多边形两两极点距离的最大值也称为凸凸多边形两两极点距离的最大值也称为凸包的直径包的直径3.3.3.3 凸多边形直径定理凸多边形直径定理v定理：凸多边形定理：凸多边形P的直径等于的直径等于P的所有平行的所有平行支撑线之间距离的最大值支撑线之间距离的最大值v这个定理说明：凸多边形

42、的直径可以在对踵这个定理说明：凸多边形的直径可以在对踵点对之间寻找点对之间寻找3.3.3.4 寻找凸多边形一个顶点寻找凸多边形一个顶点的最远对踵点的算法的最远对踵点的算法P1P2P3P4P5P6P7P8v各点与直线各点与直线P3P4之间的距离：从之间的距离：从P4端开始，逐渐增加端开始，逐渐增加至最远的至最远的P7；从从P3端，逐渐增加至最远的端，逐渐增加至最远的P7v各点与直线各点与直线P4P5之间的距离：从之间的距离：从P5端开始，逐渐增加端开始，逐渐增加至最远的至最远的P1；从从P4端，逐渐增加至最远的端，逐渐增加至最远的P1vP4的对踵点在的对踵点在P7P1之间（包含之间（包含P1和和

43、P7）v可用单峰一维优化法查找可用单峰一维优化法查找P7和和P13.3.4.5 求平面点集直径的算法求平面点集直径的算法步骤步骤1)求解点集的凸包求解点集的凸包2)分分n步对所有点做如下操作：用二分法寻找步对所有点做如下操作：用二分法寻找其最远对踵点的范围，然后顺序查找最远其最远对踵点的范围，然后顺序查找最远对踵点，并记录最远距离对踵点，并记录最远距离3)求得的最远距离就是点集的直径求得的最远距离就是点集的直径3.3.4.6 求平面点集直径的算法求平面点集直径的算法复杂度分析复杂度分析v求凸包的操作时间复杂度是求凸包的操作时间复杂度是O(nlogn)v对每点求最远对踵点的操作时间复杂度对每点求

44、最远对踵点的操作时间复杂度是是O(logm)，这里这里m=nv综合起来，求平面点集直径算法的时间综合起来，求平面点集直径算法的时间复杂度是复杂度是O(nlogn)，比在点集中两两之间比在点集中两两之间求距离的穷举法要快得多求距离的穷举法要快得多3.3.4 求最小外接矩形求最小外接矩形定义：平面点集定义：平面点集N的最小外接矩形是能的最小外接矩形是能够覆盖够覆盖N的面积最小的矩形的面积最小的矩形定义：凸多边形定义：凸多边形P的最小外接矩形是能的最小外接矩形是能够覆盖够覆盖P的面积最小的矩形的面积最小的矩形定理：平面点集定理：平面点集N的外接矩形就是的外接矩形就是N的凸的凸包的外接最小矩形包的外接

45、最小矩形算法依据：凸多边形算法依据：凸多边形P的外接最小矩形的外接最小矩形至少有一条边覆盖至少有一条边覆盖P的两个极点的两个极点3.3.5 点集分割点集分割3.3.5.1 问题描述问题描述v给定平面上的两个点集给定平面上的两个点集P和和Q，判断是否存在一判断是否存在一条直线把它们分割开条直线把它们分割开v穷举法：把穷举法：把P中的点两两连接，得到线段集中的点两两连接，得到线段集A，把把Q中的点两两连接，得到线段集中的点两两连接，得到线段集B，两两判断两两判断A和和B中的线段是否相交中的线段是否相交v此法复杂度此法复杂度O(n4)v此法一种包含的情况没考虑到此法一种包含的情况没考虑到3.3.5.

46、2 问题转换问题转换v点集分割问题可以转换成这样的问题：先点集分割问题可以转换成这样的问题：先把两个点集分别求凸包，再判断两个凸包把两个点集分别求凸包，再判断两个凸包是不是相交是不是相交v如果两个凸包不相交，则一定存在一条直如果两个凸包不相交，则一定存在一条直线把它们分割开线把它们分割开3.3.5.3 问题求解问题求解v要判断两个凸包要判断两个凸包P和和Q是不是相交，可以用是不是相交，可以用P中的所有中的所有边与边与Q中的所有边两两判断是否有交点。如果有交点，中的所有边两两判断是否有交点。如果有交点，说明它们相交；如果没有交点，做下面的判断：说明它们相交；如果没有交点，做下面的判断：v在在P中

47、任意找一顶点判断它是否在中任意找一顶点判断它是否在Q内，如果在内，如果在Q内，内，说明两个凸包相交，如果不在，做下面的判断：说明两个凸包相交，如果不在，做下面的判断：v在在Q内任意找一顶点判断它是否在内任意找一顶点判断它是否在P内，如果在内，如果在P内，内，说明两个凸包相交，如果不在，则两个凸包不相交说明两个凸包相交，如果不在，则两个凸包不相交v利用凸包判断两个点集是否能分割的时间复杂度是利用凸包判断两个点集是否能分割的时间复杂度是O(m2)，比在原点集中判断的时间复杂度比在原点集中判断的时间复杂度O(n4)大大降低大大降低3.3.6 凸包应用总结凸包应用总结v利用凸包能够大大减少点集的数量。

48、利用凸包能够大大减少点集的数量。k维球维球体中均匀独立分布的体中均匀独立分布的n个点，其凸包中顶点个个点，其凸包中顶点个数数m(k,n)为：为：平面情况：平面情况：m(2,n)=O(n1/3)立体情况：立体情况：m(3,n)=O(n1/2)v凸包相对于原点集，增加了一个序，带来了凸包相对于原点集，增加了一个序，带来了许多好的特性。例如，可以进行不同类型的二许多好的特性。例如，可以进行不同类型的二分查找等分查找等4.求线段集的两两交点求线段集的两两交点4.1 求平面线段集交点问题的描述求平面线段集交点问题的描述v计算机图形学和模式识别中会发现很多线段，计算机图形学和模式识别中会发现很多线段，求所

49、有这些线段两两的的交点是一个常见的求所有这些线段两两的的交点是一个常见的问题问题v如果两两求交点，则时间复杂度是如果两两求交点，则时间复杂度是O(n2)。这在交点比较密集的情况下是好的算法。但这在交点比较密集的情况下是好的算法。但交点的数量和线段的数量在很多情况下是一交点的数量和线段的数量在很多情况下是一个数量级的，并不是平方关系，因此需要更个数量级的，并不是平方关系，因此需要更高效的算法高效的算法4.2 平面线段集的扫描序的定义平面线段集的扫描序的定义xL1L2L3L1 a L2 a L3；L2 b L1 b L3；L2 c L3abc4.3 求平面线段集交点问题算法求平面线段集交点问题算法

50、的原理的原理v沿沿x轴方向从左到右，碰到端点和交点都是调度事件轴方向从左到右，碰到端点和交点都是调度事件v碰到一个新的开始端点，只要求它与在碰到一个新的开始端点，只要求它与在y轴上相邻两轴上相邻两条线段的交点即可。如果它和其它非相邻线段有交点，条线段的交点即可。如果它和其它非相邻线段有交点，随着扫描点的右移，肯定有机会求交点随着扫描点的右移，肯定有机会求交点v碰到下一个交点之前，线段在扫描线上的次序不变；碰到下一个交点之前，线段在扫描线上的次序不变；碰到一个交点，则交点对应的两条线段交换扫描线上碰到一个交点，则交点对应的两条线段交换扫描线上的次序的次序v碰到下一个结束端点，则需要删除它所在的线