我正在开发一个游戏，需要一个可以计算交点的算法。我已经解决了这个问题，但是我的方法非常恶劣，希望这里有人能提供更优雅的解决方案。
一对点表示它们之间画的线段的端点。给定两对点，绘制的线段是否相交，如果相交，在哪个点上？
例如，称线段为 (A.x, A.y)-(B.x, B.y) 和 (C.x, C.y)-(D.x, D.y)
有人能想到一个解决方案吗？任何语言的解决方案都可以。
编辑： 我应该更清楚地指出的一点是，如果交点超出线段长度，则算法必须返回 false。
高效的数学算法用于计算交点
44
- Mitch
1
另请参见https://dev59.com/pHRB5IYBdhLWcg3wpYmo和http://stackoverflow.com/questions/29854085/line-segments-intersectionintersection-point。 - Shital Shah
9个回答
69
大多数现有的答案都遵循以下一般想法:
此外，如果您需要将每个线段与（n-1）其他线段进行比较，则对所有线路预先计算第1步可以节省时间。
- 找到通过给定点的两条直线的交点。
- 确定交点是否属于两个线段。
- 将直线表示为y = ax + b（穿过A，B的线）和y = cx + d（穿过C，D的线）的形式。
- 查看C和D是否在y = ax+b的同侧。
- 查看A和B是否在y = cx+d的同侧。
- 如果上述两个答案都是否定的，则存在一个交点。否则，不存在交点。
- 如果存在交点，则找到交点。
此外，如果您需要将每个线段与（n-1）其他线段进行比较，则对所有线路预先计算第1步可以节省时间。
- PolyThinker
8
3不错！今天我的投票用完了，你竟然说服我去取消其中一个投票来支持这个。 - Jason S
22一个评论：不要使用y = mx + b的形式。它对于竖直线失效，而且存在数值稳定性问题。相反，使用a(x-xm)+b(y-ym)=c。 （续） - Jason S
7对于穿过点(x0,y0)和(x1,y1)的直线，令xm=(x0+x1)/2，ym=(y0+y1)/2（线段的中位数）。然后，a=(y1-y0)，b=(x0-x1)。如果评估c=a(x-xm)+b(y-ym)，则对于直线上的点(x,y)，c=0，而符号(c)告诉你一个点在哪一侧。 - Jason S
4好的，请将您需要翻译的内容发送给我。 - Jason S
9你的投票会用完？你在这个网站上花了多少时间？ - aaronsnoswell
显示剩余3条评论
19
如果你有机会的话，真的应该检查一下《碰撞检测圣经》——“实时碰撞检测”，如果你计划进行任何非平凡的事情。无论如何，进行一组线交点测试都是很昂贵的。你所做的是在复杂的多边形上使用诸如轴对齐或定向包围盒之类的东西。这将使您能够快速地进行每个“对象”之间的最坏情况O（N ^ 2）碰撞检查。然后，您可以通过只检查彼此靠近的对象的交点来进一步加快速度，例如使用空间树（二元划分或四叉树）。
这样可以剪枝许多碰撞测试。最好的优化是根本不做某件事。只有当包围盒之间发生碰撞时，才进行昂贵的线交点检查，以确定对象是否真正相交。这使您能够将对象数量扩展到一个可接受的范围内，同时保持速度合理。
- Simucal
15
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;
}
这些公式来自于：
线线相交 - 维基百科
- TomWij
5
3根据文章，“可以在线段的长度之外产生一个交点。” 这是我的问题。 解决方法可能是检查交点是否在线段的边界框内。 - Mitch
1在“return true;”的位置，您可以检查x是否在x1和x2之间，x3和x4之间，以及y是否在y1和y2之间，y3和y4之间。 - Tamara Wijsman
如果(x2-x1)的数量级比(x2+x1)小得多，或者x3、x4和y1、y2以及y3、y4存在类似的问题（在else子句中进行的数学运算），则会出现数字问题。 - Jason S
@TomWijsman，为了简化问题，只需要在x1-x2和x3-x4之间进行测试而不需要测试y。但是，由于可能存在垂直或水平的线条，最好同时测试两者。因此：(min(x1,x2) < x && x < max(x1,x2) && min(x3,x4) < x && x < max(x3,x4)) || (min(y1,y2) < y && y < max(y1,y2) && min(y3,y4) < y && y < max(y3,y4))。或者使用<=，但由于所有浮点数的存在，两者之间的差异可能是可以忽略不计的。 - Eyal
@TamaraWijsman 我只想用它来获取交点，因为我已经确定了它们相交的线。我想确认 (x1,y1) 和 (x2,y2) 是第一条线上的点，(x3,y3) 和 (x4,y4) 是第二条线上的点，而 (x,y) 是交点。 - IronThrone
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
- Ngu Soon Hui
4
一个简单的优化方法可以节省很多时间，就是在进行交点计算之前检查线条的轴对齐边界框。
如果边界框完全不相交，则可以确定没有交点。
当然，这取决于你拥有的数据。如果每次检查都很可能出现交点，那么你可能会浪费时间在一个总是正确的检查上。
- Shy
2
不，交叉点并不常见。这是一个非常好的想法，谢谢你。 - Mitch
2啊，边界框。每当我听到这些词时，我会想象计算机化的框在田野中跳跃，像春天里快乐的小羊一样。谢谢 :-) - endian
3
以下是我根据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);
}
- Ozgur Ozcitak
2
(如果我还没有想出如何这样做，我会将此作为评论留下。)
我想补充一下，作为边界框测试的替代/补充，您还可以测试线段中点之间的距离是否大于线段长度的一半。如果是，则这些线段不可能相交。
想象一下每条线段的最小包围圆，然后测试圆形相交。这允许进行预计算（至少对于静态线段和保持其长度的线段），并且是排除许多潜在相交的有效方法。
- Jo Are By
2
2您需要至少拥有50个声望才能对其他人的问题或回答进行评论。您会达到那个水平的 :) - Ivan Ferić
距离计算通常比边界框计算更昂贵，因为它们涉及平方根。 - David Rector
1
好的，数学和标量积可以帮助到这里。
- 假设你想要相交线段[AB]和[CD]
- 假设线段的交点是M
当且仅当以下条件满足时，M在线段[ÅB]内：
Vector(AB) . Vector(AM) >= 0
并且
Vector(AB) . Vector(MB) >= 0
其中"."表示标量积：u . v = ux * vx + uy * vy
所以，你的算法是:
- 找到M
- 当且仅当下面4个方程式为真时，M同时在两个线段之内
Vector(AB) . Vector(AM) >= 0
Vector(AB) . Vector(MB) >= 0
Vector(CD) . Vector(CM) >= 0
Vector(CD) . Vector(MD) >= 0
希望这能有所帮助。
- Pascal T.
0
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;
}
}
}
- Galindo
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接