Is there a line segment intersection-finding algorithm that accounts for collinear segments?

Question

I've found many algorithms online for finding the intersection point of two line segments, but they completely fail when the line segments in question are collinear. For instance, if I have one line segment from $(-1, 2)$ to $(1, 2)$, and another from $(1, 2)$ to $(2, 2)$, the algorithm should say they intersect at $(1, 2)$, but all the ones I've tried say they don't intersect at all. _{(This seems to be due to them relying on division, and when they're collinear like this, it's division by $0$)}

Is there a formula/algorithm to find the intersection point of two line segments that accounts for collinearity?

Answer 1

Handling this case generally is tricky for two reasons:

1. Floating-point precision. A really tiny change to the coordinates produces segments that are parallel but not collinear, or segments that are almost but not quite parallel, so they lie on lines that intersect very very far away.

2. Non-uniqueness. In your case, the two segments intersect at a single point, but in general, collinear segments can have an intersection which is itself a segment. What do you say when you want to take the intersection of the segment from $(0,0)$ to $(2,2)$ with the segment from $(1,1)$ to $(3,3)$?

If you know your segments' coordinates exactly (say, they're given as integers, even though the intersections might not have integer coordinates) and you're assuming the second issue won't come up, then you can check this yourself just by checking if the two segments share an endpoint.

If you don't know your segments' coordinates exactly, it's probably best to assume they're never collinear, and avoid this case.