技术类计算几何基础

1、2022/9/131Teamwork! (1+1+13)队长职责：阅读题目（英语好）熟悉队员知识全面（能很快找到简单题目）代码阅读能力强，找错能力强注意：避免以下情况：一道题目只有一个人做；三个人同时研究一题。注意代码风格（行缩进、变量命名、变量初始化！）2022/9/132点和直线的数据结构定义struct Point double x; double y;struct Line Point A, B;注意！计算几何经常涉及到开方、除法等运算，最好使用double类型！2022/9/133向量、叉积AB = (B.x-A.x, B.y-A.y)|AB| = sqrt(B.x-A.x)*(B.

2、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) 2022/9/134点和直线判断点P在直线AB的左侧还是右侧计算 APAB结果为正，则在右侧结果为负，则在左侧PPABBAAPAB = 0, P在AB上注意：A.yB.y2022/9/135思考怎么判断点P是否在线段AB上？(1) PAPB = 0(2) A.x = P.x =B.x， A.y=P.y=B.y2022/9/136poj 2318U

3、1U2UnL1L2Lnn条直线将矩形划分成n+1个区域。给定若干个点，统计每个区域各包含多少个点。2022/9/137点和直线求直线AB的中点CC.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;2022/9/138思考怎么求P到直线AB的垂点？怎么求P到直线AB的距离？2022/9/139直线与直线判断直线AB和直线CD是否相交？ 求斜率！求叉积！ AB CD = 0 两直线平行 0 两直线相交1. 斜率不存在的情况；2. 两直线重叠2022/9/131

4、0判断两线段AB和CD是否相交充要条件：A、B在CD两侧，且 C、D在AB两侧。即： CA CD 与 CB CD 异号且 AC AB 与 AD AB 异号特殊情况：交点在线段的端点2022/9/1311求两直线交点设有直线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. 可能有无数个交点（两线段存在重叠部分）2022/9/1312判断直线AB和CD是否垂直AB斜率k（存在），CD

5、斜率为k（存在），AB与CD垂直的充要条件是k*k = -1。即： (A.y-B.y) (C.y-D.y) (A.x-B.x) (C.x-D.x)*= -1上述公式对斜率为0及斜率不存在的情况仍适用！(A.x.B.x)*(C.x-D.x) + (A.y-B.y)*(C.y-D.y) = 0;2022/9/1313求直线AB与直线CD的夹角令夹角为a (a=PI/2) AB * CDcos(a) = - |AB| * |CD|2022/9/1314p点关于f点旋转角度后的点q以f为原点，建立新坐标系。新坐标系中p的坐标为p将p化成极坐标(r, )q = (r, +a)将q转化成直角坐标系求q在原

6、坐标系的位置qpfqa2022/9/1315Poj 16732022/9/1316三角形求三角形面积S = * AB AC （结果可能为负，求绝对值）ABC成左手系，负面积ABC成右手系，正面积BCACBA2022/9/1317三角形与圆 令三角形三边边长为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) 2022/9/1318多边形求多边形面积输入：多边形（顶点按逆时针顺序排列）输出：面积S2022/9/1319凸多边形的三角形剖分很自然地，我们

7、会想到以 P1为扇面中心，连接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积： S= (Si) (i=1N-2)P1P2P3P4P5P6S1S2S3S42022/9/1320凹多边形的面积？P1P4P3P2 S= (Si) (i=1N-2)，公式依然成立！2022/9/1321任意点为扇心的三角形剖分：我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？比如，以多边形内部的一个点为扇心，就可以把多边形剖分成 N个三角形。P0P1P2P6P5P4P32022/9/1322前面的三角剖分显然对于多边形内部任意一点都是合适的！我们可以得到：

8、S= (Si) （ i=1N ）即：S= /2 （ i=1N ） Xi X0 Yi Y0X(i+1) X0 Y(i+1) Y02022/9/1323能不能把扇心移到多边形以外呢？P0P1P2P3P42022/9/1324既然内外都可以，为什么不设P0为坐标原点呢？OP1P2P3P4现在的公式？2022/9/1325简化的公式：S= /2（ i=1N ） Xi YiX(i+1) Y(i+1)2022/9/1326思考怎么判断一个点是否在多边形里面？2022/9/1327其它几何问题求圆的面积、体积三角形的重心（中线交点）、垂心（垂线交点）、内心（角平分线交点）、外心（中垂线交点）2022/9/1

9、328求凸包2022/9/13292022/9/13302022/9/13311. 找出最低点P0，即P0.y=Pi.y (1=in)如果存在多个最低点，找最左边的点2. 将P1Pn排序（按直线P0Pi与x轴（正轴方向）夹角大小排）2022/9/1332pointsn 记录已排序的n个点的坐标result 记录凸包点集 （result是个栈,top是其指针）初始化： result = P0, P1, P2, top = 32022/9/1333for (int i=3; in; i+) 1. while (resulttop-2在直线resulttop-1 pointsi 的顺时针方向) to

10、p-;2. result.push(pointsi);2022/9/1334result = P0, P1, P2，扫描点P3P1在P2P3的顺时针方向，将P2出栈，result = P0, P1P0在P1P3的逆时针方向，停止出栈。P3入栈，得到result = P0, P1, P3|P2 P3| |P2 P1|02022/9/1335result = P0, P1, P3，扫描点P4P1在P3P4的逆时针方向，停止出栈。P4入栈，得到result = P0, P1, P3, P42022/9/1336result = P0, P1, P3, P4，扫描点P5P3在P4P5的顺时针方向，P4

11、出栈，result = P0, P1, P3P1在P3P5的逆时针方向，停止出栈P5入栈，result = P0, P1, P3, P52022/9/1337result = P0, P1, P3, P5，扫描点P6P3在P5P6的顺时针方向，P5出栈，result = P0, P1, P3P1在P5P6的逆时针方向，停止出栈P6入栈，result = P0, P1, P3, P62022/9/1338result = P0, P1, P3, P6，扫描点P7P3在P6P7的逆时针方向，停止出栈P7入栈，result = P0, P1, P3, P6，P72022/9/1339result =

12、 P0, P1, P3, P6，P7，扫描点P8P6在P7P8的逆时针方向，停止出栈P7入栈，result = P0, P1, P3, P6，P7, P82022/9/1340result = P0, P1, P3, P6，P7, P8 ，扫描点P9P7在P8P9的顺时针方向，P8出栈P6在P7P9的顺时针方向，P7出栈P3在P6P9的逆时针方向，停止出栈P9入栈，result = P0, P1, P3, P6, P92022/9/1341result = P0, P1, P3, P6, P9 ，扫描点P10P6在P9P10的顺时针方向，P9出栈，result=P0,P1,P3,P6P3在P6

13、P10的顺时针方向，P6出栈，result=P0,P1,P3P1在P3P10的逆时针方向，停止出栈P10入栈，result = P0, P1, P3, P102022/9/13422022/9/13432022/9/13442022/9/1345POJ练习题2242 求三角形外接圆半径1654 求多边形面积1673 求垂线、求直线交点1675 求两条直线的夹角2074 求两直线交点2318 判断点和直线之间的位置2022/9/1346计算几何注意事项数据类型一般采用double类型注意精度！判断x是否为0应该采用fabs(x)eps，其中eps为精度，一般取1e-8。圆周率取3.1415926