我如何确定两条直线是否相交,如果相交,在x,y点处?


当前回答

我从《多视图几何》这本书里读到了这些算法

以下文本使用

'作为转置符号

*作为点积

当用作算子时,X作为叉乘

1. 线的定义

点x_vec = (x, y)'在直线ax + by + c = 0上

标记L = (a, b, c)',点为(x, y, 1)'为齐次坐标

直线方程可以写成

(x, y, 1)(a, b, c)' = 0或x' * L = 0

2. 直线交点

我们有两条直线L1=(a1, b1, c1)', L2=(a2, b2, c2)'

假设x是一个点,一个向量,x = L1 x L2 (L1叉乘L2)。

注意,x始终是一个二维点,如果你对(L1xL2)是一个三元素向量,x是一个二维坐标感到困惑,请阅读齐次坐标。

根据三重积,我们知道

L1 * (L1 x L2) = 0, L2 * (L1 x L2) = 0,因为L1,L2共平面

我们用向量x代替L1*x,那么L1*x=0, L2*x=0,这意味着x在L1和L2上,x是交点。

注意,这里x是齐次坐标,如果x的最后一个元素是零,这意味着L1和L2是平行的。

其他回答

我从《多视图几何》这本书里读到了这些算法

以下文本使用

'作为转置符号

*作为点积

当用作算子时,X作为叉乘

1. 线的定义

点x_vec = (x, y)'在直线ax + by + c = 0上

标记L = (a, b, c)',点为(x, y, 1)'为齐次坐标

直线方程可以写成

(x, y, 1)(a, b, c)' = 0或x' * L = 0

2. 直线交点

我们有两条直线L1=(a1, b1, c1)', L2=(a2, b2, c2)'

假设x是一个点,一个向量,x = L1 x L2 (L1叉乘L2)。

注意,x始终是一个二维点,如果你对(L1xL2)是一个三元素向量,x是一个二维坐标感到困惑,请阅读齐次坐标。

根据三重积,我们知道

L1 * (L1 x L2) = 0, L2 * (L1 x L2) = 0,因为L1,L2共平面

我们用向量x代替L1*x,那么L1*x=0, L2*x=0,这意味着x在L1和L2上,x是交点。

注意,这里x是齐次坐标,如果x的最后一个元素是零,这意味着L1和L2是平行的。

许多答案把所有的计算都打包成一个函数。如果您需要计算直线斜率、y轴截距或x轴截距,以便在代码的其他地方使用,那么这些计算将是冗余的。我分离出了各自的函数,使用了明显的变量名,并注释了我的代码以使其更易于理解。我需要知道直线是否无限超出它们的端点,所以在JavaScript中:

http://jsfiddle.net/skibulk/evmqq00u/

var point_a = {x:0, y:10},
    point_b = {x:12, y:12},
    point_c = {x:10, y:0},
    point_d = {x:0, y:0},
    slope_ab = slope(point_a, point_b),
    slope_bc = slope(point_b, point_c),
    slope_cd = slope(point_c, point_d),
    slope_da = slope(point_d, point_a),
    yint_ab = y_intercept(point_a, slope_ab),
    yint_bc = y_intercept(point_b, slope_bc),
    yint_cd = y_intercept(point_c, slope_cd),
    yint_da = y_intercept(point_d, slope_da),
    xint_ab = x_intercept(point_a, slope_ab, yint_ab),
    xint_bc = x_intercept(point_b, slope_bc, yint_bc),
    xint_cd = x_intercept(point_c, slope_cd, yint_cd),
    xint_da = x_intercept(point_d, slope_da, yint_da),
    point_aa = intersect(slope_da, yint_da, xint_da, slope_ab, yint_ab, xint_ab),
    point_bb = intersect(slope_ab, yint_ab, xint_ab, slope_bc, yint_bc, xint_bc),
    point_cc = intersect(slope_bc, yint_bc, xint_bc, slope_cd, yint_cd, xint_cd),
    point_dd = intersect(slope_cd, yint_cd, xint_cd, slope_da, yint_da, xint_da);

console.log(point_a, point_b, point_c, point_d);
console.log(slope_ab, slope_bc, slope_cd, slope_da);
console.log(yint_ab, yint_bc, yint_cd, yint_da);
console.log(xint_ab, xint_bc, xint_cd, xint_da);
console.log(point_aa, point_bb, point_cc, point_dd);

function slope(point_a, point_b) {
  var i = (point_b.y - point_a.y) / (point_b.x - point_a.x);
  if (i === -Infinity) return Infinity;
  if (i === -0) return 0;
  return i;
}

function y_intercept(point, slope) {
    // Horizontal Line
    if (slope == 0) return point.y;
  // Vertical Line
    if (slope == Infinity)
  {
    // THE Y-Axis
    if (point.x == 0) return Infinity;
    // No Intercept
    return null;
  }
  // Angled Line
  return point.y - (slope * point.x);
}

function x_intercept(point, slope, yint) {
    // Vertical Line
    if (slope == Infinity) return point.x;
  // Horizontal Line
    if (slope == 0)
  {
    // THE X-Axis
    if (point.y == 0) return Infinity;
    // No Intercept
    return null;
  }
  // Angled Line
  return -yint / slope;
}

// Intersection of two infinite lines
function intersect(slope_a, yint_a, xint_a, slope_b, yint_b, xint_b) {
  if (slope_a == slope_b)
  {
    // Equal Lines
    if (yint_a == yint_b && xint_a == xint_b) return Infinity;
    // Parallel Lines
    return null;
  }
  // First Line Vertical
    if (slope_a == Infinity)
  {
    return {
        x: xint_a,
      y: (slope_b * xint_a) + yint_b
    };
  }
  // Second Line Vertical
    if (slope_b == Infinity)
  {
    return {
        x: xint_b,
      y: (slope_a * xint_b) + yint_a
    };
  }
  // Not Equal, Not Parallel, Not Vertical
  var i = (yint_b - yint_a) / (slope_a - slope_b);
  return {
    x: i,
    y: (slope_a * i) + yint_a
  };
}

以下是对加文回答的改进。马普的解决方案也类似,但都没有推迟分割。

这实际上也是Gareth Rees的答案的一个实际应用,因为向量积在2D中的等价是补点积,这段代码用了其中的三个。切换到3D并使用叉积,在最后插入s和t,结果是3D中直线之间的两个最近点。 不管怎样,2D解:

int get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, 
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
    float s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t;
    s10_x = p1_x - p0_x;
    s10_y = p1_y - p0_y;
    s32_x = p3_x - p2_x;
    s32_y = p3_y - p2_y;

    denom = s10_x * s32_y - s32_x * s10_y;
    if (denom == 0)
        return 0; // Collinear
    bool denomPositive = denom > 0;

    s02_x = p0_x - p2_x;
    s02_y = p0_y - p2_y;
    s_numer = s10_x * s02_y - s10_y * s02_x;
    if ((s_numer < 0) == denomPositive)
        return 0; // No collision

    t_numer = s32_x * s02_y - s32_y * s02_x;
    if ((t_numer < 0) == denomPositive)
        return 0; // No collision

    if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive))
        return 0; // No collision
    // Collision detected
    t = t_numer / denom;
    if (i_x != NULL)
        *i_x = p0_x + (t * s10_x);
    if (i_y != NULL)
        *i_y = p0_y + (t * s10_y);

    return 1;
}

基本上,它将除法延迟到最后一刻,并将大多数测试移动到某些计算完成之前,从而增加了早期退出。最后,它还避免了直线平行时的除零情况。

您可能还想考虑使用ε检验,而不是与零比较。非常接近平行的线会产生稍微偏离的结果。这不是一个bug,这是浮点数学的一个限制。

下面是一个基本的c#线段实现,并有相应的交点检测代码。它需要一个名为Vector2f的2D向量/点结构,不过你可以用任何其他具有X/Y属性的类型替换它。如果更适合你的需要,你也可以用double替换float。

这段代码用于我的. net物理库Boing。

public struct LineSegment2f
{
    public Vector2f From { get; }
    public Vector2f To { get; }

    public LineSegment2f(Vector2f @from, Vector2f to)
    {
        From = @from;
        To = to;
    }

    public Vector2f Delta => new Vector2f(To.X - From.X, To.Y - From.Y);

    /// <summary>
    /// Attempt to intersect two line segments.
    /// </summary>
    /// <remarks>
    /// Even if the line segments do not intersect, <paramref name="t"/> and <paramref name="u"/> will be set.
    /// If the lines are parallel, <paramref name="t"/> and <paramref name="u"/> are set to <see cref="float.NaN"/>.
    /// </remarks>
    /// <param name="other">The line to attempt intersection of this line with.</param>
    /// <param name="intersectionPoint">The point of intersection if within the line segments, or empty..</param>
    /// <param name="t">The distance along this line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
    /// <param name="u">The distance along the other line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
    /// <returns><c>true</c> if the line segments intersect, otherwise <c>false</c>.</returns>
    public bool TryIntersect(LineSegment2f other, out Vector2f intersectionPoint, out float t, out float u)
    {
        var p = From;
        var q = other.From;
        var r = Delta;
        var s = other.Delta;

        // t = (q − p) × s / (r × s)
        // u = (q − p) × r / (r × s)

        var denom = Fake2DCross(r, s);

        if (denom == 0)
        {
            // lines are collinear or parallel
            t = float.NaN;
            u = float.NaN;
            intersectionPoint = default(Vector2f);
            return false;
        }

        var tNumer = Fake2DCross(q - p, s);
        var uNumer = Fake2DCross(q - p, r);

        t = tNumer / denom;
        u = uNumer / denom;

        if (t < 0 || t > 1 || u < 0 || u > 1)
        {
            // line segments do not intersect within their ranges
            intersectionPoint = default(Vector2f);
            return false;
        }

        intersectionPoint = p + r * t;
        return true;
    }

    private static float Fake2DCross(Vector2f a, Vector2f b)
    {
        return a.X * b.Y - a.Y * b.X;
    }
}

我试过其中一些答案,但它们对我不起作用(对不起伙计们);在网上搜索之后,我找到了这个。

对他的代码做了一点修改,我现在有了这个函数,它将返回交点,如果没有找到交点,它将返回- 1,1。

    Public Function intercetion(ByVal ax As Integer, ByVal ay As Integer, ByVal bx As Integer, ByVal by As Integer, ByVal cx As Integer, ByVal cy As Integer, ByVal dx As Integer, ByVal dy As Integer) As Point
    '//  Determines the intersection point of the line segment defined by points A and B
    '//  with the line segment defined by points C and D.
    '//
    '//  Returns YES if the intersection point was found, and stores that point in X,Y.
    '//  Returns NO if there is no determinable intersection point, in which case X,Y will
    '//  be unmodified.

    Dim distAB, theCos, theSin, newX, ABpos As Double

    '//  Fail if either line segment is zero-length.
    If ax = bx And ay = by Or cx = dx And cy = dy Then Return New Point(-1, -1)

    '//  Fail if the segments share an end-point.
    If ax = cx And ay = cy Or bx = cx And by = cy Or ax = dx And ay = dy Or bx = dx And by = dy Then Return New Point(-1, -1)

    '//  (1) Translate the system so that point A is on the origin.
    bx -= ax
    by -= ay
    cx -= ax
    cy -= ay
    dx -= ax
    dy -= ay

    '//  Discover the length of segment A-B.
    distAB = Math.Sqrt(bx * bx + by * by)

    '//  (2) Rotate the system so that point B is on the positive X axis.
    theCos = bx / distAB
    theSin = by / distAB
    newX = cx * theCos + cy * theSin
    cy = cy * theCos - cx * theSin
    cx = newX
    newX = dx * theCos + dy * theSin
    dy = dy * theCos - dx * theSin
    dx = newX

    '//  Fail if segment C-D doesn't cross line A-B.
    If cy < 0 And dy < 0 Or cy >= 0 And dy >= 0 Then Return New Point(-1, -1)

    '//  (3) Discover the position of the intersection point along line A-B.
    ABpos = dx + (cx - dx) * dy / (dy - cy)

    '//  Fail if segment C-D crosses line A-B outside of segment A-B.
    If ABpos < 0 Or ABpos > distAB Then Return New Point(-1, -1)

    '//  (4) Apply the discovered position to line A-B in the original coordinate system.
    '*X=Ax+ABpos*theCos
    '*Y=Ay+ABpos*theSin

    '//  Success.
    Return New Point(ax + ABpos * theCos, ay + ABpos * theSin)
End Function