java - 检查点 (x,y) 是否在直线上绘制的两点之间

Question

我在两点 A(x,y)---B(x,y) 之间画了一条线，现在我有了第三个点 C(x,y)。我想知道如果 C 位于 A 和 B 之间绘制的线上。我想用 java 语言来做。我找到了几个类似的答案。但是，每个人都有一些问题，没有人是完美的。

Answer 1

if (distance(A, C) + distance(B, C) == distance(A, B))
    return true; // C is on the line.
return false;    // C is not on the line.

要不就：

return distance(A, C) + distance(B, C) == distance(A, B);

其工作方式相当简单。如果 CAB在线，您将得到以下场景：

A-C------B

并且，无论它在那条线上的哪个位置，dist(AC) + dist(CB) == dist(AB). 对于任何其他情况，您有一些描述的三角形和“dist(AC) + dist(CB) > dist(AB)”：

A-----B
 \   /
  \ /
   C

事实上，即使 C 位于外推线上，这也有效：

C---A-------B

前提是距离保持无符号。距离dist(AB)可以计算为：

  ___________________________
 /           2              2
V (A.x - B.x)  + (A.y - B.y)

请记住浮点运算的固有限制（有限精度）。您可能需要选择“足够接近”的测试（例如，小于百万分之一的错误）以确保等式的正确运行。

Answer 2

注意力！仅限数学！

你可以试试这个公式。把你的A(x1, y1)和B(x2, y2)坐标放到公式中，然后你会得到类似的东西

y = k*x + b; // k and b - numbers

然后，任何满足这个等式的点都在你的线上。要检查C(x, y)介于A(x1, y1)和之间，B(x2, y2)请检查：(x1<x<x2 && y1<y<y2) || (x1>x>x2 && y1>y>y2)

例子

A(2,3) B(6,5)

直线方程：

(y - 3)/(5 - 3) = (x - 2)/(6 - 2)
(y - 3)/2 = (x - 2)/4
4*(y - 3) = 2*(x - 2)
4y - 12 = 2x - 4
4y = 2x + 8
y = 1/2 * x + 2; // equation of line. k = 1/2, b = 2;

让我们检查一下是否C(4,4)在这条线上。

2<4<6 & 3<4<5 // C between A and B

现在将 C 坐标代入方程：

4 = 1/2 * 4 + 2
4 = 2 + 2 // equal, C is on line AB

PS：正如@paxdiablo 所写，您需要在计算之前检查线是水平还是垂直。只需检查

y1 == y2 || x1 == x2

Answer 3

我相信最简单的是

// is BC inline with AC or visa-versa
public static boolean inLine(Point A, Point B, Point C) {
   // if AC is vertical
   if (A.x == C.x) return B.x == C.x;
   // if AC is horizontal
   if (A.y == C.y) return B.y == C.y;
   // match the gradients
   return (A.x - C.x)*(A.y - C.y) == (C.x - B.x)*(C.y - B.y);
}

您可以通过将 x 值的差除以 y 值的差来计算梯度。

注意：如果在屏幕上绘制 C 是否出现在 A 和 B 之间的线上，有一个不同的测试。数学假设 A、B、C 是无限小的点。实际上非常小到表示误差之内。

Answer 4

上面的答案是不必要的复杂。最简单的如下。

1. 如果 (x-x1)/(x2-x1) = (y-y1)/(y2-y1) = alpha（一个常数），则点 C(x,y) 将位于点 1 和 2 之间的线上.

2. 如果 alpha < 0.0，则 C 在点 1 的外部。

3. 如果 alpha > 1.0，则 C 在点 2 的外部。
4. 最后，如果 alpha = [0,1.0]，则 C 在 1 和 2 的内部。

希望这个答案有帮助。

Answer 5

我认为这里的所有方法都有一个缺陷，因为它们没有尽可能严格地处理舍入误差。基本上，所描述的方法会告诉你你的点是否足够接近使用一些简单的算法的线，并且它或多或少是精确的。

为什么精度很重要？因为这是op提出的问题。对于计算机程序，没有直线上的点，只有直线的 epsilon 内的点，并且需要记录该 epsilon 是什么。

让我们来说明问题。使用距离比较算法：

假设一个段从 (0, 0) 到 (0, 2000)，我们在应用程序中使用浮点数（大约有 7 个小数位精度），我们测试 (1E-6, 1000) 上的点是否是上线与否。

从线段的任一端到该点的距离为 1000.0000000005 或 1000 + 5E-10，因此，与该点的距离之和的差值约为 1E-9。但是这些值都不能存储在具有足够精度的浮点数上，并且该方法将返回true。

如果我们使用更精确的方法，比如计算到直线中最近点的距离，它会返回一个浮点数有足够精度存储的值，我们可以根据可接受的 epsilon 返回 false。

我在示例中使用了浮点数，但同样适用于任何浮点类型，例如双精度。

一种解决方案是使用 BigDecimal 以及您想要的任何方法，如果不会导致性能和内存命中问题。

一种比比较浮点距离更精确的方法，更重要的是，始终精确，尽管计算成本更高，是计算到直线中最近点的距离。

点到线段的最短距离

看起来我正在分裂头发，但我之前不得不处理这个问题。这是链接几何运算时的一个问题。如果您不控制要处理的精度损失类型，最终您将遇到困难的错误，这将迫使您对代码进行严格的推理以修复它们。

Answer 6

我认为这可能会有所帮助

如何检查一个点是否位于另外两个点之间的线上

该解决方案仅使用整数，因为您只提供整数，这也消除了一些陷阱

Answer 7

我相信一个简单的方法是检查由 3 个点形成的角度。如果角度 ACB 是 180 度（或接近它，取决于您想要的准确度），则点 C 位于 A 和 B 之间。

Answer 8

这是我的 C# 解决方案。我相信 Java 等价物几乎是相同的。

笔记：

1. 仅当该点在线的范围内（它不假定无限线）时，方法才会返回 true。

2. 它将处理垂直或水平线。

3. 它计算被检查点与线的距离，因此允许将容差传递给该方法。

    /// <summary>
    /// Check if Point C is on the line AB
    /// </summary>
    public static bool IsOnLine(Point A, Point B, Point C, double tolerance)
    {
        double minX = Math.Min(A.X, B.X) - tolerance;
        double maxX = Math.Max(A.X, B.X) + tolerance;
        double minY = Math.Min(A.Y, B.Y) - tolerance;
        double maxY = Math.Max(A.Y, B.Y) + tolerance;
   
        //Check C is within the bounds of the line
        if (C.X >= maxX || C.X <= minX || C.Y <= minY || C.Y >= maxY)
        {
            return false;
        }
   
        // Check for when AB is vertical
        if (A.X == B.X)
        {
            if (Math.Abs(A.X - C.X) >= tolerance)
            {
                return false;
            }
            return true;
        }
   
        // Check for when AB is horizontal
        if (A.Y == B.Y)
        {
            if (Math.Abs(A.Y - C.Y) >= tolerance)
            {
                return false;
            }
            return true;
        }
   
   
        // Check istance of the point form the line
        double distFromLine = Math.Abs(((B.X - A.X)*(A.Y - C.Y))-((A.X - C.X)*(B.Y - A.Y))) / Math.Sqrt((B.X - A.X) * (B.X - A.X) + (B.Y - A.Y) * (B.Y - A.Y));
   
        if (distFromLine >= tolerance)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
   

Answer 9

def DistBetwPoints(p1, p2):
    return math.sqrt( (p2[0] - p1[0])**2 + (p2[1] - p1[1])**2 )

# "Check if point C is between line endpoints A and B"
def PointBetwPoints(A, B, C):
    dist_line_endp = DistBetwPoints(A,B)
    if DistBetwPoints(A,C)>dist_line_endp:       return 1
    elif DistBetwPoints(B,C)>dist_line_endp:     return 1
    else:                                        return 0

Answer 10

这是我制作的一个 JavaScript 函数。您将三个点传递给它（三个具有 x 和 y 属性的对象）。第 1 点和第 2 点定义您的线，第 3 点是您要测试的点。

您将收到一个带有一些有用信息的对象：

• on_projected_line- 如果pt3位于线上的任何位置，包括点外。
• on_line- 如果pt3在线上和之间或上pt1和上pt2。
• x_between- 如果pt3在 x 边界之间或之上。
• y_between- 如果pt3在 y 边界之间或之上。
• between- 如果x_between和y_between都是真的。

/**
 * @description Check if pt3 is on line defined by pt1 and pt2.
 * @param {Object} pt1 The first point defining the line.
 * @param {float} pt1.x
 * @param {float} pt1.y
 * @param {Object} pt2 The second point defining the line.
 * @param {float} pt2.x
 * @param {float} pt2.y
 * @param {Object} pt3 The point to test.
 * @param {float} pt3.x
 * @param {float} pt3.y
 */
function pointOnLine(pt1, pt2, pt3) {
    const result = {
        on_projected_line: true,
        on_line: false,
        between_both: false,
        between_x: false,
        between_y: false,
    };

    // Determine if on line interior or exterior
    const x = (pt3.x - pt1.x) / (pt2.x - pt1.x);
    const y = (pt3.y - pt1.y) / (pt2.y - pt1.y);

    // Check if on line equation
    result.on_projected_line = x === y;

    // Check within x bounds
    if (
        (pt1.x <= pt3.x && pt3.x <= pt2.x) ||
        (pt2.x <= pt3.x && pt3.x <= pt1.x)
    ) {
        result.between_x = true;
    }

    // Check within y bounds
    if (
        (pt1.y <= pt3.y && pt3.y <= pt2.y) ||
        (pt2.y <= pt3.y && pt3.y <= pt1.y)
    ) {
        result.between_y = true;
    }

    result.between_both = result.between_x && result.between_y;
    result.on_line = result.on_projected_line && result.between_both;
    return result;
}

console.log("pointOnLine({x: 0, y: 0}, {x: 1, y: 1}, {x: 2, y: 2})")
console.log(pointOnLine({x: 0, y: 0}, {x: 1, y: 1}, {x: 2, y: 2}))

console.log("pointOnLine({x: 0, y: 0}, {x: 1, y: 1}, {x: 0.5, y: 0.5})")
console.log(pointOnLine({x: 0, y: 0}, {x: 1, y: 1}, {x: 0.5, y: 0.5}))