python - Arithmetic accuracy issues while testing for intersection of two line segments -

i wrote code testing intersection of 2 line segments in plane. won't bother details.

the code takes 2 line segments, each described 2 end-points, fits each segment line fitting a , b in y = a*x + b. finds intersection point of 2 lines x = (b2 - b1) / (a2 - a1). last, tests if intersection point x contained within 2 line segments.

the relevant part looks this:

# line parameterization = delta y / delta x, b = y - a*x a1 = (line1.edge2.y - line1.edge1.y) / (line1.edge2.x - line1.edge1.x) b1 = line1.edge1.y - a1 * line1.edge1.x a2 = (line2.edge2.y - line2.edge1.y) / (line2.edge2.x - line2.edge1.x) b2 = line2.edge1.y - a2 * line2.edge1.x # intersection's x x = - (b2 - b1) / (a2 - a1) # if intersection x within interval of each segment # there intersection if (isininterval(x, line1.edge1.x, line1.edge2.x) ,     isininterval(x, line2.edge1.x, line2.edge2.x)):     return true else:     return false 

for brevity dropped lot of tests handling specific cases when edges parallel each other (a1==a2), when on same line, when edge of length 0, when edge along vertical axis (then a becomes infinite) etc.

the function isininterval simply

def isininterval(x0, x1, x2):     """tests if x0 in interval x1 x2"""     if x1 <= x0 <= x2 or x2 <= x0 <= x1:         return true     else:         return false 

now question: find due roundoff errors, test give false results when intersection coincides segment edge.

for example, line1 between (0,0) , (3,5) , line2 between (3,5) , (7,1) resulting intersection x 2.9999999999999996, gives false answer. should have been 3.

can please suggest solution?

this problem/feature of floating point arithmetic. there ways minimise error, ordering instructions ways, in end, approximate answers, because you're representing possibly infinite numbers finite number of bits.

you need define whatever functions build in such way tolerant of these errors. looking @ example, difference between "proper" value , got of order 1e-16 - extremely extremely low.

with inequality , equality, it's worth relax constraints exact/bitewise matching. example, if wanted test x == 3, write abs(x - 3) < epsilon, epsilon = 1e-6 or epsilon = 1e-9. basically, difference between want have , have smaller small value. ditto, inequality, might test 3 - epsilon <= x or x <= 3 + epsilon.