0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I know and control that all line segments' start and end points are integers, and always parallel to both axes in the plane. $\endgroup$ – Ben C. Leggiero Mar 21 '17 at 0:45
  • 1
    $\begingroup$ For axes-parallel segments, it would probably be overkill to use an actual segment collision algorithm. You could just do some casework on whether segments are parallel or perpendicular, then compare the coordinates accordingly. $\endgroup$ – Misha Lavrov Mar 21 '17 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.