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

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

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

所以例如调用线(Ax,Ay) - (Bx,By)和(Cx,Cy) - (Dx,Dy)

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

编辑:我应该更清楚的一点,如果交叉点超出线段的长度,算法必须返回false.

1> PolyThinker..：

---

这里已有的大多数答案似乎都遵循以下一般观点:

找到通过给定点的两条直线的交点.

确定交叉点是否属于两个线段.

但是当交叉不经常发生时,更好的方法可能是扭转这些步骤:

以y = ax + b(线路经过A,B)和y = cx + d(线路经过C,D)的形式表示直线

见如果C和d是在相同侧的Y = AX + B

见,如果A和B是在相同侧的Y = CX + d

如果回答上述均没有,则是一个交叉点.否则没有交集.

找到交叉点,如果有的话.

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

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

---

一条评论:不要使用y = mx + b表格.垂直线失败,也存在数值稳定性问题.而是使用(x-xm)+ b(y-ym)= c.(续)

---

你可以用完投票？你在这个网站上花了多少时间？

---

对于通过点(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),那么c = 0表示线上的(x,y),符号(c)告诉你一个点在哪一侧.

---

太好了!我今天没有投票了,你实际上说服我去除了我的其他选票以投票支持这一票.

---

(你也可以用x0,y0或x1,y1替换xm,ym)

2> mmcdole..：

---

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

亚马逊 - 实时碰撞检测

基本上,无论如何,进行一系列的线交叉测试都很昂贵.你所做的是在复杂的多边形上使用诸如边界框(轴对齐或方向)之类的东西.这将允许您快速执行最坏情况O(N ^ 2)检查每个"对象"之间的冲突.然后,您可以通过仅使用彼此靠近的对象的交叉点来使用空间树(二进制分区或四叉树)来进一步加快速度.

这允许您修剪许多碰撞测试.最好的优化根本就没有做任何事情.只有在边界框之间发生碰撞时,才会执行昂贵的线交叉以确定对象是否真正相交.这允许您在保持速度合理的同时向上扩展对象的数量.

3> Tamara Wijsm..：

---

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

公式取自:
线 - 线交叉 - 维基百科

---

从文章中,"可以产生超出线段长度的交叉点." 这是我的问题.解决方案可以是检查交叉点是否在线的边界框内.