y′轴计算矩，那么矩具有旋转不变性。
y(xi , yj )O Nhomakorabeax
多边形位置由质心表示 多边形方向可由主轴定义
问题：如何用几何矩求面积？
m q p ( )dxdy pdx qdy x y k 1 Lk
令q=x,p=-y,得
1 m 1 m pk 1 S ydx xdy pk ydx xdy 2 k 1 pk pk 1 2 k 1 1 m ( xk yk 1 xk 1 yk ) 2 k 1
2 矢量


既有大小又有方向的量，也称向量。其几何意义一 般是指从起点指向终点的有向线段。 矢量的加减法 矢量的点乘：a· b=|a|· |b|· cos(a,b) 矢量的叉乘：∣a×b∣=|a|· |b|· sin(a,b)

矢量的混合积： (a×b)· c
3 点与线的关系

点在线上 点在有向线的左侧 点在有向线的右侧

思考：如何求线段与线段的距离？
12 几何矩
对于二元有界函数f ( x , y )，它的( j + k )阶矩为
M jk





x j y k f ( x, y )dxdy j, k 0,1,2,
集合{Mjk }对于函数f (x，y)是惟一的，也只有
f(x，y)才具有这种特定的矩集。
问题：用向量叉乘的方法能不能计算多边形的面积？ 如何判断多边形的走向是顺时针还是逆时针？
顺向点 逆向点
10 三角网剖分
简单多边形的三角剖分
离散点集的三角网剖分
11 点到线段的距离
11 点到线段的距离
如何判断角度是锐角还是钝角 如何计算点到直线的距离 （ 1 ）构建直线方程，利用点到直线的距离公式 求取距离。 （ 2 ）计算向量叉乘，其结果的一半为三角形的 面积，除以边长的2倍，即得高，就是要求的距 离。
6 线与面的关系

当N=-1时，令λ=│D1│/ (│D1│+│D2│) 若N2<0，则线段的[0,λ]间的部份在面的前面；
6 线与面的关系

当 N=0时，线段在面之上。此时线段在面的正面 或在面的背面。若另两个端点中有一端点在面的 前面，则此线段在 面的正面，可见；若另两端 点均在面之后，此时线段在面的背面，需和此面 比较，他们的投影公共部份即为棱的不可见部份。
计算机图形学基础
Computer Graphics
第三章 基本图形算法（三）
赵东保 华北水利水电学院 2011.9
1 概述
在计算机图形学中，经常需要处理一些共性的 问题，如判断两条线段是否相交，它们的交点 是多少；线段与面之间的位置关系；点是否落 在面内，点与线段的位置关系等等，这些问题 也是计算机图形学的基本问题。
7 面与面的关系

二维平面内，多边形的关系主要为 多边形之间相交 一个多边形在另一个多边形内 多边形之间相离
7 面与面的关系
三维空间内，如何判断多边形之间的遮挡关系？
8 射线求交
射线与直线求交 设直线方程为 ax+by+c=0 ，射线方程为 x=d1t+x0 ， y=d2t+y0。(t>0) 把射线方程代入直线方程有： (ad1+bd2)t+ax0+by0+c=0 若ad1+bd2=0，直线与射线平行 若ad1+bd2不为零，可求得t=-(ax0+by0+c)/(ad1+bd2) 若t<0，则无交点；t=0，直线与射线重合，t>0,则 有交点。
M ' jk
x 1 N j k ( x x ) ( y y ) f ( x, y ) y 1 M
3 主轴 使二阶中心矩从μ11变得最小的旋转角θ可以由下 式得出：
211 tan2 20 02
将x、y轴分别旋转θ角得坐标轴x′、y′，称为该物体的 主轴。如果物体在计算矩之前旋转θ角，或相对于x′、

5 线与线的关系



三维空间中，假定 Z 轴是深度 方向，如何判断空间两线段是 否相互遮挡？ 将两线段向XOY平面投影 利用参数方程求两投影线段的 交点，并获得参数λ，u。 将参数 λ ， u 代入 Z 方向的参数 方程，获得深度，比较深度可 判知遮挡关系
6 线与面的关系
二维平面内，主要有如下关系： 线段与面相交 线段在面内 线段与面相离
2 质心 当j=1, k=0 时，M10 对多边形区域来讲就是多边形区 域内所有点的 x 坐标的总和，类似地， M01 就是多边 形区域内所有点的y坐标的总和，所以
M10 M 01 x ,y M 00 M 00
就是物体的质心的坐标。 为了获得矩的不变特征，往往采用中心矩以及归 一化的中心矩。中心矩的定义为
12 几何矩
1 面积 参数j ＋k称为矩的阶。特别地，零阶矩是多边形的 面积， 即
M 00





f ( x, y )dxdy
对二维离散函数f (x，y)，零阶矩可表示为
M 00
x 1
N
f ( x, y )
y 1
M
所有的一阶矩和高阶矩除以M00后，与多边形区域大 小无关。
再令N=N1+N2
6 线与面的关系

则当N≤-2，线段在面的后面 N=0，线段在面上； N=-1，线段贯穿面； N>0，线段在面之前。（ N=1 和N=2 ）
6 线与面的关系

一条线段被一平面遮挡的判别原则如下： 当N>0时，面不遮挡线段，不用进行比较； 当N≤-2时，线段被面遮挡，两者在投影平面上的 公共部份即为线段被面遮挡的部份；

9 凸包的生成
步 1【找内点】：找到点集合的一个内点 G ，从 内点作水平向右的一向量L； 步 2【排序】：连接内点和全部点列，根据这些 连线与L的夹角按递增次序对点集排序，形成一 个双向链接表； 步 3【求凸包上的起点】：求取点列中的任一个 极点P0（X或Y的最小/大者）；
9 凸包的生成
步 4【求凸包上的一个顶点】：从 P0 出发依次考察连续 的三个顶点，如果是向逆向转（图中实心圆点），则前 进到下一点，否则删去三个顶点中的中间点（图中空心 圆点），且后退到上一点； 步5【求取凸包】：按步 4遍历点表，其结果即为点集的 有向凸包。这样求得的凸包是一个循环点列，选取任一 个起点均可作为凸包的起点。
5 线与线的关系


若A，B分别在CD的两侧；C，D分别在AB的两 侧则二者必相交 退化情况
5 线与线的关系
两线段的参数方程为：
两线段的交点应满足： 求得
代入u,v可得交点坐标
5 线与线的关系


三维空间中，怎样判断空间两线段是否相交，并 求出交点 参数方程求交 三点构成面，判断另一点是否在面上，再转为二 维平面上的判断线段是否相交 向三个平面投影：
3 点与线的关系

利用向量的叉乘可以判断点与线的各种关系
i a b xa xb j ya yb k 0 ( x a yb ya x b ) k 0
AB AD AB AC AB AE
4 点与面的关系

点在面内的包含性检测 空间一点是否在平面上
5 线与线的关系

判断两条线段是否相交 线段求交

8 射线求交
射线与面求交 假设面方程为 ax+by+cz+d=0 ，再设射线方程为 x=d1t+x0， y=d2t+y0，z=d3t+z0。(t>0) 把射线方程代入直线方程有： (ad1+bd2+cd3)t+ax0+by0+cz0+d=0 若ad1+bd2+cd3=0，射线与面平行 若ad1+bd2+cd3不为零，可求得 t=-(ax0+by0+cz0+d)/(ad1+bd2+cd3) 。若 t<0 ，则无 交点；t=0，射线与面重合，t>0,则有交点。
6 线与面的关系

二维平面内，如何判断线段在面内？

两个条件： （1）线段两端点都在面内 （2）线段和多边形边不相交 线段与多边形的交点如何求取？

6 线与面的关系

三维空间内，如何判断线段与面的遮挡关系 设线段的两端点为P1(x1,y1,z1)，P2(x2,y2,z2) 平面方程：Ax+By+Cz+D=0 令 D1= Ax1+By1+Cz1+D D2= Ax2+By2+Cz2+D 当D1(D2)<0 设 N1(N2)=-2 当D1(D2)=0 设N1(N2)=0 当D1(D2)>0 设N1(N2)=1