检查两个线段是否发生碰撞(仅检查它们是否相交,而不是相交)

Question

我需要一个快速算法来检查两条非无限线是否正在交叉.必须快速,因为它会在手机上运行很多.

该算法只需要返回yes或no,它不必确切地找出线交叉的位置!

我看过这里:你如何检测两个线段相交的位置？ 但是这个线程是一个丛林,人们一直在说"这就是答案"但是其他两个人说这是错误的,因为这个和那个错误.

请帮我找到一个好的和有效的算法.

为了清楚起见:我需要一个你给出的函数
lineApointAx
lineApointAy
lineApointBx
lineApointBy
lineBpointAx
lineBpointAy
lineBpointBx
lineBpointBy
......并且返回true或false,具体取决于两条线是否交叉.

如果你回答(伪)代码,而不是公式,我将不胜感激.

Answer 1

一段的两端在另一段的不同侧上是必要和充分的,反之亦然.要确定一个点在哪一侧,只需采用交叉产品,看看它是正面的还是负面的:

(B _x - A _x)(P _y - B _y) - (B _y - A _y)(P _x - B _x)

编辑:
拼出来:假设您正在查看两个线段,[AB]和[CD].当且仅当((A和B是[CD]的不同侧)和(C和D在[AB]的不同侧))时,这些段相交.

要查看两个点P和Q是否位于线段[EF]的不同侧,请计算两个交叉积,一个用于P,一个用于Q:

(F _x - E _x)(P _y - F _y) - (F _y - E _y)(P _x - F _x)

(F _x - E _x)(Q _y - F _y) - (F _y - E _y)(Q _x - F _x)

如果结果具有相同的符号(正值或两者均为负值),则忘记它,点在同一侧,段不相交.如果一个是正面而另一个是负面的,则这些点位于相反的一侧.

Answer 2

如果你有两个给定的点是(X1,Y1)和(X2,Y2),想象两者都是无限的线,而不仅仅是段:

1. 确定两者的公式(参见:http://en.wikipedia.org/wiki/Linear_equation#Two-point_form)

2. 确定两条线的交点(参见:http://zonalandeducation.com/mmts/intersections/intersectionOfTwoLines1/intersectionOfTwoLines1.html)

3. 如果X1 <intersectionX <X2且Y1 <intersectionY <Y2,则是,则段相交.