栏目
/ Category
联系我们
/ CONTACT US
  • 地 址:江苏省如皋市中山路东方豪都6楼
  • 电 话:0513-87289069/68760932
  • 传 真:0513-87289069
  • 邮 箱:webmaster@jsyyl.com
技术文章|两线段相交的快速判断法

一、数学是科技的王者:


在哲学被指责为玄学和功利科学的时代,数学是唯一不受外部学科批判的学术系统。随着计算机被广泛应用于理工科的分析过程中,数学有被逐渐边缘化的趋势。而事实上,数学一直是大学系统里最神圣最宏伟的学科,千年以来始终掌握着话语权。即便是计算机迅猛发展的时代,数学的重要性也一直在凸显,电脑无法替代那些严谨的公式和缜密的逻辑,更无法脱离数学给予它的强力支持。


二、问题的引入:


在地下车库预应力有限元设计过程中,为了计算最终普通钢筋数量,需要判断一根梁、一个板带中有几根预应力筋,以往的做法是根据预应力筋展开图,逐根读取每个板带、每根梁中的预应力筋数量,然后写入数据文件,最后程序根据该数据文件直接完成截面配筋计算。


每个板带都是一个区域,其中包含多少根预应力筋,可以在ObjectArx中应用IntersectWith函数去计算。图1中包含5万多根预应力筋,两万多个板带,如果逐个去比较计算,至少要比较10亿多次。




图1、招商双玺三期地下车库顶板预应力筋布置图


三、快速排斥:


初步判断,以两条线段为对角线的矩形,如果不重合的话,那么两条线段一定不可能相交。如图2。

图2、快速排斥法


两条线段组成的矩形可能重合的条件有且只有以下四条:

1、线段ab的低点低于cd的最高点(可能重合)

2、cd的最左端小于ab的最右端(可能重合)

3、cd的最低点低于ab的最高点(加上条件1,两线段在竖直方向上重合)

4、ab的最左端小于cd的最右端(加上条件2,两直线在水平方向上重合)


代码实现(C++)如下:

if(min(a.x,b.x)<=max(c.x,d.x) && min(c.y,d.y)<=max(a.y,b.y)&&min(c.x,d.x)<=max(a.x,b.x) && min(a.y,b.y)<=max(c.y,d.y));

return true;


四、跨立试验:


1、传统算法:


初等几何判断两根直线是否相交,是通过直线参数方程的方法,求解出两个直线方程的交点,然后判断该交点是否在线段范围之内。


清华大学出版的《计算机图形学》一书中给出了一种参数化向量求解方法,该方法在本质上仍然是求解方程组的解,通过判定方程组的解是否在限定的区间来确定线段是否相交,若相交再进一步求解交点。


线段相交问题,首先要判断两线段是否会相交,然后再考虑求交点。上述两种方法都是先求解方程组,再通过对解的合理性的判断来确定线段是否相交。这种思路必然会因为求解方程组而带来大量的计算,影响效率。


2、算法几何:


算法几何应用矢量代数的原理,给出了简洁的判断算法,即跨立试验方法。


如果两条线段相交,那么必须跨立,就是以一条线段为标准,另一条线段的两端点一定在这条线段的两段。


图3、跨立试验


也就是如图3所示:a b两点在线段cd的两端,c d两点在线段ab的两端。


3、矢量外积:


矢量外积也就是矢量叉乘。


矢量外积的数值在这里不再讨论,这里关注的重点是矢量外积的数值,也就是方向。


图4、连续线段的转向


如图4所示,P0P1矢量与P0P2矢量叉乘时,若数值大于0,则可以判断PoP2位于P0P1的右侧,反之则在左侧。依此原理,可以得到图3跨立试验的基本表达式。


4、跨立试验基本表达式:


(1)(ca x cd)·(cb x cd)<=0  说明ca cb先对于cd的方向不同,则a b在线段cd的两侧。


(2)(ac x ab·(ad x ab) <=0,说明 c d点在线段ab的两侧。


以上条件为判断线段ab、cd是否相交的充分必要条件,包含相交点在线段上的情形。


5、代码实现(C++)


double u,v,w,z;//分别记录两个向量


u=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);


v=(d.x-a.x)*(b.y-a.y)-(b.x-a.x)*(d.y-a.y);


w=(a.x-c.x)*(d.y-c.y)-(d.x-c.x)*(a.y-c.y);


z=(b.x-c.x)*(d.y-c.y)-(d.x-c.x)*(b.y-c.y);


return (u*v<=0.00000001 && w*z<=0.00000001);


五、结论:


1、应用快速排斥法,筛选出少数几条合乎条件的预应力筋线段,然后再应用跨立试验,确定与板带相交的线段,从而可以方便地根据图形导出每根板带中包含的预应力筋数量和面积。


2、矢量代数可以方便、优雅地解决了最常见的线段相交问题。


3、简单的程序代码,蕴含着数学的智慧,使得计算程序的效率成倍提升。

上一篇:技术文章|盐城外国语学校综合楼桁架节点验算
下一篇:工程案例|宁荣新城翠湖苑有粘结预应力地下车库顶板竣工报告
返回顶部