有效的mathalgorithm来计算交叉点

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

一对点代表它们之间画出的一条线的终点。 给定两对点，划线是否相交，如果是，在哪一点？

例如，将线（Ax，Ay） – （Bx，By）和（Cx，Cy） – （Dx，Dy）

任何人都可以想出解决scheme吗？ 任何语言的解决scheme都可以。

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

Answer 1

这里的大部分答案似乎都遵循这样的一般概念：

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

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

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

注意：要做第2步，只要检查（Cy – a（Cx） – b）和（Dy – a（Dx） – b）是否有相同的符号。 第3步是类似的。 步骤5只是两个方程的标准math。

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

Answer 2

如果你有机会，你应该真的检查碰撞检测圣经，“实时碰撞检测”，如果你打算做任何不平凡的事情。 我不是一个专业的游戏程序员，我理解并且可以将这些概念应用于一些小问题。

替代文字http://msinilo.pl/blog/img/RealTimeCollisionDetection_13330/cover_rtcd.png

亚马逊 – 实时碰撞检测

基本上，不pipe做什么，做一组线交叉testing都是昂贵的。 你所做的就是在复杂的多边形上使用边界框（轴alignment或定向）。 这将允许您快速地进行每个“对象”之间碰撞的最坏情况O（N ^ 2）检查。 然后，通过使用空间树（二进制分区或四叉树），只通过检查相互靠近的对象的交集，可以进一步加快速度。

这允许您修剪许多，许多碰撞testing。 最好的优化是不做的。 只有一旦你在边界框之间发生碰撞，你是否会花费昂贵的线交点来确定这些对象是否确实相交。 这样可以在保持合理的速度的同时缩放对象的数量。

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

进行交点计算之前，可以节省大量时间的简单优化是检查线的轴alignment边界框。
如果边界框完全不相交，那么你可以肯定没有交集。
当然这取决于你所拥有的数据。 如果你在每一次检查中都很有可能发现一个十字路口，那么你可能会发现自己在一张总是真实的支票上浪费时间。

Answer 5

 public struct PointD { pubic 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 6

那么，math和标量产品可以帮助那里。
– 假设你想要相交分段[AB]和[CD]
– 假设这些线的交点是M

M是在段[ÅB]内的当且仅当
vector（AB）。 向量（AM）> = 0
和
vector（AB）。 向量（MB）> = 0

那里的点“。” 表示一个标量产品：u。 v = ux * vx + uy * vy

所以，你的algorithm是：
– findM
– 当且仅当下面4个等式成立时，M在两个分段内
vector（AB）。 向量（AM）> = 0
vector（AB）。 向量（MB）> = 0
vector（CD）。 向量（CM）> = 0
vector（CD）。 vector（MD）> = 0

希望这可以帮助

Answer 7

下面是我在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 8

（我会留下这个评论，除非我还没有想出如何去做。）

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

设想每条线的最小封闭圆，然后testing圆的交点。 这允许预先计算（至less对于静态线和保持其长度的线）以及排除大量潜在交点的有效方式。

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; } } }