Python计算几何学——求两条线段的交点

首先是基于矩阵行列式的思路，这个思路来自于：http://dec3.jlu.edu.cn/webcourse/t000096/graphics/chapter5/01_1.html

def get_crossing(s1,s2):
    xa,ya = s1[0][0],s1[0][1]
    xb,yb = s1[1][0],s1[1][1]
    xc,yc = s2[0][0],s2[0][1]
    xd,yd = s2[1][0],s2[1][1]
    #判断两条直线是否相交，矩阵行列式计算
    a = np.matrix(
        [
            [xb-xa,-(xd-xc)],
            [yb-ya,-(yd-yc)]
        ]
    )
    delta = np.linalg.det(a)
    #不相交,返回两线段
    if np.fabs(delta) < 1e-6:
        print(delta)
        return None        
    #求两个参数lambda和miu
    c = np.matrix(
        [
            [xc-xa,-(xd-xc)],
            [yc-ya,-(yd-yc)]
        ]
    )
    d = np.matrix(
        [
            [xb-xa,xc-xa],
            [yb-ya,yc-ya]
        ]
    )
    lamb = np.linalg.det(c)/delta
    miu = np.linalg.det(d)/delta
    #相交
    if lamb <= 1 and lamb >= 0 and miu >= 0 and miu <= 1:
        x = xc + miu*(xd-xc)
        y = yc + miu*(yd-yc)
        return (x,y)
    #相交在延长线上
    else:
        return None

注：这个方法看起来挺有门道，其实速度很慢

实际用的时候，我使用的是下面这个先求直线交点，然后再判断交点是否在两条线段上的方法：

def inSegment(p,line,line2):
    '''
    检查某交点是否在线段line上（不含line的端点），在求交点时已经确认两条直线不平行
    所以，对于竖直的line，line2不可能竖直，却有可能水平，所以检查p是否在line2上，只能检查x值即p[0]
    '''
    if line[0][0] == line[1][0]:#如果line竖直
        if  p[1] > min(line[0][1],line[1][1]) and p[1] < max(line[0][1],line[1][1]):
            #if p[1] >= min(line2[0][1],line2[1][1]) and p[1] <= max(line2[0][1],line2[1][1]):
            if p[0] >= min(line2[0][0],line2[1][0]) and p[0] <= max(line2[0][0],line2[1][0]):
                return True
    elif line[0][1] == line[1][1]:#如果line水平
        if p[0] > min(line[0][0],line[1][0]) and p[0] < max(line[0][0],line[1][0]):
            #if p[0] >= min(line2[0][0],line2[1][0]) and p[0] <= max(line2[0][0],line2[1][0]):
            if p[1] >= min(line2[0][1],line2[1][1]) and p[1] <= max(line2[0][1],line2[1][1]):
                return True
    else:
        if p[0] > min(line[0][0],line[1][0]) and p[0] < max(line[0][0],line[1][0]):
            #line为斜线时，line2有可能竖直也有可能水平，所以对x和y都需要检查
            if p[1] >= min(line2[0][1],line2[1][1]) and p[1] <= max(line2[0][1],line2[1][1]) and p[0] >= min(line2[0][0],line2[1][0]) and p[0] <= max(line2[0][0],line2[1][0]):
                return True
    return False

def getLinePara(line):
    '''简化交点计算公式'''
    a = line[0][1] - line[1][1]
    b = line[1][0] - line[0][0]
    c = line[0][0] *line[1][1] - line[1][0] * line[0][1]
    return a,b,c

def getCrossPoint(line1,line2):
    '''计算交点坐标，此函数求的是line1中被line2所切割而得到的点，不含端点'''
    a1,b1,c1 = getLinePara(line1)
    a2,b2,c2 = getLinePara(line2)
    d = a1* b2 - a2 * b1
    p = [0,0]
    if d == 0:#d为0即line1和line2平行
        return ()
    else:
        p[0] = round((b1 * c2 - b2 * c1)*1.0 / d,2)#工作中需要处理有效位数，实际可以去掉round()
        p[1] = round((c1 * a2 - c2 * a1)*1.0 / d,2)
    p = tuple(p)
    if inSegment(p,line1,line2) and getLineLength(p,line1[0]) < 1e-3 and getLineLength(p,line1[1]) < 1e-3:
        #print(p)
        return p
    else:
        return ()

注：思路二求的是线段line1上的line1和line2 的交点，不含端点

有兴趣转行机器学习的朋友可以加群：

机器学习-菜鸡互啄群