计算线段之间的交点

问题描述 投票：0回答：4

我需要帮助来了解如何计算交叉点。我已经阅读了这里的几个问题，并查看了其他网站上的几个示例，但我仍然很困惑并且不明白，而且我不喜欢在不了解事情如何工作的情况下复制和粘贴代码。

到目前为止我知道我要比较每个线段的点，如 Ax、Ay、Bx、By、Cx、Cy、Dx、Dy。有人可以帮我解释一下我要计算什么吗？如果有交集，计算结果会是什么？

这是我看到的示例代码之一。我不需要交点，只是想知道线条是否相交。

public static Point lineIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
    if (denom == 0.0) { // Lines are parallel.
        return null;
    }
    double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3))/denom;
    double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3))/denom;
    if (ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) {
        // Get the intersection point.
        return new Point((int) (x1 + ua*(x2 - x1)), (int) (y1 + ua*(y2 - y1)));
    }

    return null;
}

我是否还需要计算一些中值，如下面的代码示例所示？

For lines through points (x0,y0) and (x1,y1), let xm = (x0+x1)/2, ym = (y0+y1)/2 (median of line segment). 
Then a = (y1-y0) and b = (x0-x1). 
If you evaluate c = a(x-xm)+b(y-ym), c=0 for (x,y) on the line, and the sign(c) tells you which side a point is on
java android math intersection
4个回答
32
投票

您展示的第一段代码基于向量叉积，这已在此处进行了解释如何检测两条线段相交？非常详细。

IMO，一种更简单的理解方法是通过求解方程组。首先大致观察线条，然后从中切出片段。下面我对给定的段 

((x1, x2), (y1, y2))
和 
((x3, x4), (y3, y4))
使用符号。

  1. 检查是否有任何线条是垂直的（

    x1 == x2
    或 
    x3 == x4
    ）。

    a.如果两者都是垂直且

    x1 != x3
    ，则没有相交。

    b.如果两者都是垂直且

    x1 == x3
    ，请检查
    (y1, y2)
    和
    (y3, y4)
    是否重叠。

    c.如果只有一条是垂直的（例如第一条），则建立第二条线的方程（如下所述），找到两条线相交的点（通过将 

    x1
    代入第二条线的方程）并检查是否该点位于两个线段内（类似于步骤 5）。

    d。如果没有，请继续。

  2. 使用点坐标以 

    y = a*x + b
    的形式构建线方程（如此处）。

    a1 = (y2-y1)/(x2-x1)
b1 = y1 - a1*x1 
a2 = (y4-y3)/(x4-x3)
b2 = y3 - a2*x3

  3. 检查线条是否平行（相同的斜率

    a
    ）。如果是，检查它们是否具有相同的截距
    b
    。如果是，检查一维线段 
    (x1, x2)
    和 
    (x3, x4)
    是否重叠。如果是，那么您的细分确实重叠。线平行的情况可能是不明确的。如果它们重叠，您可以将其视为交点（如果它们的末端接触，甚至可以是一个点），也可以不将其视为交点。注意：如果您正在使用浮动，则会有点棘手，我认为您会想忽略这一点。如果您只有整数，检查 
    a1 = a2
    是否等于：

    if((y2-y1)*(x4-x3) == (x2-x1)*(y4-y3))

  4. 如果线不平行。交点相当于代表两条线的方程组的解。实际上，

    y = a1*x + b1
    和 
    y = a2*x + b2
    相交基本上意味着这两个方程都成立。通过使两个右侧相等来求解该方程组，它将给出交点。事实上，你只需要 
    x
    交点坐标（画出来你就会明白为什么）：

    x0 = -(b1-b2)/(a1-a2)

  5. 最后一步是检查交点

    x0
    是否位于两个线段内。即，
    min(x1, x2) < x0 < max(x1, x2)
    和
    min(x3, x4) < x0 < max(x3, x4)
    。如果是，那么你们的线确实相交！

5
投票

我真的很喜欢@sashkello的答案，并发现它比向量实现更直观、更容易解释。特别是在将此类代码添加到代码库时。

我要警告一下，您可以使用 Java 的 Line2D 辅助方法。

Line2D.linesIntersect(double x1, double y1,
                      double x2, double y2,
                      double x3, double y3,
                      double x4, double y4)

唯一的缺点是它要求您考虑线段相交，即使它们只是接触（在两个端点和线本身）。

例如，下面的线被视为相交，因为它们共享点 (1,1)。

L1 = [(0,0),(1,1)]
L2 = [(1,1),(2,3)]

如果这是一个问题，您可以添加 4 个检查来查看分数是否相等。

如果您担心某个点落在直线内的某个点上，那么这需要更多的工作，您最好自己实现它，这样您就可以在算法本身中进行检查。

如果这些边缘情况都不会影响您，那么 

Line2D.linesIntersect
适合您。 :)

1
投票
public void fixData()
{
    slope = (p2.getY() - p1.getY()) / (p2.getX() - p1.getX());
    yInt = p1.getY() - slope * p1.getX();
    xInt = (-yInt) / slope;
}
0
投票

我在这篇文章回答了问题，但我想将我自己的答案复制粘贴到此处以供将来的访问者使用。

我想让接受的答案变得非常简单。请注意，这是 C#，因此语法与 Java 类似，应该很容易理解。

// Setup formulas:

double A(double y2, double y1) => y1-y2;
double B(double x1,double x2) => x2-x1;
double C(double x1, double y1, double x2, double y2) => x1 * y2 - x2 * y1;

// Gives the Ax+By+C=0 form of the line
(double A, double B, double C) LineEquation(double x1, double y1, double x2, double y2) => 
(A(y2, y1), B(x1, x2), C(x1, y1, x2, y2));

//The Mobius version of a Cartesian point, called a "homogeneous point"
(double X, double Y, double Z) HomogeneousPointOfIntersection(double A1, double B1, double C1, double A2, double B2, double C2) =>
(B1 * C2 - B2 * C1, A2 * C1 - A1 * C2, A1 * B2 - A2 * B1);

注意公式 

HomogeneousPointOfIntersection
返回一个三元组，称为 
(X,Y,Z)
。要获得实际的笛卡尔 (X,Y) 点，您必须对 X,Y,Z 分量进行最终除法。

但是！如果 Z 分量为零，则意味着线是平行的，您不应该进行最终除法，因为这将是 NaN 错误。所以如果 Z 为零，你想早点返回/逃离。

这是最终的示例代码。

// Test that two sloping lines intersect


(double x, double y) p1 = (4, 2);
(double x, double y) p2 = (7, 5);

var line1 = LineEquation(p1.x,p1.y,p2.x,p2.y);

(double x, double y) p3 = (7, 2);
(double x, double y) p4 = (5, 7);

var line2 = LineEquation(p3.x, p3.y, p4.x, p4.y);

// h_p stands for homogeneous point
var h_p = HomogeneousPointOfIntersection(line1.A, line1.B, line1.C,line2.A,line2.B,line2.C);

if(h_p.Z == 0) return; // Return early as the below will be NaN.In this test example, this will be bypassed as we can get a successful final result.

var actualpointX = h_p.X / h_p.Z; // yields the Cartesian X value
var actualpointY = h_p.Y / h_p.Z; // yields the Cartesian Y value

因此，这段代码将处理所有具有平行线单边条件的条件。请随意测试垂直线和水平线，您会发现这些条件仍然会返回点交点。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.