高效的数学算法来计算交点 [英] 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.
一对重present它们之间的连线的终点点。鉴于两对点，做画线相交，如果是这样，在什么时候？
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?
因此，例如调用线（AX，AY） - （BX，BY）和（CX，CY） - （DX，DY）
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.
编辑：有一点我应该更清楚，该算法必须返回false，如果交点超出线段的长度。 I.E.这是不是一种相贯线： lines.gif
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. I.E. this isn't an intersecition: lines.gif
推荐答案
大多数问题的答案已经在这里似乎遵循的总体思路是：
Most of the answers already here seem to follow the general idea that:
- 找到两条直线传球给定的点的交集。
- 确定的交点属于这两个线段。
但是，当路口不经常发生，更好的方法可能是扭转这些步骤：
But when intersection does not occur often, a better way probably is to reverse these steps:
- EX preSS中的 Y = AX + B 的（行通过A，B）和 Y = CX + D 的（行传递的形式直线C，D）
- 在看C和D是在同一侧的 Y = AX + B 的
- 在看，如果A和B是在同一侧的 Y = CX + D 的
- 如果答案以上都否，然后出现是的交集。否则就没有交集。
- 找到的交集，如果存在的话。
- express the straight lines in the form of y = ax + b (line passing A,B) and y = cx + d (line passing C,D)
- see if C and D are on the same side of y = ax+b
- see if A and B are on the same side of y = cx+d
- if the answer to the above are both no, then there is an intersection. otherwise there is no intersection.
- find the intersection if there is one.
请注意：做第2步，只是检查（赛扬 - 一（CX） - b）和（240 - 一（DX） - 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）等线段，precomputing步骤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屋！
