Check if a point projected on a line segment is not outside it

Question

See the image above; basically, I want a simple test to check if a point is within the line segment's range. The information (or input, if you prefer) I have is the point's coordinates, and the line segment termination points' coordinates. The output I want is a simple boolean. How can I check this in a simple way?

Aymara

Interesting reading regarding this subject: sunshine2k.de/coding/java/PointOnLine/PointOnLine.html – Eadwina

Answer 1

You can have a simple and uniform check if you use the inner product. The inner product between two vectors can be geometrically visualised as the product of the lengths of the two vectors time the cosine of the angle between the two, or the product of the length of one of the vectors and the length of the (orthogonal) projection of the other onto the line determined by that vector.

In your situation, if you project the vector v from one of the endpoints of the segment to the point under consideration, the point lies inside the allowed region if and only if the projection falls on the segment s connecting the two endpoints. And that is equivalent to

0 <= v·s <= s·s

(strict inequalities if you want to exclude the lines perpendicular to the segment through the endpoints)

public static boolean inRange(double start_x, double start_y, double end_x, double end_y,
                              double point_x, double point_y) {
    double dx = end_x - start_x;
    double dy = end_y - start_y;
    double innerProduct = (point_x - start_x)*dx + (point_y - start_y)*dy;
    return 0 <= innerProduct && innerProduct <= dx*dx + dy*dy;
}

Birdbath

Answer 2

It's not hard to determine the equations of those perpendicular dotted lines passing through the endpoints of your bold line.

Let the bold line be defined by the points (x1, y1) and (x2, y2). Then, it has a slope

m = (y2 - y1) / (x2 - x1)

So all perpendicular lines will be of the form

y(x) = (-1/m)x + c

We can use that to determine the equations of the perpendicular lines that pass through (x1, y1) and (x2, y2) (respectively), which essentially represent the boundary of the region in which all valid points must reside:

ya(x) = (-1/m)x + y1 + x1/m
yb(x) = (-1/m)x + y2 + x2/m

So, for an arbitrary point (x*, y*), to determine if it lies in the valid region, you can test whether

ya(x*) <= y* <= yb(x*)

(or the reverse if ya(x*) is larger)

---

The following should do the trick:

public static boolean check(double x1, double y1, double x2, double y2,
            double x, double y) {

    if (x1 == x2) {  // special case
        return y1 < y2 ? (y1 <= y && y <= y2) : (y2 <= y && y <= y1);
    }

    double m = (y2 - y1) / (x2 - x1);
    double r1 = x1 + m * y1;
    double r2 = x2 + m * y2;
    double r = x + m * y;
    return r1 < r2 ? (r1 <= r && r <= r2) : (r2 <= r && r <= r1);
}

Emmott

Answer 3

I took Daniel Fischer answer which is great, and adjusted it for 3D and Unity:

public bool InSegmentRange(Vector3 start, Vector3 end, Vector3 point) {
    Vector3 delta = end - start;
    float innerProduct = (point.x - start.x) * delta.x + (point.y - start.y) * delta.y + (point.z - start.z) * delta.z;
    return innerProduct >= 0 && innerProduct <= delta.x * delta.x + delta.y * delta.y + delta.z * delta.z;
}

Baggage

This answer brings nothing new – Weepy

Why not? Might be useful for someone who needs to do this in 3D instead of 2D – Baggage

Answer 4

You can do this by computing the angles.

Suppose your endpoints are (x1,y1) and (x2,y2), and your point is (x,y).

Then you create two vectors, from one endpoint to other, and one endpoint to your point:

vec1 = (x - x1, y - y1);
vec2 = (x2 - x1, y2 - y1);

Compute the dot product:

double dotp = (x-x1) * (x2-x1) + (y-y1) * (y2 - y1);

Now the dot product divided by magnitude gives you the cosine of the angle:

double theta = Math.acos((dtop) / (Math.sqrt((x-x1) * (x-x1) + (y-y1) * (y-y1)) 
       * Math.sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1))));

Now the trick is that if your angle is greater than PI / 2, you are 'out'

public static boolean check(double x, double y, double x1, double y1, 
                            double x2, double y2) {
    // vectors are (dx1, dy1) and (dx2, dy2)
    double dx1 = x - x1, dx2 = x2 - x1, dy1 = y - y1, dy2 = y2 - y1;

    double dotp = dx1 * dx2 + dy1 * dy2;
    double theta = Math.acos(dotp  / (Math.sqrt(dx1 * dx1 + dy1 * dy1) 
                                      * Math.sqrt(dx2 * dx2 + dy2 * dy2)));
    theta = Math.abs(theta);

    if (theta > (Math.PI / 2))
        return false;
    dx1 = x - x2;
    dx2 = x1 - x2;
    dy1 = y - y2;
    dy2 = y1 - y2;
    dotp = dx1 * dx2 + dy1 * dy2;
    theta = Math.acos(dotp  / (Math.sqrt(dx1 * dx1 + dy1 * dy1) 
                               * Math.sqrt(dx2 * dx2 + dy2 * dy2)));
    theta = Math.abs(theta);

    if (theta > (Math.PI / 2))
        return false;
    return true;
}

Limerick

Answer 5

Simplest way is to calculate the dot product of your line and vector between one of the two termination points. if dot product is between 0 and 1 then your point projection is on the line

dot=AB.AP=AB(x)*AP(x) + AB(y)*AP(y)
if(dot<1 && dot>0){
Projection is on the line
}

if you want to know more, then Wikipedia had explained it very well.

Ortolan

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Berns