```# # intersections.py # # Python for finding line intersections # intended to be easily adaptable for line-segment intersections # import math def intersectLines( pt1, pt2, ptA, ptB ): """ this returns the intersection of Line(pt1,pt2) and Line(ptA,ptB) returns a tuple: (xi, yi, valid, r, s), where (xi, yi) is the intersection r is the scalar multiple such that (xi,yi) = pt1 + r*(pt2-pt1) s is the scalar multiple such that (xi,yi) = pt1 + s*(ptB-ptA) valid == 0 if there are 0 or inf. intersections (invalid) valid == 1 if it has a unique intersection ON the segment """ DET_TOLERANCE = 0.00000001 # the first line is pt1 + r*(pt2-pt1) # in component form: x1, y1 = pt1; x2, y2 = pt2 dx1 = x2 - x1; dy1 = y2 - y1 # the second line is ptA + s*(ptB-ptA) x, y = ptA; xB, yB = ptB; dx = xB - x; dy = yB - y; # we need to find the (typically unique) values of r and s # that will satisfy # # (x1, y1) + r(dx1, dy1) = (x, y) + s(dx, dy) # # which is the same as # # [ dx1 -dx ][ r ] = [ x-x1 ] # [ dy1 -dy ][ s ] = [ y-y1 ] # # whose solution is # # [ r ] = _1_ [ -dy dx ] [ x-x1 ] # [ s ] = DET [ -dy1 dx1 ] [ y-y1 ] # # where DET = (-dx1 * dy + dy1 * dx) # # if DET is too small, they're parallel # DET = (-dx1 * dy + dy1 * dx) if math.fabs(DET) < DET_TOLERANCE: return (0,0,0,0,0) # now, the determinant should be OK DETinv = 1.0/DET # find the scalar amount along the "self" segment r = DETinv * (-dy * (x-x1) + dx * (y-y1)) # find the scalar amount along the input line s = DETinv * (-dy1 * (x-x1) + dx1 * (y-y1)) # return the average of the two descriptions xi = (x1 + r*dx1 + x + s*dx)/2.0 yi = (y1 + r*dy1 + y + s*dy)/2.0 return ( xi, yi, 1, r, s ) def testIntersection( pt1, pt2, ptA, ptB ): """ prints out a test for checking by hand... """ print "Line segment #1 runs from", pt1, "to", pt2 print "Line segment #2 runs from", ptA, "to", ptB result = intersectLines( pt1, pt2, ptA, ptB ) print " Intersection result =", result print if __name__ == "__main__": pt1 = (10,10) pt2 = (20,20) pt3 = (10,20) pt4 = (20,10) pt5 = (40,20) testIntersection( pt1, pt2, pt3, pt4 ) testIntersection( pt1, pt3, pt2, pt4 ) testIntersection( pt1, pt2, pt4, pt5 ) ```