As we continue to look at different computational geometry problems, one simple, yet important test is to see whether a given point lies on a line segment. Similar to our previous posts, we will be utilizing the cross product and dot product to check for the proper conditions. Hopefully, these computations have become second nature now. Again, I have uploaded the script checkPointOnSegment.m if you want to test on your own.

We will first define our segments and point of interest. Our segment will consist of a 2×2 array, with each row specifying each endpoint A and B, and a point C will be defined as a 2 element array. For example, given the following, we have a line from (-1,4) to (3,-2) and want to check if the point (1,1) lies on the segment.

>> segment = [-1 4; 3 -2];
>> C = [1 1];

Let’s now define the line segment as a vector from point A (-1,4) to point B(3,-2) and the vector AC:

A = segment(1,:);
B = segment(2,:);
% form vectors for the line segment (AB) and the point to one endpoint of
% segment
AB = B - A;
AC = C - A;

As we have shown previously, collinearity can be checked through the cross product. If the cross product of AB and AC is 0, then the segments have a 0 or 180 degree angle between them and are therefore collinear. We can do this simple check for whether a point is on a line, given our definition of cross. Note: if you use Matlab’s built-in cross, you’ll have to append 0’s to all of your vectors, but you will still obtain the same results.

% if not collinear then return false as point cannot be on segment
if cross(AB, AC) == 0
    checkPt = true;
end
%% Cross product returning z value
function z = cross(a, b)
    z = a(1)*b(2) - a(2)*b(1);

Alas, a line segment is different than a line, in that it has endpoints, while a line continues to infinity in both directions. So we need to perform some additional checks for whether the point is beyond the limits of the line segment. While we could do some simple > or < checks, let's use the dot product to see whether the point lies on the line segment or is found at the endpoints. So our complete code will be:

% if not collinear then return false as point cannot be on segment
if cross(AB, AC) == 0
    % calculate the dotproduct of (AB, AC) and (AB, AB) to see point is now
    % on the segment
    dotAB = dot(AB, AB);
    dotAC = dot(AB, AC);
    % on end points of segment
    if dotAC == 0 || dotAC == dotAB
        onEnd = true;
        checkPt = true;
    % on segment
    elseif dotAC > 0 && dotAC < dotAB
        checkPt = true;
    end
end

Let’s look at some examples. Please feel free to try on your own and let us know how it works for you.

[checkPt, onEnd] = checkPointOnSegment(segment, C, true)
checkPt =
  logical
   1

onEnd =
  logical
   0

[checkPt, onEnd] = checkPointOnSegment(segment, [7,-5], true)
checkPt =
  logical
   0

onEnd =
  logical
   0