《陈可卿几何与计算》PPT课件

《《陈可卿几何与计算》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、几何与计算清华大学计算机系陈可卿代数与几何几何在实际生活中被人们广泛的应用。但是，一开始人们只能用直观的绘图来描绘几何，简单直观，但是难以拓展。如何让人们可以通过，最方便的代数计算，来实现对几何的描述，操作？于是，便有了计算几何。今天我要讲的就是与几何相关的，计算机问题。二维向量(x,y)向量的长度向量的内积向量的叉积加减法……内积两个向量是否垂直等价用于计算两个向量夹角，是否在同180°内。叉积两个向量是否平行等价等价于两个向量张成的平行四边形面积。可以用于计算面积。（有向面积）例1给N个点，问每个点在下列图形中第几块。线段之间不相交简单计算点到直线距离内积性质简单

2、多边形面积计算利用有向面积点是否在凸多边形内利用叉积凸包计算利用叉积的方向判断例2一个蚂蚁，只会向左走，且走出来的路径不相交。现在给出N（≤50）个点，求这个蚂蚁可以走的最长路径。（从左下角的点开始）知识预备为了方便后面介绍三维，以及更广泛计算几何的应用，我们先介绍一下矩阵和行列式。矩阵简单的矩阵矩阵计算矩阵加法矩阵乘法乘法满足结合律，不满足交换律。例3矩阵的应用求用1*2的多米诺骨牌，覆盖5*N的棋盘的方法数。（N≤109）矩阵的其他计算矩阵的转置矩阵的逆矩阵的分块计算……例4对于多元一次方程组，我们写成矩阵形式简写行列式行列式定义1、2、3、4、行列式计算满足上述

3、4个性质的任何计算出来的值，都叫做行列式。不过可以证明，这样计算的值是唯一的。行列式的计算方法很多，这里介绍两种。行列式展开（便于理解）对角化（便于计算）行列式应用N个向量其行列式值就是N维空间中，由这N个向量张成的空间体的体积。比如，2维，3维。行列式应用（2）对于多元一次方程组，我们写成矩阵形式我们可以用高斯消元法，也可以使用Cramer法则其中这种方法，有其理论价值，以及在小范围计算时的价值。直线相交直线一般式解方程解得直线相交(扩展)交点不存在直线与线段，线段与线段相交判断点是否，在线段上通过距离判断两点式到一般式三维向量(x,y,z)向量的长度向量的内积加减

4、法……三维叉积叉积意义方向：垂直两向量构成平面模长：张成的平行四边形面积用途平行判断，求法向量，等等三维向量的计算应用求点到直线距离求点到平面距离求两直线之间距离求直线到面的距离求直线到面的夹角……例5在三维空间中，有N个球体，现在从坐标原点，朝方向(x,y,z)发射一束光线。当光线射到球面时，会发生反射（入射角等于反射角）求光线运动的轨迹（输出前k个，光线碰到的球）特殊坐标表示除了我们常用的坐标表示方式之外，还有许多有用的坐标表示方式。接下来，我们介绍两个对于二维坐标平面的特殊表示方法。复平面射影坐标复平面复数a+bi可以看成坐标点(a,b)加减乘除复数运算的意义加

5、减法：同普通向量计算乘法：模长相乘，角度相加除法：模长相除，角度相减所以复数也可以用极坐标表示法例6在平面上有一个三角形△ABC，这个三角形通过一些列的平移，旋转，缩放变换，变成了△A’B’C’。问在原三角形中一点P，在变换后，P’的坐标。复平面应用用于只涉及平移、旋转、缩放的坐标变换坐标旋转(x,y)*(cosa,sina)=(xcosa-ysina,xsina+ycosa)eix=cosx+isinx(傅里叶变换等等)射影坐标在普通坐标系中引入无穷远点无穷远点1、每条直线上有一个无穷远点2、平行直线交与无穷远点3、所有无穷远点构成一个直线射影平面坐标表示法对于普通

6、点(x,y)(x,y,1)或者说(a,b,c)其中a/c=x,b/c=y,c≠0对于无穷远点(a,b,c),c=0坐标(0,0,0)无意义，且任意两直线都有交点。射影平面上的直线射影平面上直线和点一样，也可以用坐标表示。用X表示点X=(x1,x2,x3)用U表示直线U=(u1,u2,u3)则X在直线U上有，X·U=0（看成三维内积）X1，X2两点连成直线U=X1×X2（叉积）射影平面上的直线（续）由于射影平面上的点与直线有对偶性，可以类似推导出则直线U通过点X，U·X=0U1，U2两直线交与点X=U1×U2对称的，如果U=(0,0,u3)则，直线非正常直线。射影坐标

7、应用求两直线交点不需要再推导麻烦的公式，可以直接求的，而且也不用考虑特殊情况。如果没有焦点，则x3=0。求点到直线距离例如求点X到直线U的距离，可以直接计算得交点。X’=(U×X)×U再计算两点距离射影坐标应用(续)混合积应用三个点X1,X2,X3(X1×X2)·X3=0（三点共线）三条直线U1,U2,U3(U1×U2)·U3=0（三线公点）等等可以推导，应用各种对偶性质例6如下图，要求在PropertyLine上找一个点，使得，在这个点上观察，House不被任何障碍挡住。一些特殊的计算几何方法半平面交顾名思义，就是将一些半平面求交。思想为凸多边形和