One computational geometry question that we will want to address is how to determine the intersection of two line segments. This will allow for further solutions for more complex questions, including a general solution regarding whether a point is inside or outside of a convex or non-convex polygon. Previously, we’ve described how to define a line segment in MATLAB, and we will use this definition in our current method for solving for line intersections.
Note: Much credit for this post and explanation should be given to Gareth Rees. While preparing this post, I ran across his response, and I can’t do it much more justice, so here is his general implementation in MATLAB.
There are 5 possibilities if we have two line segments:
1) The two line segments are collinear and overlapping (intersecting portion is a line segment)
2) The two line segments are collinear and disjoint (not intersecting)
3) The two line segments are parallel (not intersecting)
4) Not parallel and intersect
5) Not parallel and non-intersecting
In order to determine collinearity and intersections, we will take advantage of the cross product. A cross product returns the vector perpendicular to two given vectors. Alternatively, if two segments are parallel, the cross product will be 0 (as A X B = |A|*|B|*sin(theta), and theta of 0 or 180 will return 0), and this will provide a great check for discriminating possibilities 1,2,3 and 4,5. The built-in cross MATLAB function will provide the cross product of two vectors, but doing so requires that the vectors be defined in three dimensions. We can therefore either append a 0 to all of our 2-D line segments or use the following function, which returns only the k vector (ignoring the i and j vectors) of the cross product.
%% Cross product returning z valuefunction z = cross(a, b) z = a(1)*b(2) - a(2)*b(1);
Now let’s define our function “checkSegmentIntersection”, which will take as input two line segments (A and B). These input arguments will be 2×2 arrays with each row describing the endpoints of the line segment. The output arguments of “doesIntersect” will be a boolean value true/false and “intersection” will provide the intersection point (or line segment) if there is an intersection (or overlap). Our default initialization of “false” and NaN will be the outputs for the second, third and fifth possibilities. We will therefore only check for the first and fourth possibilities.
function [doesIntersect, intersection] = checkSegmentIntersection(A, B) % Check if two line segments (A and B) intersect in 2D space. % initialize output values doesIntersect = false; intersection = NaN;
As we described previously, we will utilize parametric equations for the two line segments, such that segment1 = p + t*r and segment2 = q + u*s, where t and u range from 0 to 1.
% Solve for all of these variables given the two line segmentsp = A(1,:);r = parameterizeLine(A(1,:), A(2,:));q = B(1,:);s = parameterizeLine(B(1,:), B(2,:));Then, as described by Gareth Rees, we can solve for the intersection using the following two equations:
% t = (q-p) x s/(r x s)% u = (q-p) x r/(r x s)% Solve for cross productsr_cross_s = cross(r, s);q_p_cross_s = cross(q-p, s);q_p_cross_r = cross(q-p, r);% solve for t and ut = q_p_cross_s / r_cross_s;u = q_p_cross_r / r_cross_s;
Now, let’s check if the two line segments are collinear or parallel. If the line segments are collinear/parallel and q_p_cross_r is not 0, then there is no intersection. Otherwise, if it is 0, we will find the line segment where overlapping occurs.
%% First Possibilityif r_cross_s == 0 if q_p_cross_r == 0 t0 = dot(q-p,r)/dot(r,r); if t0 >= 0 && t0 <= 1 doesIntersect = true; % return a line segment where intersection occurs intersection = [p; p+t0*r]; end end
On the other hand, if the line segments are not parallel (r_cross_s ~= 0), then we check to see if they intersect within the range of 0 to 1 for both u and t.
%% Fourth possibilityelse if t >= 0 && t <= 1 && u >=0 && u <= 1 doesIntersect = true; intersection = p + t * r; end end
Let’s do some validation of our code. First, for condition 1, let’s use A = [4 -1; 0 5]; and B = [3 0.5; 6 -4]; I’ve uploaded a version of the code that includes plotResults as an input argument if you want to give it a try, but here would be the output:
[doesInt, inter] = checkSegmentIntersection(A,B,true)doesInt = logical 1inter = 4.0000 -1.0000 3.0000 0.5000
For conditions 2 and 3, we would need collinear lines that do not intersect and parallel lines, respectively. Let’s use A = [4 -1; 0 5]; B = [6 -4; 8 -7] and [5 0; 1 6], respectively. Both conditions will return the following results for the intersection, with the following graphical representations.
[doesInt, inter] = checkSegmentIntersection(A,B,true)doesInt = logical 0inter = NaN
For condition 4, let’s generate line segments that intersect. Using A = [4 -1; 0 5]; and B = [5 2; 1 -2];
[doesInt, inter] = checkSegmentIntersection(A,B,true)doesInt = logical 1inter = 3.2000 0.2000
Finally, non-parallel lines that do not intersect. A = [4 -1; 0 5]; and B = [0 0 2 1];
[doesInt, inter] = checkSegmentIntersection(A,B,true)doesInt = logical 0inter = NaN
Take a look at the uploaded checkSegmentIntersection.m file if you want to try some line segment examples as well. If you have any comments or questions, please feel free to let us know.
