algorithm - 计算交叉点的高效数学算法

Question

对于我正在开发的游戏，我需要一种可以计算交叉点的算法。我已经解决了这个问题，但是我这样做的方式真的很讨厌，我希望这里有人可能有一个更优雅的解决方案。

一对点表示在它们之间绘制的线的端点。给定两对点，绘制的线是否相交，如果相交，在什么点？

因此，例如调用 (Ax, Ay)-(Bx, By) 和 (Cx, Cy)-(Dx, Dy) 行

谁能想到解决方案？任何语言的解决方案都可以。

编辑：我应该更清楚一点，如果交点超出线段的长度，算法必须返回 false。

Answer 1

已经在这里的大多数答案似乎都遵循以下一般思想：

1. 找到通过给定点的两条直线的交点。
2. 确定交点是否属于两条线段。

但是当不经常发生交叉时，更好的方法可能是反转这些步骤：

1. 以y = ax + b（通过 A、B 的线）和y = cx + d（通过 C、D的线）的形式表达直线
2. 查看 C 和 D 是否在y = ax+b的同一侧
3. 查看 A 和 B 是否在y = cx+d的同一侧
4. 如果上面的答案都是no，那么就有一个交集。否则没有交集。
5. 找到交叉点，如果有的话。

注意：要执行第 2 步，只需检查 (Cy - a(Cx) - b) 和 (Dy - a(Dx) - b) 是否具有相同的符号。步骤 3 类似。第 5 步只是两个方程的标准数学运算。

此外，如果您需要将每个线段与 (n-1) 个其他线段进行比较，则为所有线预先计算步骤 1 可以节省您的时间。

Answer 2

如果你有机会真的应该看看碰撞检测圣经，“实时碰撞检测”如果你打算做任何不平凡的事情。我不是专业的游戏程序员，我理解并可以轻松应用其中的概念。

亚马逊 - 实时碰撞检测

基本上，无论如何做一组线交叉测试都是昂贵的。您所做的是在复杂的多边形上使用边界框（轴对齐或定向）之类的东西。这将允许您快速对每个“对象”之间的碰撞进行最坏情况 O(N^2) 检查。然后，您可以通过仅检查彼此靠近的对象的交叉点来使用空间树（二进制分区或四叉树）进一步加快速度。

这使您可以修剪许多许多碰撞测试。最好的优化是什么都不做。只有在边界框之间发生碰撞时，您才会进行昂贵的线交叉以确定对象是否真的相交。这使您可以在保持合理速度的同时增加对象的数量。

Answer 3

float x12 = x1 - x2;
float x34 = x3 - x4;
float y12 = y1 - y2;
float y34 = y3 - y4;

float c = x12 * y34 - y12 * x34;

if (fabs(c) < 0.01)
{
  // No intersection
  return false;
}
else
{
  // Intersection
  float a = x1 * y2 - y1 * x2;
  float b = x3 * y4 - y3 * x4;

  float x = (a * x34 - b * x12) / c;
  float y = (a * y34 - b * y12) / c;

  return true;
}

公式取自：
线-线交点 - 维基百科

Answer 4

public struct PointD
{
    public double X { get; set; }
    public double Y { get; set; }
}

/// <summary>
/// Find the intersection point between two lines.
/// </summary>
/// <param name="IntersectPoint">The intersection point. A <see cref="Esteem.Geometry.PointD">PointD</see> structure.</param>
/// <param name="L1StartPoint">The starting point of first line. A PointD structure.</param>
/// <param name="L1EndPoint">The end point of first line. A PointD structure.</param>
/// <param name="L2StartPoint">The starting point of second line. A PointD structure.</param>
/// <param name="L2EndPoint">The end point of second line. A PointD structure.</param>
/// <param name="L1IntersectPos">The intersection position at first line.</param>
/// <param name="L2IntersectPos">The intersection position at second line.</param>
/// <returns>Returns a boolean. True if there is intersection, false otherwise.</returns>
/// <remarks>The formula is taken from comp.graphics.algorithms Frequently Asked Questions.</remarks>
public static bool LineIntersect(out PointD IntersectPoint, PointD L1StartPoint, PointD L1EndPoint, PointD L2StartPoint, PointD L2EndPoint, out double L1IntersectPos, out double L2IntersectPos) 
{
    IntersectPoint = new PointD();
    double ay_cy, ax_cx, px, py;
    double dx_cx = L2EndPoint.X - L2StartPoint.X,
        dy_cy = L2EndPoint.Y - L2StartPoint.Y,
        bx_ax = L1EndPoint.X - L1StartPoint.X,
        by_ay = L1EndPoint.Y - L1StartPoint.Y;

    double de = (bx_ax) * (dy_cy) - (by_ay) * (dx_cx);
    //double tor = 1.0E-10;     //tolerance


    L1IntersectPos = 0;      L2IntersectPos = 0;
    if (Math.Abs(de)<0.01)
        return false;
    //if (de > -tor && de < tor) return false; //line is in parallel

    ax_cx = L1StartPoint.X - L2StartPoint.X;
    ay_cy = L1StartPoint.Y - L2StartPoint.Y;
    double r = ((ay_cy) * (dx_cx) - (ax_cx) * (dy_cy)) / de;
    double s = ((ay_cy) * (bx_ax) - (ax_cx) * (by_ay)) / de;
    px = L1StartPoint.X + r * (bx_ax);
    py = L1StartPoint.Y + r * (by_ay);

    IntersectPoint.X = px;  //return the intersection point
    IntersectPoint.Y = py;  //return the intersection position
    L1IntersectPos = r;      L2IntersectPos = s;

    return true; //indicate there is intersection
}

要检查交点是否不超出线的原始长度，只需确保0<r<1和0<s<1

Answer 5

一个可以节省大量时间的简单优化是在进入交点计算之前检查线的轴对齐边界框。
如果边界框完全不相交，那么您可以确定没有交集。
当然，这取决于您拥有的数据。如果在您进行的每一次检查中都很有可能出现交叉点，那么您可能会发现自己在浪费时间进行始终正确的检查。

Answer 6

下面是我在MathWorld中描述的线交点。对于一般碰撞检测/交叉点，您可能需要查看分离轴定理。我发现这个关于 SAT 的教程非常有用。

    /// <summary>
    /// Returns the intersection point of the given lines. 
    /// Returns Empty if the lines do not intersect.
    /// Source: http://mathworld.wolfram.com/Line-LineIntersection.html
    /// </summary>
    public static PointF LineIntersection(PointF v1, PointF v2, PointF v3, PointF v4)
    {
        float tolerance = 0.000001f;

        float a = Det2(v1.X - v2.X, v1.Y - v2.Y, v3.X - v4.X, v3.Y - v4.Y);
        if (Math.Abs(a) < float.Epsilon) return PointF.Empty; // Lines are parallel

        float d1 = Det2(v1.X, v1.Y, v2.X, v2.Y);
        float d2 = Det2(v3.X, v3.Y, v4.X, v4.Y);
        float x = Det2(d1, v1.X - v2.X, d2, v3.X - v4.X) / a;
        float y = Det2(d1, v1.Y - v2.Y, d2, v3.Y - v4.Y) / a;

        if (x < Math.Min(v1.X, v2.X) - tolerance || x > Math.Max(v1.X, v2.X) + tolerance) return PointF.Empty;
        if (y < Math.Min(v1.Y, v2.Y) - tolerance || y > Math.Max(v1.Y, v2.Y) + tolerance) return PointF.Empty;
        if (x < Math.Min(v3.X, v4.X) - tolerance || x > Math.Max(v3.X, v4.X) + tolerance) return PointF.Empty;
        if (y < Math.Min(v3.Y, v4.Y) - tolerance || y > Math.Max(v3.Y, v4.Y) + tolerance) return PointF.Empty;

        return new PointF(x, y);
    }

    /// <summary>
    /// Returns the determinant of the 2x2 matrix defined as
    /// <list>
    /// <item>| x1 x2 |</item>
    /// <item>| y1 y2 |</item>
    /// </list>
    /// </summary>
    public static float Det2(float x1, float x2, float y1, float y2)
    {
        return (x1 * y2 - y1 * x2);
    }

Answer 7

（我会将此作为评论，除非我还没有弄清楚如何这样做。）

我想补充一点，作为边界框测试的替代/补充，您还可以测试线的中点之间的距离是否大于线的组合长度的一半。如果是这样，这些线不可能相交。

想象每条线的最小封闭圆，然后测试圆相交。这允许预计算（至少对于静态线和保留其长度的线）和排除许多潜在交叉点的有效方法。

Answer 8

好吧，数学和标量产品可以提供帮助。
- 假设您要使线段 [AB] 和 [CD]
相交 - 假设线的交点是 M

当且仅当
Vector(AB) 时，M 在段 [ÅB] 内。向量(AM) >= 0
和
向量(AB) 。向量(MB) >= 0

点“。”在哪里 表示标量积： u 。v = ux * vx + uy * vy

所以，你的算法是： - 当且仅当下面的 4 eq 为真 Vector(AB)时
，找到 M
- M 在两个段内。
向量(AM) >= 0
向量(AB) 。向量(MB) >= 0
向量(CD) 。向量(CM) >= 0
向量(CD)。向量(MD) >= 0

希望这可以帮助

Answer 9

private function Loop(e:Event):void
{
    var x12:Number = Ball1.x - Ball2.x;
    var x34:Number = Ball3.x - Ball4.x;
    var y12:Number = Ball1.y - Ball2.y;
    var y34:Number = Ball3.y - Ball4.y;

    // Det
    var c:Number = x12 * y34 - y12 * x34;

    if (Math.abs(c) < 0.01)
    {
        Circle.visible = false;
    }
    else
    {
        var a:Number = Ball1.x * Ball2.y - Ball1.y * Ball2.x;
        var b:Number = Ball3.x * Ball4.y - Ball3.y * Ball4.x;
        var px:Number = (a * x34 - b * x12) / c;
        var py:Number = (a * y34 - b * y12) / c;

        var Btwn12x:Boolean = (px >= Math.min(Ball1.x, Ball2.x)) && (px <= Math.max(Ball1.x, Ball2.x));
        var Btwn12y:Boolean = (py >= Math.min(Ball1.y, Ball2.y)) && (py <= Math.max(Ball1.y, Ball2.y));
        var Btwn34x:Boolean = (px >= Math.min(Ball3.x, Ball4.x)) && (px <= Math.max(Ball3.x, Ball4.x));
        var Btwn34y:Boolean = (py >= Math.min(Ball3.y, Ball4.y)) && (py <= Math.max(Ball3.y, Ball4.y));

        var Btwn12:Boolean = Btwn12x && Btwn12y;
        var Btwn34:Boolean = Btwn34x && Btwn34y;

        if(Btwn12 && Btwn34)
        {
            Circle.visible = true;
            Circle.x = px;
            Circle.y = py;
        }
        else
        {
            Circle.visible = false;
        }
    }
}