平面两线段相对位置的矢积判断算法

在计算机绘图中,常常要对平面内两线段是否有交、或交点是否有效,进行大量的判断运算。本文提出了一种矢积判断算法。运用该方法,经一次判断后,可排除50％—70％两线段无交或交点无效的情况。最多判断两次,两线段无交或交点无效的情况,即可完全排除。无交的两线段,不再参与以后的求交运算,大大减少了求交运算量,使得求交的速度比目前常用的一些方法明显加快。

A KIND JUDGING COMPUTATION BY VECTOR PRODUCT TO DECIDE VELATIVE PLACE OF TWO SEGMENT LINES IN A PLANE

Using the computer to made a drawing needs a large amounts of judging computations which decide whether two segment lines in a plane have a cross or have an effective point of intasection.This paper proposes a kind judging computation ly vector product. This method is taken so that we can exclude the situation that the two segment lines have sope-rcent to 70 percent passilility to come to no cross ot to no effective point of intersection only after one judgement. At most by two judements, the situation that the two segment lines have no cross or no effective point of intersection can be excluded.The two segment lines with no cross will no longer take part in the following computation which finds crosses, thus greatly reducing the computation of finding crosses, leaving the speed of finding crosses obviously fast compared to some method adopted to the present moment.