《计算几何讲》PPT课件.ppt

计算几何 Computational Geometry,多边形重心与费马点凸包（极角序、水平序）平面最远点对(旋转卡壳)最近点对(二分),多边形重心,对于三角形的重心,那么，推广至多边形，猜测为：,多边形重心,不妨假设一个梯形,因此，猜测有误！,多边形重心,P1,P2,P3,P4,P5,P6,C1,C2,C3,C4,加权平均,将多边形拆分为N个三角形，分别求其重心和面积，可以想象，原来的质量均匀分布在内部的区域上，而现在质量仅分布在这N个重心点上（等价变换），这时就可以利用刚才猜想的公式了。,多边形面积,P1,P2,P3,P4,P5,P6,C1,C2,C3,C4,公式：,其中：ci向量就表示第i个三角形的重心 C1=(p1.x+p2.x+p3.x)/3,(p1.y+p2.y+p3.y)/3 S是总面积,三角形的心,外心：外接圆圆心，三条中垂线的交点内心：内接圆圆心，三条角平分线交点重心：三条中线的交点垂心：三条垂线的交点,三角形费马点,在一个三角形中，到3个顶点距离之和最小的点叫做这个三角形的费马点。若三角形有一内角不小于120度，则此钝角的顶点就是距离和最小的点。若三角形ABC的3个内角均小于120，那么3条距离连线正好三等分费马点所在的周角。所以三角形的费马点也称为三角形的等角中心。,凸包,对于一个平面点集，它的凸包指的是包含它的最小凸图形或者最小凸区域。凸包：点集中所有点的凸组合。凸包的顶点称为极点。,应用,篱笆问题：假设你种了很多树，想用一个篱笆把所有的树都包在里面。出于经济考虑，这个篱笆应该是越小越好。,Graham-Scan算法,选取最低点中最左的一个作为参考点用极角排序 极角排序（叉乘来排序）Graham-Scan算法每一步是得到一个临时凸包只要当前点在上一条边的左手方向，就加入这个点否则回溯，直到新的点在左手方向为止,共线点对于要求求共线点的情况，没有办法简单而完美的处理：A、B两点没有办法都加入凸包中,特殊情况,水平序,先按y坐标排y相同的按x坐标排2次扫描先从第1个点即0开始到最后1个点即9得到右链再从最后1个点即9开始到第1个点即0，不包括已经在右链的点,最远点对（凸包的直径）,枚举O(n2)凸包+旋转卡壳 O(nlogn+n)最远点对在凸包上（数量不多久在凸包集中枚举，多则选择旋转卡壳）,旋转卡壳(Rotating Calipers),在得到凸包以后，可以只在顶点上面找最远点了。可以想象有两条平行线，“卡”住这个凸包，然后卡紧的情况下旋转一圈，肯定就能找到凸包直径，也就找到了最远的点对。或许这就是为啥叫“旋转卡壳法”。,旋转卡壳(Rotating Calipers),最近点对,纯枚举o(n*n)分治更省时,最近点对,选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=mind1,d2，S中的最接近点对或者是d，或者是某个p,q，其中pP1且qP2，如图所示。,