javamathgeometrycomputational-geometry

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


illustration

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?


Solution

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