计算交点的高效数学算法 [英] Efficient maths algorithm to calculate intersections

问题描述

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

For a game I am developing I need an algorithm that can calculate intersections. I have solved the problem, but the way I have done it is really nasty and I am hoping someone here might have a more elegant solution.

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

A pair of points represent the end points of a line drawn between them. Given two pairs of points, do the drawn lines intersect, and if so, at what point?

例如调用 (A.x, A.y)-(B.x, B.y) 和 (C.x, C.y)-(D.x, D.y) 行

So for example call the lines (A.x, A.y)-(B.x, B.y) and (C.x, C.y)-(D.x, D.y)

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

Can anyone think of a solution? A solution in any language will do.

一个我应该更清楚的点，如果交点超出线段的长度，算法必须返回假.

A point I should have made clearer, the algorithm must return false if the point of intersection is beyond the lengths of the line segments.

推荐答案

这里的大部分答案似乎都遵循以下总体思路:

Most of the answers already here seem to follow the general idea that:

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

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

But when intersection does not occur often, a better way probably is to reverse these steps:

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. 找到交叉点(如果有).

1. express the straight lines in the form of y = ax + b (line passing A,B) and y = cx + d (line passing C,D)
2. see if C and D are on the same side of y = ax+b
3. see if A and B are on the same side of y = cx+d
4. if the answer to the above are both no, then there is an intersection. otherwise there is no intersection.
5. find the intersection if there is one.

注意:要进行第 2 步，只需检查 (C.y - a(C.x) - b) 和 (D.y - a(D.x) - b) 是否具有相同的符号.步骤 3 类似.第 5 步只是两个方程的标准数学运算.

Note: to do step 2, just check if (C.y - a(C.x) - b) and (D.y - a(D.x) - b) have the same sign. Step 3 is similar. Step 5 is just standard math from the two equations.

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

Furthermore, if you need to compare each line segment with (n-1) other line segments, precomputing step 1 for all lines saves you time.

这篇关于计算交点的高效数学算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！