Posted on June 20th, 2014
In the Point in Polygon Test post we used a Ray-Line Segment intersection test in order to figure out how many sides of the polygon intersected a test ray. This post will explain how that test was derived.
Find out if a ray with origin and direction intersects a line segment with end points and .
This problem can be converted into a Ray-Ray intersection problem if you turn the line segment into a ray with origin and direction but we are not going to do that. Well we are, but not explicitly.
Checking if two things intersect involves finding out if they share at least one common point. The first step is to express the ray and the line segment as sets of points.
In parametric form, the ray becomes
The line segment on the other hand is
Next we can set the two equations to be equal and find the values of and . Since there are two dimensions the equality can be split into the and counterparts and give us two equations to solve for the two unknowns. Once and are calculated the ray and the segment intersect if and . Under these conditions the point of intersection is on both the ray and the line segment.
After Some Algebra
The solution simplifies very neatly if you make some substitutions. Let , and . Intuitively, is just the direction perpendicular to . The result:
The symmetry is pretty cool!