北京大学ACM暑期课讲义-计算几何教程.ppt

《北京大学ACM暑期课讲义-计算几何教程.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算几何教程ComputationalGeometry计算几何的恶心之处代码长，难写。需要讨论各种边界情况。后面所介绍的算法，有些对于边界情况的处理很完美，不需要再做讨论；有些则不然，需要自行处理边界情况。精度误差2-DimensionVector二维矢量矢量既有大小又有方向的量。又称为向量。大家初中都毕业了我就不多说了。矢量的表示点积夹角矢量的垂直矢量的缩放矢量的投影矢量的对称二维叉积有向面积有向面积的符号点积和二维叉积的方向性利用点积可以判断矢量的前后。利用二维叉积可以判断矢量的左右。二维矢量的旋转二维

2、矢量的极角2-DimensionComputationalGeometry二维计算几何约定直线点到直线的距离分点三角形的面积两直线交点两线段交点求出直线的交点，然后其判断是否在两条线段上即可。若判断两线段是否相交，则要注意平行不一定不相交，两条线段可能有重合部分或重合点。三角形的重心多边形多边形是平面上由有限线段（大于2）组成，且首尾连接起来划出的封闭图形。教程后面的多边形一般指简单多边形，即边不相交的多边形。多边形的记录一般以顺次记录其顶点的方式完成，即顺次记录组成多边形的线段。方向一般为逆时针。判断点在

3、多边形内外以要判断的点为起点任作一射线，计算该射线与多边形的交点数目。若有偶数个交点则在形外，否则在形内。若与线段在端点处相交或重合，则要进行复杂的判断。此时可另取一射线。求多边形的面积基本的思路是进行三角剖分。求多边形的面积如果用普通面积的累加来计算的话，三角剖分就变得十分复杂。但是使用有向面积的话，这个过程就变得简单自然通用。算法算法演示算法演示算法演示算法演示算法演示算法演示算法演示算法演示算法演示三角剖分三角剖分即将多边形分为若干三角形部分，其中既有“正部分”亦有“负部分”。利用这种方法可以解决很多

4、问题。例题：求多边形的重心名前通り，给定一个简单多边形，求其重心之所在。预备知识：求质点组的重心解答利用三角剖分，计算各个三角形的面积和重心，将此三角形化为一个质量为其面积，坐标为其重心的质点。若此三角形属于“负部分”，则其拥有“负质量”。最后计算质点组的重心即可。凸集凸集举例空集直线、射线、线段凸多边形圆及内部、二次曲线及内部若干种原料，每种原料含A成分和B成分的比例不同；混合这些原料能得到的产品的A,B两种成分的比例凸包对于点集S，包含S中所有点的最小的凸集称为S的凸包。若S是有限集，则其凸包是凸多边形

5、。直观来看，把S中所有点钉在一个木板上，用一个橡皮筋框起所有点来，一撒手，橡皮筋就表示出了S的凸包。凸包水平序Graham扫描算法Graham扫描算法有水平序和极角序两种。极角序算法能一次确定整个凸包，但是计算极角需要用到三角函数，速度较慢，精度较差，特殊情况较多。水平序算法需要扫描两次，但排序简单，讨论简单，不易出错。算法流程算法演示首先将所有点排序。算法演示将1和2压入栈。算法演示2被弹出栈，3进栈。算法演示没有点被弹出栈，4进栈。算法演示4被弹出栈，5进栈。算法演示5被弹出栈，6进栈。算法演示6被弹出

6、栈，7进栈。算法演示如此直到下凸壳被找到。算法演示倒序进行扫描找到上凸壳。Graham扫描的时间复杂度这太傻缺了。算法的瓶颈在排序，所以时间复杂度是O(NlogN)。若坐标均为整数，可以用基数排序将复杂度优化到O(N)。旋转卡壳算法如何计算N个点中，距离最大的两个点的距离？要求O(NlogN)的算法。容易证明距离最大的两个点一定是凸包上的两个点，很明显是先求凸包然后做文章啦。对踵点若凸包上的两个顶点能落在一对平行切线上，则称它们为对踵点。容易证明，答案一定是一对对踵点之间的距离。对踵点的枚举从一对对踵点逆时

7、针枚举下一对对踵点的话，只需要观察下图中α角和β角的大小，选择其中较小的一个转过去就行了。算法最左侧点和最右侧点一定是对踵点。从此点对开始枚举即可。注意不只有“点–点”的情况，还有“点–边”和“边–边”的情况。这些情况下要枚举所有的点对。虽然看上去很简单，但是写起来还是要颇费一番周折的。旋转卡壳练习题POJ2178求点集中最远点POJ3608求两凸包间的最近点POJ2079求以点集中的点为顶点组成的三角形的最大面积，要求O(N2)算法。半平面半平面的表示半平面的交半平面是凸集，所以半平面的交也是凸集。有限个

8、半平面的交可能是空集、点、直线、射线、线段、凸多边形、有“开口”的形状甚至一个半平面。朴素的每次O(N)算法为了保证结果是凸多边形或其退化，首先建立一个非～常～大的边框。你懂的。每次顺次枚举多边形的边，与半平面求交，并将交的部分加入新多边形。在得到半平面边界与凸多边形所交形成的边时，立即将其加入新多边形。算法演示值得注意的边界情况1值得注意的边界情况2值得注意的边界情况3合计O(NlogN)的算法这是朱泽园在其国