土石方计算原理.doc

渠道堤防土石方工程量计算编程原理分析 康李建 （水利部河北水利水电勘测设计研究院，天津，300250） 摘要：渠道堤防设计时，经常要计算渠堤的填方和挖方等土石方工程量，应用计算几何算法编制程序，提高工程量计算的效率和精度。 关键词：渠道堤防；土石方工程量；编程原理；计算几何 1、前言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。通过掌握计算几何的一些基本算法，应用计算几何的知识便可以解决工程中遇到的实际问题。 在进行渠道堤防设计时，经常要计算渠堤的填方和挖方等土石方工程量，用手工计算费时又费力，而且容易出错，误差较大，如果编制电算程序来计算，就可以大大减轻设计人员的工作负担，提高计算速度，得到准确的工程量计算结果。而我们在编制电算程序时，就要用到计算几何的一些算法。 计算渠道堤防土石方工程量，必须有地形横断面资料和渠道堤防断面要素，把地形横断面上的点连起来就是一条折线，同样渠道堤防断面要素组成的点也可以连成一条折线，两条折线肯定有多个交点，从而使这两条折线构成一个或数个多边形，我们只要计算出这一个或多个多边形的面积，渠道堤防的土石方工程量就可以准确的计算出来。 由此可见，我们通过编程计算渠堤土石方工程量时，首先要判断上述两条折线的交点情况；其次根据交点情况，判断各个多边形所代表的土石方挖填类型；然后计算出各个多边形的面积即可求出土石方工程量。 在实际工作中，求渠道内坡和地面线的交点，只要求出两条线段的交点即可；而要计算渠道外坡和地面线的交点，由于外坡与地面的交点为未知点，就需要求出由地面线构成的线段和由外坡构成的直线的交点。因此，在求折线交点时，需要用到的计算几何的算法包括：判断两线段是否相交、判断线段和直线是否相交、计算线段或直线与线段的交点。 我们分两步确定两条线段是否相交： (1)快速排斥试验 设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交。 (2)跨立试验 如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2上；同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。 所以判断线段P1P2和Q1Q2相交的依据是（两式中有一个成立即可）： ( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) = 0 ( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) = 0 2.1.2判断线段和直线是否相交 如果线段P1P2和直线Q1Q2相交，则P1P2跨立Q1Q2，即： ( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) = 0。 对于两条共线的线段，它们之间的位置关系有以下几种情况：两条线段没有交点、两条线段有无穷交点、两条线段有一个交点。设line1是两条线段中较长的一条，line2是较短的一条，如果line1包含了line2的两个端点，两线段有无穷交点；如果line1只包含line2的一个端点，那么如果line1的某个端点等于被line1包含的line2的那个端点，这时两线段只有一个交点，否则两线段也是有无穷的交点；如果line1不包含line2的任何端点，这时两线段没有交点。 设一条线段为L0 = P1P2，另一条线段或直线为L1 = Q1Q2 ，计算L0和L1的交点的过程为： （1）首先判断L0和L1是否相交，如果不相交则没有交点，否则说明L0和L1一定有交点，下面就将L0和L1都看作直线来考虑。