aprendtech.com >> blog >> this post
If you have trouble viewing this, try the pdf of this post. You can download the code used to produce the figures in this post.

Intersection of line segments using complex variables in Matlab

NOTE: Sep. 2, 2011, this is a substantial edit of my previous post to explain more details.
A post by Loren Shure of Mathworks, reminded me of a function, PolylineIntersectSegment.m, that I wrote to compute the intersection of a polyline with a line segment. This function nicely combines the topics of my last two posts, use of complex variables as vectors and lines, so I will discuss it in more detail. The use of complex variables simplifies the code and makes it easier to understand and modify.
A polyline[1] is a set of connected line segments. Line segments are naturally specified by their start and end points instead of the n and ŝ vectors described in my last post. An example is shown in Fig. 1↓
figure SingleLine.png
Figure 1 A line segment is specified by its start and end points,  P1,  P2. From these, we can compute the difference vector d =  P1 −  P2 and a point on the line segment is r =  P1 + sd 0 ≤ s < 1.
In a polyline, as shown in Fig. 3↓, the end point of one segment is the start point of the next. The four points (1 − 4) define a three segment polyline (shown in blue). A polyline is in general not closed although it can be. In addition, the segments of the polyline can cross.
The PolylineIntersectSegment.m function code is based on the intersection between two segments L1 and L2 determined by their end points (see Fig. 2↓)
L1P11,  P12 L2: P21,  P22 .
Letting the vectors dk = Pk2 − Pk1,   k = 1, 2 be the vectors from the start to the end points of the two segments, points on the segments are r1 = P11 + sd1 and r2 = P21 + td2 with 0 ≤ s < 1 and 0 ≤ t < 1. At the point of intersection, r1 and r2 are equal
r1 = P11 + sd1 = r2 = P21 + td2
Rearranging terms
(1) sd1 − td2 = P21 − P11 = D.
figure Intersect2lines2D.png
Figure 2 Intersection of two line segments.
Now let nk be vectors perpendicular to dk,  k = 1, 2. If we use complex numbers to represent the vectors, we can compute the perpendicular vectors by multiplying by eiπ ⁄ 2 = i so nk = idk. Taking the dot product of both sides of Eq. 1↑, we can solve for sint and tint. Dotting first with n2 and solving
sint = (Dn2)/(d1n2)
and then with n1
tint =  − (Dn1)/(d2n1).
We can then test that 0 ≤ s < 1 and 0 ≤ t < 1 for intersection points. I use open intervals to avoid duplicate hits when segments intersect at end points. You can change this test depending on how inclusive you want to make your definition of intersection to be. This will depend on your application so I do not think there is a single correct answer. The test in the code is shown below and it easy to change. If the segments are parallel or have zero length, then there will be a division by zero. Matlab will return a NaN for sint or tint and the logical test will return false indicating no intersection. You can also modify the code to test for these and do something different.
% test for intersection in PolylineIntersectSegment
intersectsOK = (s>=0)&(s<1)&(t>=0)&(t<1);
The actual point of intersection will be
Pintersect = P11 + sintd1
The code of PolylineIntersectSegment.m (see the zip file for this post) shows how the use of complex variables simplifies things. As noted above, to find a perpendicular vector, multiply the vector by i, which rotates it by 90 degrees. All the Matlab functions like diff work with complex variables. The code is a straightforward implementation of the equations. Some examples are given with the zip file and are shown in the box. The polyline in the third example is shown in Fig. 3↓.
figure IntersectExample.png
Figure 3 Example of intersection of a line segment and a polyline. The test segment is in red, the polyline in blue with vertexes numbered, and the intersection points are circles.
%%  intersect of 2 lines
zseg = [0 1i]; % line along the y axis
p1 = [-.5 .5] + 0.5*1i; % line segment parallel to x-axis at y=0.5
zi = PolylineIntersectSegment(zseg,p1);
%% add another segment along same direction as first one but of zero length
% only chooses the intersection with the correct segment
p1null = [p1, p1(end)];
zi = PolylineIntersectSegment(zseg,p1null);
%% add another segment along same direction as first one
% only chooses the intersection with the correct segment
p2 = [p1, (1.5+0.5i)];
zi = PolylineIntersectSegment(zseg,p2);
%% add segment parallel to test segment in y-direction
% ignores segments to test segment
p3 = [p2,(1.5+2i)];
zi = PolylineIntersectSegment(zseg,p3);
%% display results
fh = figure;
hold on
hold off
axis([-2 2 -2 2])
The code uses the zdot function for the dot product of two vectors represented as complex variables.
function d = zdot(z1,z2) % dot product for complex vectors
     d = real( z1(:) .* conj(z2(:)));
Last edited Sep. 1, 2011
© 2011 by Aprend Technology and Robert E. Alvarez
Linking is allowed but reposting or mirroring is expressly forbidden.


[1] Philip Schneider, David H. Eberly: Geometric Tools for Computer Graphics. Morgan Kaufmann, 2002.