(Projected) Point on Line (2D) Algorithm 
Download Article and Source (70 kb)
Introduction
This little article presents different algorithms about the relation of a given point to a given line in the twodimension case. In detail, following topics are addressed:
In every case, we have following input data:
1. Is test point on a line using yintercept form ?
In this chapter it is tested if the given point p lies on the line using the yintercept form which is wellknown from school :) This form defines a line using its slope (against the xcoordinate) and the intersection with the ycoordinate (yintercept):
The general equation of a line is y = m*x + b
where m is the slope (defined as Δy/Δx) and b the yintercept. m = dy / dx = v_{2}.y  v_{1}.y / v_{2}.x  v_{1}.x

Having calulcated the slope, it is now used to derive the yintercept by just inserting one of the two points (here v_{1} is used, but could be also interchanged with v_{2}):
The line to test against is now completely defined by the yintercept form. To check if the test point p lies on it, this equation can be easily used.
By putting the coordinate of the testpoint into the equation and using the actual line slope m, the yintercept of test point p called b(p) should be equal to that of the line in case the test point lies on the line:
If b(p) = b, the pt lies on the line.
Drawbacks:
2. Is point on a line using the perp dot product ?
The perp dot product provides a more better way for solving. Recall the perp dot product (PDP) of two twodimensional vector e_{1} = (e_{1}.x, e_{1}.y) and e_{2} = (e_{2}.x, e_{2}.y) is defined as
and actually calculates the area of the parallelogram spanned by the two vectors e_{1} and e_{2} as shown in the diagram below:
Particularly, this implies that the pdp is 0 if both vectors e_{1} and e_{2} are parallel. If the two vectors are defined by the three points v_{1}, v_{2} and p as shown in the figure above, it results obviously in the fact that the pdp is zero only if the p lies on the line e_{1} = vector from v_{1} to v_{2}.
/** * Calculates the area of the parallelogram of the three points. * This is actually the same as the area of the triangle defined by the three points, multiplied by 2. * @return 2 * triangleArea(a,b,c) */ float perpDotProduct(Point a, Point b, Point c) { return (a.x  c.x) * (b.y  c.y)  (a.y  c.y) * (b.x  c.x); } 
Again, there is the floatingpoint accuraccy problem, so instead of checking against zero, some epsilon value has to be used. Because the size of the pdp value depends on the length of the vectors, no static value can be used. One approach is to compare the pdp/area value to the fraction of another area which also depends on the length of the line e_{1}=(v_{1}, v_{2}), e.g. the area of the square with side e_{1} which is computed below in function getEpsilon():
public double getEpsilon() { int dx1 = v2.x  v1.x; int dy1 = v2.y  v1.y; double epsilon = 0.003 * (dx1 * dx1 + dy1 * dy1); return epsilon; } 
In conclusion, the check if the point p lies on line v_{1}v_{2} is then:
boolean isPointOnLineviaPDP() { return ( Math.abs(perpDotProduct(v1, v2, p) < getEpsilon()) ); } 
3. Is point on a line segment using the perp dot product ?
The previous chapter explained how to test if the test point p lies on the given line in general, but not if it's on the closed line segment between both points in particular.
However, this turns out to be quite simple: The test point must lie inside the bounding box spanned by the two line points. Look at the figure below:
The xcoordinate of the test point must lie in between the xcoordinates of both line points:
Note that '<=' is used instead of '<' to include also the endpoints of the line segment. The very same is also done for the ycoordinates:
In conclusion, the test point lies on the line segment if it lies on the general line (using algorithm of chapter 2) and it the test point is inside the bounding box. Below is the complete function to the line segment test:
/** * Check if the point is on the line segment. */ public boolean isPointOnLineSegmentViaCrossProduct() { if (!( (v1.x <= p.x && p.x <= v2.x)  (v2.x <= p.x && p.x <= v1.x) )) { // test point not in xrange return false; } if (!( (v1.y <= p.y && p.y <= v2.y)  (v2.y <= p.y && p.y <= v1.y) )) { // test point not in yrange return false; } return isPointOnLineviaPDP(); } 
4. Is the projection of a point on a line segment using the perp dot product ?
In this chapter an algorithm is presented to test if the projected point p' of the point p onto the line e_{1} lies on inside the closed line segment.
The projected point p' is the nearest point to p that lies on the given line. Have a look at the figures below:
Projected point p' is on line segment
Projected point p' is not on line segment
In the left figure, the projected point p' lies inside the line segement, while this is not the case in the right figure.
To handle this problem, we use the dot product this (not the perp dot product!).
The dot product (DP) and perp dot product (PDP) are related, but are not identical.
Both calculate a scalar value from two vectors. However, the perp dot product is obtained by calculating the dot product of one vector with the perpendicular vector (the one that is 90 degrees rotated) of the other one. Direct comparison of equations:
where v1, v2 are the length of the vector and α is the angle between both vectors.
Because the perpendicular vector v' of a vector v (x1, y1) is v'(y1, x1), the derived definition of PDP from DP is obvious.
Let's get back to the actual problem:
Consider the vectors e_{1} = (v_{2}, v_{1}) and e_{2} = (pv_{1}).
Here follows the code:
/** * Check if the projected testpoint onto the line is on the line segment. * @return true if projected point is on line segment, false otherwise */ public boolean isProjectedPointOnLineSegment() { // get dotproduct e1 * e2 Point e1 = new Point(v2.x  v1.x, v2.y  v1.y); int recArea = dotProduct(e1, e1); // dot product of e1 * e2 Point e2 = new Point(p.x  v1.x, p.y  v1.y); double val = dotProduct(e1, e2); return (val > 0 && val < recArea); } 
5. What are the coordinates of the projected point on a line segment using the perp dot product ?
In the previous chapter it was only checked if the projected point p' lies on the line segment v_{1}v_{2}, however the actual coordinates were not calculated. This is now caught up in this final section!
Let's have a look at the following figure:
At first let's calculate angle α using the dot product. We know that DP(e_{1}, e_{2}) = e_{1} * e_{2} * cos(α). As we know all three points and so also the vectors e_{1} and e_{2}, it's easy to get cos(α):
Because the line pp' (blue line in the figure) is perpendicular to e_{1}, cos(α) is also defined as cos(α) = v_{1}p' / e_{2}, so we can get the length of the line segment from v_{1} to p':
As the points v_{1} and v_{2} are known as well as the distance from v_{1} to p', we starting from v_{1} we can just 'go along' to p'. In particular, the position of p' is can be calculated as:
Here the code of the whole function:
/** * Get projected point P' of P on line e1. * @return projected point p. */ public Point getProjectedPointOnLine() { // get dot product of e1, e2 Point e1 = new Point(v2.x  v1.x, v2.y  v1.y); Point e2 = new Point(p.x  v1.x, p.y  v1.y); double valDp = dotProduct(e1, e2); // get length of vectors double lenLineE1 = Math.sqrt(e1.x * e1.x + e1.y * e1.y); double lenLineE2 = Math.sqrt(e2.x * e2.x + e2.y * e2.y); double cos = valDp / (lenLineE1 * lenLineE2); // length of v1P' double projLenOfLine = cos * lenLineE2; Point p = new Point((int)(v1.x + (projLenOfLine * e1.x) / lenLineE1), (int)(v1.y + (projLenOfLine * e1.y) / lenLineE1)); return p; } 
Be inspecting this calculation, a simplification is possible. Rechecking the calculation of variables cos, projLenOfLine and final calculation of p'.x and putting it altogether, we get following (example for xcoordinate, analogous for the ycoordinate):
Calculating the length of the lines e1 and e2 is quite expensive due to the square root.
However, the equation above deptics that lenLineE2 cancels out itself. Furthermore, the calculation contains lenLineE1 * lenLineE1 which also removes the sqaure root and is simply: e1.x * e1.x + e1.y * e1.y. These facts are used in the optimized version of getProjectedPointOnLine() below:
/** * Get projected point P' of P on line e1. Faster version. * @return projected point p. */ public Point getProjectedPointOnLineFast() { // get dot product of e1, e2 Point e1 = new Point(v2.x  v1.x, v2.y  v1.y); Point e2 = new Point(p.x  v1.x, p.y  v1.y); double valDp = dotProduct(e1, e2); // get squared length of e1 double len2 = e1.x * e1.x + e1.y * e1.y; Point p = new Point((int)(v1.x + (val * e1.x) / len2), (int)(v1.y + (val * e1.y) / len2)); return p; } 
Sunshine, December 2013
This site is part of Sunshine's Homepage