计算几何PPT课件

2.3.1 判断线段相交和求交点 坐标
判断线段相交和求线段交点是解决 几何问题的基础和基本手段
这两个操作在几何问题中大量应用
而判断线段是否相交是更常见的问 题，在很多情况下只是判断线段是否 相交，而不是求其交点
2.3.2 线段的规范相交和非规 范相交
（1）
（2）
（3）
（4）
（5）
（1）是规范相交，其它是非规范相交。非规范相交 的情况还有很多。通常只考虑规范相交
2.1 叉积 2.2 点积 2.3 线段交点 2.4 多边形的凸凹性判断 2.5 多边形内外判断 2.6 多边形的面积 2.7 多边形的重心
2.1 叉积
2.1.1 叉积的直观意义 2.1.2 叉积的几何意义 2.1.3 叉积与正弦函数的联 系 2.1.4 二维叉积和三维叉积
b (xb, yb)
(xa, ya) a
用解析几何借助计算机处理几何问题存在着两大缺陷：1） 方程解的情况复杂，例如Ax+By+C=0；2）存在着浮点误差 积累
计算几何采用了介于代数与几何之间的方式解决几何问题。 它利用几何特性辅助简单的代数运算解决几何问题，既能 精确求解，有提高了算法效率，并且不失几何的优美特性
2. 计算几何的基本问题
2.2.4 点积与余弦函数的关系
A B A B cos
通常用这个公式求解两个向量的夹角 上面的公式对高维情形仍然成立
2.3 线段交点
2.3.1 判断线段相交和求交点坐标 2.3.2 线段的规范相交和非规范相交 2.3.3 线段的相交问题的解析几何做法 2.3.4 利用叉积判断线段相交 2.3.5 利用点积判断线段非规范相交的状 况 2.3.6 利用叉积求线段的交点
2.3.3 线段的相交问题的解析 几何做法
判断线段相交的解析几何做法通常是：1）根据 两条线段的端点列出两条线段所在直线的方程；2） 联立方程求方程组的解；3）根据解的存在情况判 断它们所在直线有无交点；4）如果有交点，判断 交点是否都在两条线段的内部
解析几何做法存在很多特殊情况难以统一处理： 例如，1）线段与坐标轴平行；2）两条线段平行
2.1.2 叉积的几何意义
b (xb, yb)
(xa, ya) a
c 问题：已知三角形三 个顶点的坐标，怎样 求其面积？
O
叉积是两个向量所构成的平行四边形的有向面积
当两个向量呈右手系时，有向面积为正值 当两个向量呈左手系时，有向面积为负值
2.1.3 叉积与正弦函数的联系 c b (xb, yb)
c
2.1.1 叉积的直观意 义
O
要判断向量b是否在右手螺旋意义下处于a之后，在
wenku.baidu.com
第一象限可以判断它们的斜率：
yb ya 0 xb xa
上式可以化为xayb-xbya > 0. 这个判断依据在整个 平面上有效。
xayb-xbya > 0时，向量a和b呈右手系 xayb-xbya < 0时，向量a和b呈左手系 xayb-xbya = 0时，向量a和b共线
2.3.5 利用点积判断线段非规 A范相交的状况D
BC 非规范相交的情况有很多种，但它们有一个共性：至少存 在一条线段的某个端点在另一条线段所在的直线上
这时的相应叉积是0。上图中向量AB和向量AC的叉积为0
此时可以用向量CA和向量CB的点积判断C是否在线段内部：
点积是正数则在线段外部；点积等于0则与点A或B重合；点 积为负数则在线段内部
如果点积等于0，则比较坐标就可以知道C与A重合还是与B
重合；如果点积小于0，则继续计算向量AC和AB的点积就可
2.2.3 点积的几何解释
在科学研究中，向量一般是高维的，并且可以表 示任何意义
一般用向量的点积表示两个向量的接近程度、相 似程度或相反程度。如果两个向量的模固定，那么， 当两个向量方向一致时，向量的点积值是正数并且 最大；当两个向量方向相反时，两个向量的点积是 负数且最小
当两个向量垂直时，两个向量的点积为0。这也 是向量垂直的判断方式。科学研究中，当发现两个 向量垂直时，一般认为它们是没有关系
两个向量为： Ax1, x2,...,xn Bx1, x2 ,...,xn
定义两个向量的点积为：
n
A B xi xi i 1
2.2.2 点积的性质
两个向量的点积是标量 点积的变化与向量模的变化成正比。也 就是说，可以把向量标准化后再求点积， 然后再乘上某个系数，就可以得到原来向 量的点积 上述两个性质对于二维、三维、任意维 的情况结论是一样的
xb yb zb
叉积的本质是一个向量，这个向量垂直于求叉积的 两个向量所在平面，大小是叉积的绝对值
二维情况的叉积向量平行于z轴，因此可以用正负号 表示方向
2.2 点积
2.2.1 点积的定义 2.2.2 点积的性质 2.2.3 点积的几何解释 2.2.4 点积与余弦函数的关 系
2.2.1 点积的定义
第11章 计算几何
1. 计算几何概述 2. 计算几何的基本问题 3. 凸包及其应用 4. 求线段集的两两交点
1. 计算几何概述
在计算机图形学、图形用户接口、可视化技术、计算机辅 助设计、模式识别等领域，需要快速的几何算法
解析几何是一个选择。解析几何把所有的几何问题转换成 纯粹的代数问题，而代数问题是可以用计算机解决的
O
(xa, ya) a
△Oab的面积是(1/2)*|a|*|b|*sin
(1/2)*|a|*|b|*sin = (1/2)* a b
sin = a b / ( |a|*|b|)
2.1.4 二维叉积和三维叉积
a b xa ya b a xb yb
i jk
a b xa ya za yabz za yb i za xb xa zb j xa yb ya xb k
解析几何做法存在着计算误差，尤其在做除法运 算时
2.3.4 利用叉积判断线段相交
A
D
C
B
两条线段AB和CD规范相交等价于：A和B分属线 段CD所在直线的两侧；C和D分属线段AB所在直 线的两侧
判断A和B是否在线段CD所在直线的两侧可以判
断向量CD和CA的叉积是否与向量CD与CB的叉积
符号相反