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.

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 and **s**̂ vectors described in my last post. An example is shown in Fig. 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 **L**_{1} and **L**_{2} determined by their end points (see Fig. 2↓)
**L**_{1}: **P**_{11}, **P**_{12}
**L**_{2}:** P**_{21}, **P**_{22}
.
Letting the vectors **d**_{k} = **P**_{k2} − **P**_{k1}, *k* = 1, 2 be the vectors from the start to the end points of the two segments, points on the segments are **r**_{1} = **P**_{11} + *s***d**_{1} and **r**_{2} = **P**_{21} + *t***d**_{2} with 0 ≤ *s* < 1 and 0 ≤ *t* < 1. At the point of intersection, **r**_{1} and **r**_{2} are equal
**r**_{1} = P_{11} + *s***d**_{1} = **r**_{2} = **P**_{21} + *t***d**_{2}
Rearranging terms

Now let **n**_{k} be vectors perpendicular to **d**_{k}, *k* = 1, 2. If we use complex numbers to represent the vectors, we can compute the perpendicular vectors by multiplying by *e*^{iπ ⁄ 2} = *i* so **n**_{k} = *i***d**_{k}. Taking the dot product of both sides of Eq. 1↑, we can solve for *s*_{int} and *t*_{int}. Dotting first with **n**_{2} and solving
*s*_{int} = (**D**⋅**n**_{2})/(**d**_{1}⋅**n**_{2})
and then with **n**_{1}
*t*_{int} = − (**D**⋅**n**_{1})/(**d**_{2}⋅**n**_{1}).
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 *s*_{int} or *t*_{int} 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
**P**_{intersect} = **P**_{11} + *s*_{int}**d**_{1}

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↓.

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] : *Geometric Tools for Computer Graphics*. Morgan Kaufmann, 2002.