混合积判断线段相交的方法分析.docxVIP

混合积判断线段相交的方法分析混合积判断线段相交的方法分析 文章编号:1003—5850(2006)lO一0034—02 混合积判断线段相交的方法分析 AnAnalysisofTwoSegmentsIntersectionJudgmentwithMixedProduct 王舒鹏方莉 (武汉大学武汉430079) 【摘要1判断线段相交是许多算法都要解决的问题,介绍了一种利用混合积来判断线段相交的方法,并给出了 这种方法的严密数学基础和基于VisualC++的编程实现过程.对其中所用到的定理给予严密的数学证明.该方 法形式简单,运算量较小,适用范围广,乃判断线段相交的理想方法之一. 【关键词】线段相交,混合积,向量几何,分析 中图分类号:P208文献标识码:A ABSTRACTJudgingwhethertWOsegmentsintersectisacommonprobleminmucharithmeticthathastObesolved.Thisarticle mainlypresentsamethodwhichjudgessegmentintersectionbyusingthetoolofmixedproduct,anddescribestheprecisemath baseandtheprocessofprogrammingimplementation.Themaththeorembeingusedhasbeenprovedprecisely.Thismethod,asan idealoneinjudgingsegmentintersection,ischaracterizedwithsimpleform,lessamountofoperationandwidelyused. KEYWORDSsegmentintersection,mixedproduct,vectorgeometry,analysis 判断两条线段相交与否是地理信息系统中许多算 法所要解决的问题之一.一般来说判断线段相交的方 法主要有以下两种:一是把两线段所在的直线方程解 出,求出直线间的交点,再判断该交点是否在两条线段 上;另一种方法是利用向量几何中混合积的性质,通过 判断由端点所构成的向量与辅助向量的混合积的正负 来判断两线段是否相交.由于第一种方法需要联立方 程解方程组,再判断解的合理性,所以如果针对仅要求 判断线段是否相交的问题来说显然计算量太大,效率 不高.而第二种方法恰恰针对第一种算法的不足,充分 挖掘线段相交的几何特征,引入几何工具大大提高了 判断线段相交的效率. 1混合积的概念及相关定理的严密证 明 设.;,,;为三个向量,称(×)?;为三个向量的 混合积(mixedproduct,scalartripleproduct).也可记 作(,,:). 引理三个向量,,;的混合积的绝对值等于这 三个向量张成的平行六面体的体积.当,,构成右 手系时混合积取正值,构成左手系时混合积取负值. 证明:①如果,,;共面,则外积×垂直于这 个平面从而也垂直向量C,所以(口×6)?C一0;这时以 ,,为三条棱构成的平行六面体5退化为平面,5 *2006—04—03收到,2006—08—23改回 **王舒鹏,男,1984年生,在读本科,研究方向:摄影测量,遥感. 的体积为0; ②如果这三个向量不共面,在空间中取一点O,以 0为始点作3个有向,因此 (口×6)一CS*h一一V 证毕. 图1三向量不共面图 2混合积判定准则 由以上的定理可以推出判断线段相交的一种通用 方法.设有两线段PP.,QQ,其中Pz为辅助向量. 向量PP,PQ,Pz,PQ在直角坐标系中的坐标分 别为(xl,yl,z1),(x2,y2,z2),(x3,y3,z3),(x4,y4, z4).判断线段相交图如图2所示. 已知向量PP,PlQ,Pz成右手系;PP:,PQ, 第19卷第1o期电脑开发与应用 PP,PQ,Pz的混合积 『l2z3『 II (PlP2,P1Q2,Plz)一fl23f≤0. llI 212223I 向量Pz为辅助向量,所以它的坐标可以设为 (O,0,1),则得到混合积判定准则的一般表达形式: (xl2一2y1)≥0且(xly4--x4y1)≤0. 已知以上的判定准则包含了端点相交,端点在线 段上,线段重合的情况.所以该准则在判断线段相交时 不用分多种情况讨论,使用起来十分方便. 3这种判断方法的程序表达 intInteraction(Associationa,Associationb) //a,b是两条已知线段,Association是一个表示线段的类,可 以用字典来实现 ffloatd1,d2,d3,d4; floatakx,aky,avx,avy,bkx,bky,bvx,