确定两条线是否相交

Question

我在stackoverflow上看过很多帖子,正在讨论这个话题.我从stackoverflow中找到了一个解决方案,但我找不到帖子.这就是说:如果两条线相交,那么交叉产品会为左侧和右侧产生两种不同的结果.一个积极和一个消极.否则两者都有相同的标志.到目前为止还可以.使用的公式是,其中AB是一行而CD是另一行.

dotproductleft =(Bx-Ax)(Cy-By) - (By-Ay)(Cx-Bx)

dotproductright =(Bx-Ax)(Dy-By) - (By-Ay)(Dx-Bx)

如果我为以下给定的GPS坐标计算得到这个,我得到一个交叉点,在没有交叉点的情况下.

答:x:15.4433917 y:47.0697272

B:x:15.4433661 y:47.0697722

C:x:15.4434363 y:47.0696776

D:x:15.442966 y:47.0700098

如果我在谷歌地图引擎上绘制它,我可以看到这些线之间肯定没有交集.

dotproductleft的结果:-7.372399999828474E-10和dotproductright:1.1921940000328E-8

它非常适合其他例子,但在这里我看到它不能正常工作.但我无法发现公式中的任何错误.

Answer 1

的线,其包含任何线段(例如AB和CD)将始终相交(除非它们是平行的).

您想检查线段是否相交.通过找到交点并检查它是否位于两个线段上,这很容易做到.

因此,使用您的示例,两条线(线段AB和CD所在的线)在P =(15.4434,47.0697)处相交.现在,如果P位于AB上,则PA和PB的点积为负(因为PA和PB之间的角度为180°,cos(180°)= -1).

如果计算PA和PB的点积,您将得到一个正数(因此它不在 AB上).但是,PC和PD的点积给你一个负数(因此它位于CD上).

因此,如果上述点积(具有交点)为负,则可以检查线段是否相交.