java - 检查投影在线段上的点是否不在它之外

Question

见上图；基本上，我想要一个简单的测试来检查一个点是否在线段的范围内。我拥有的信息（或输入，如果您愿意）是点的坐标和线段终止点的坐标。我想要的输出是一个简单的布尔值。我怎样才能以简单的方式检查这个？

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

确定通过粗线端点的那些垂直虚线的方程式并不难。

让粗线由点和定义。然后，它有一个斜率(x1, y1)(x2, y2)

m = (y 2 - y 1 ) / (x 2 - x 1 )

所以所有垂直线的形式都是

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

我们可以用它来确定穿过和（分别）的垂直线的方程，它们基本上表示所有有效点必须驻留的区域的边界：(x1, y1)(x2, y2)

y a (x) = (-1/m)x + y 1 + x 1 /m
y b (x) = (-1/m)x + y 2 + x 2 /m

因此，对于任意点(x*, y*)，要确定它是否在有效区域内，您可以测试是否

y a (x*) <= y* <= y b (x*)

（或者如果更大则相反）ya(x*)

---

以下应该可以解决问题：

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

Answer 3

您可以通过计算角度来做到这一点。

假设您的端点是 (x1,y1) 和 (x2,y2)，而您的点是 (x,y)。

然后创建两个向量，从一个端点到另一个端点，一个端点到您的点：

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

计算点积：

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

现在点积除以幅度为您提供角度的余弦：

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

现在的诀窍是，如果你的角度大于PI / 2，你就“出局”了

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

Answer 4

我接受了 Daniel Fischer 的回答，这很好，并针对 3D 和 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;
}