Check if a point projected on a line segment is no

问题:

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?

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

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

回答3:

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

回答4:

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