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

Question

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

Answer 1

使用内积可以进行简单统一的检查。两个向量之间的内积可以在几何上可视化为两个向量的长度乘以两者之间角度的余弦的乘积，或者向量之一的长度与（正交）投影的长度的乘积另一个到由该向量确定的线上。

在您的情况下，如果将向量

v

从线段的端点之一投影到所考虑的点，当且仅当投影落在连接两个线段

s

上时，该点位于允许的区域内端点。这相当于

0 <= v·s <= s·s

（如果要排除通过端点垂直于线段的线，则严格不等式）

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 = (y2 - y1) / (x2 - x1)

所以所有垂直线都将具有以下形式

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

我们可以用它来确定分别穿过

(x1, y1)

和

(x2, y2)

的垂线方程，它们本质上表示所有有效点必须驻留在其中的区域的边界：

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

所以，对于任意点

(x*, y*)

，要判断它是否位于有效区域内，可以测试是否

ya(x*) <= y* <= yb(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

我采纳了 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;
}

Answer 4

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

假设你的端点是（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 5

最简单的方法是计算两个端点之一之间的直线和向量的点积。如果点积在 0 和 1 之间，那么你的点投影就在线上