math - 判断两条线是否相交

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

如果我在 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 上）。

因此，如果上述点积（与交点）为负，您可以检查线段是否相交。