一种快速判断线段相交的方法.pdfVIP

!’ 测 绘 通 报 !!’ 年 第 ( 期 文章编号：!#$!#%%（!!’）!($!!’!$! 中图分类号：)!* 文献标识码：+ 一种快速判断线段相交的方法 李永红，华一新 （信息工程大学 测绘学院，河南 郑州 ,!!,） ! #$%’ $ ()*+,-. !//#//*01 $%# 20$#3/#+$*0 4 5*0# 6#17#0$/ -. /012$3012，456 /7$871 摘要：线段相交是在拓扑计算、等高线检查、多边形裁剪等 9.: 空间分析中经常要碰到的问题。提出一种判定线段相交的混合积 判定准则，大大减少计算量。 关键词：混合积；混合积判定准则；相交 一、常规思路及存在的问题 三、混合积判定准则 判定两条直线段的相交情况通常有两种方法。 设有两线段 ， ，如图 。 !% ! % % 一是把线段直线化，列出直线方程，求出可能的交 点，进而判断方程组的解是否同时在两条直线段上； 二是运用向量代数，清华大学出版的《计算机图形 学》一书中给出了一种参数化向量求解方法，该方法 在本质上仍然是求解方程组的解，通过判定方程组 的解是否在限定的区间来确定线段是否相交，若相 交再进一步求解交点。 线段相交问题，首先要判断两线段是否会相交， 图 然后再考虑求交点。上述两种方法都是先求解方程 % 组，再通过对解的合理性的判断来确定线段是否相 ， 垂直 ， 所在平面。 交。这种思路必然会因为求解方程组而带来大量的 !% # % #% !% ! % 则线段 ， 相交的判定条件，即充分 计算，影响效率。在 中经常需要判断一条线段与 !% ! % 9.: 必要条件是 许多条链的相交关系，而其中满足相交关系的链的数 ［ ］［ ］ 目是比较少的，即使用线段的外接矩形进行过滤，也 !% ! !% % !% # !% ! !% !% # ? ? 会有许多不可能相交的线段参与了计算。因此，提高 !! !% ［ ］［ ］? 效率的关键在于提高判定方法的质量，排除干扰链。 %