高效的数学算法来计算交叉点

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. 如果回答上述均没有,则是一个交叉点.否则没有交集.
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

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