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?

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;
}

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);
}