> 判断两线段是否相交
> 我们分两步确定两条线段是否相交：
> (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 ) * ( Q2 - Q1 ) × ( P2 - 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
> 同理判断Q1Q2跨立P1P2的依据是：
> 
> ( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) ≥ 0
> 

• 有无穷个交点的时候就麻烦了 (0) frkstyc 2006-04-22 19:50:11