GIS算法：1_两点线段是否相交

两点线段是否相交，是最经典的计算几何问题之一，它和点是否在多边形内，是所有GIS空间计算的基础。

计算两点线段是否相交，要通过两个步骤，首先判断它们的最小外包矩形（MBR）是否相交，如果外包矩形不相交，那么线段也不相交；如果外包矩形相交，那么进行叉积运算。

1.MBR快速排斥

即判断以两线段为对角线的矩形是否相交，若不相交，则两线段一定不相交。

判断两个矩形是否相交，只要任一矩形的最右端都大于另一矩形的最左端且任一矩形最高端大于另一矩形的最低端，则两矩形相交；反之，若其中任一条件不满足，两矩形不相交。

MBR快速排斥伪码：

isIntersectMBR：

if(

    max(p1.x,p2.x)>=min(p3.x,p4.x)    #矩形1最右端大于矩形2最左端

    and max(p3.x,p4.x)>=min(p1.x,p2.x)   #矩形2最右端大于矩形最左端

    and max(p1.y,p2.y)>=min(p3.y,p4.y)   #矩形1最高端大于矩形最低端

    and max(p3.y,p4.y)>=min(p1.y,p2.y) #矩形2最高端大于矩形最低端

): true

else:false

返回true，则最小外包矩形相交。

2.跨立实验

若两线段相交，则两线段必须跨立。

线段P1P2与线段P3P4相交，则P1和P2一定在线段P3P4的两侧。

判断线段P1P2跨立线段P3P4的条件是(P3P1×P3P4) ×(P3P2×P3P4)≤0

判断线段P3P4跨立线段P1P2的条件是(P2P3×P2P1) ×(P2P4×P2P1)≤0

等于0是共线情况。

跨立实验伪码：

叉积计算：

cross(p1,p2,p3):

    x1=p2.x-p1.x

    y1=p2.y-p1.y

    x2=p3.x-p1.x

    y2=p3.y-p1.y

    return x1*y2-x2*y1     

判断语句：

if(cross(p1,p2,p3)*cross(p1,p2,p4)<=0 and cross(p3,p4,p1)*cross(p3,p4,p2)<=0):true

else:false

如果isIntersectMBR为false，不相交。

如果isIntersectMBR为true，cross为false，则不相交，为true，则相交。