计算几何学课件

1/60,计算几何学,2/60,叉积点积,计算几何的基本工具,计算几何的常见问题总结,3/60,叉积（外积）,已知有向线段op1=(x1,y1),op2=(x2,y2)op1与op2叉积表示为：op1op2几何意义：是以op1、op2为边的平行四边形的有向面积。即op1op2=|op1|*|op2|*sin(a)，0=a0，则向量op1到op2成逆时针；即op2在op1的左边。b.若op1op20，则向量op1到op2成顺时针；即op2在op1的右边。c.若op1op2=0，则向量op1和向量op2共线.(同向或反向)。,叉积-“左右”判定,a,b,c,左,右,p1(x1,y1),O,5/60,叉积点积,计算几何的基本工具,计算几何的常见问题总结,6/60,点积（内积）,已知有向线段op1=(x1,y1),op2=(x2,y2)op1与op2的点积表示为op1op21.几何意义：OP1在OP2上的的投影OP1与OP2的长度乘积op1op2=|op2|*|op1|*cos(a)，0=a0，则op1（op2）指向op2（op1）的前方,且共线时取最大值若0，则向量p0p2在p0p1的左边，因此在p1点左转若0，则向量p0p2在p0p1的右边，因此在p1点右转若=0，则说明点p0、p1和p2共线,p1,p2,p0,左,右,右,11/60,线段方面的问题,判断连续线段的左右转向判断线段是否与水平射线相交判断两线段是否相交判断任意两线段是否相交计算点到线段的距离小结,12/60,判断线段是否与水平射线相交,Ya=Yp=Yb点p在ab的右边,即abap0,addb0,判断交点是否在线段上（d是否在ab上）,16/60,判断线段是否相交,无同号，有0,判断交点是否在线段上,returnfalse,returntrue,returntrue,真,假,是,否,有同号,returnfalse,17/60,线段方面的问题,判断连续线段的左右转向判断线段是否与水平射线相交判断两线段是否相交判断任意一对线段是否相交计算点到线段的距离小结,18/60,确定任意一对线段是否相交,使用扫除的技术,即假设一条垂直扫除线沿X轴方向从左到右移动,每遇到线段端点,就进行一定的操作。,前提：1.没有线段是垂直的;2.没有三条输入线段相交于同一点;,设一序列T，当线段的左端点遇到扫除线时,线段就按交点的y值递减的插入到序列T中,当其右端点遇到扫除线时离开序列T。,b,ab,abc,dbc,ced,e,dbc,de,abc,T序列,ced,Y,19/60,b,ab,abc,dbc,dbc,abc,对所有线段的端点按x值从小到大进行排序。若存在x值相同的点，将左端点排前；若都为左端点，将y值小的排前。,不相交,不相交,不相交,相交,for(每个端点p),左端点,右端点,将线段插入到T中,判断是否与其相邻的元素相交,判断它的上下相邻元素之间是否相交，并删除,returntrue,处理下个端点,是,是,否,否,O(nlgn),returntrue,只能判断是否有交点，不能求交点个数,20/60,不相交,相交,for(每个点p),左端点,右端点,将线段插入到T中,判断是否与其相邻的元素相交,判断它的上下相邻元素之间是否相交，并删除,将交点插到顶点序列中,处理下个点,是,否,O(nlgn),交点,a,ba,cba,Q1,cab,相交,Q2,count+,acb,不相交,acb,cb,b,交换所属线段的位置，再判断是否与其相邻的元素相交,是,处理下个点,将交点插到顶点序列中,是,否,否,可求交点个数,21/60,线段方面的问题,判断连续线段的左右转向判断线段是否与水平射线相交判断两线段是否相交判断任意一对线段是否相交计算点到线段的距离小结,22/60,点到线段距离已知点A,B,C的坐标，求点C到线段AB的距离；设CH为三角形CAB的高。三角形ABC的面积有两种计算方法：(1)1/2（|AB|*|CH|）(2)1/2|ACAB|因此距离|CH|=|ACAB|/|AB|=,A,B,C,H,23/60,线段方面的问题,判断连续线段的左右转向判断线段是否与水平射线相交判断两线段是否相交判断任意两线段是否相交计算点到线段的距离小结,24/60,线段方面问题的小结,判断连续线段的左右转向判断线段ab是否与点p的向左水平射线L相交判断两线段是否相交判断任意一对线段是否相交计算点到线段的距离,用叉积正负号判断,YaYp=d，则R中最多只有6个S中的点。Proof:,在分治法的合并步骤中最多只需要检查6n/2=3n个候选者,O(nlogn),d,d,任意两点距离=对角线距离,p1,p2,R,55/60,最近、最远点对问题,寻找最近点对寻找最远点对小结,56/60,寻找最远点对,用格雷厄姆扫描法或步进法求凸包(O(nlogn)用旋转卡壳算法求凸包直径，也就找到了最远点对(O(n),这一对最远点必然存在于这n个点所构成的凸包上。且一定是凸包直径的两端点,平均复杂度O(nlogn)。,方法：,57/60,最近、最远点对问题小结,寻找最近点对寻找最远点对,:分治法递归的寻找,:先求出凸包，再找到凸包的直径,58/60,叉积点积,计算几何的基本工具,总结,计算几何的常见问题,线段