math - 判断两条线是否相交

Question

我在stackoverflow上看到很多帖子都在讨论这个话题。我从stackoverflow上拿了一个解决方案，但我找不到帖子。意思是:如果两条线相交，则叉积会在左侧和右侧产生两个不同的结果。一正一负。否则两者具有相同的符号。到目前为止没问题。使用的公式是，其中 AB 是一行，CD 是另一行。

dotproductleft = (B.x-A.x)(C.y-B.y)-(B.y-A.y)(C.x-B.x)

dotproductright = (B.x-A.x)(D.y-B.y)-(B.y-A.y)(D.x-B.x)

如果我针对以下给定的 GPS 坐标进行计算，我会得到一个交叉点，如果没有交叉点是可能的。

A: 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

如果我在 Google Maps Engine 上绘制它，我可以看到这些线之间绝对没有交点。

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 上)。

因此，如果上述点积(与交点)为负，则可以检查线段是否相交。