计算几何基础 (2).ppt

Teamwork! (1+1+13) 队长职责： 阅读题目（英语好） 熟悉队员 知识全面（能很快找到简单题目） 代码阅读能力强，找错能力强 注意： 避免以下情况：一道题目只有一个人做；三个人同时研究一题。 注意代码风格（行缩进、变量命名、变量初始化！） 点和直线的数据结构定义 struct Point{ double x; double y; }; struct Line { Point A, B; } 向量、叉积 AB = (B.x-A.x, B.y-A.y) |AB| = sqrt((B.x-A.x)*(B.x-A.x) + (B.y-A.y)*(B.y-A.y)) AB × CD = B.x-A.x, D.x-C.x B.y-A.y, D.y-C.y AB * CD = (B.x-A.x) * (D.x-C.x) + (B.y-A.y) * (D.y-C.y) 点和直线 判断点P在直线AB的左侧还是右侧 思考 怎么判断点P是否在线段AB上？ poj 2318 点和直线 求直线AB的中点C C.x = (A.x + B.x)/2; C.y = (A.y + B.y)/2; 设P’为P关于AB的对称点，则 P’.x = P.x + A.y – B.y; P’.y = P.y + B.x – A.x; 思考 怎么求P到直线AB的垂点？ 怎么求P到直线AB的距离？ 直线与直线 判断直线AB和直线CD是否相交？ 求斜率！ 求叉积！ AB × CD = 0 两直线平行 ≠0 两直线相交 判断两线段AB和CD是否相交 充要条件：A、B在CD两侧，且 C、D在AB两侧。 即： CA × CD 与 CB × CD 异号 且 AC × AB 与 AD × AB 异号 特殊情况：交点在线段的端点 求两直线交点 设有直线AB和CD，求交点P 令t = ( AC × CD )/( AB× CD ) P.x = A.x - (A.x-B.x)*t; P.y = A.y - (A.y-B.y)*t; 思考：如何求两线段交点？ 注意：1.线段可能无交点(两线段不相交） 2. 可能交点刚好在线段端点 3. 可能有无数个交点（两线段存在重叠部分） 判断直线AB和CD是否垂直 AB斜率k（存在），CD斜率为k’（存在），AB与CD垂直的充要条件是k*k’ = -1。即： (A.y-B.y) (C.y-D.y) (A.x-B.x) (C.x-D.x) 求直线AB与直线CD的夹角 令夹角为a (a=PI/2) AB * CD cos(a) = ------------------------ |AB| * |CD| p点关于f点旋转α角度后的点q 以f为原点，建立新坐标系。 新坐标系中p的坐标为p’ 将p化成极坐标(r, θ) q’ = (r, θ+a) 将q’转化成直角坐标系 求q’在原坐标系的位置q Poj 1673 三角形 求三角形面积 S = ?* AB × AC （结果可能为负，求绝对值） 三角形与圆 令三角形三边边长为a，b， c 半周长 P = (a+b+c)/2 面积S = sqrt(P* (P-a)*(P-b)*(P-c)) 三角形内切圆半径 r = S/P ; 三角形外接圆半径 R = a*b*c/(4*S) 多边形 求多边形面积 输入：多边形（顶点按逆时针顺序排列） 输出：面积S 凸多边形的三角形剖分 很自然地，我们会想到以 P1为扇面中心，连接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积： S=∑ (Si) (i=1…N-2) 凹多边形的面积？ 任意点为扇心的三角形剖分： 我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？ 比如，以多边形内部的一个点为扇心，就可以把多边形剖分成 N个三角形。 前面的三角剖分显然对于多边形内部任意一点都是合适的！ 我们可以得到： S= ∑(Si) （ i=1…N ） 即：S=∑ ∣ ∣/2 （ i=1…N