确定两条线是否相交 [英] Determine if two lines intersect

问题描述

我在stackoverflow上看到了很多帖子，都在讨论这个话题.我从stackoverflow那里获得了一个解决方案，但是找不到发布信息.就是说:如果两条线相交，则叉积将为左侧和右侧产生两个不同的结果.一正一负.否则，两者具有相同的符号.到目前为止，还可以. 使用的公式是，其中AB是一行，而CD是另一行.

I've seen many postings here on stackoverflow, which are discussing this topic. I took a solution from stackoverflow, but I couldn't find the posting. It was to say: If two lines are intersecting, then the crossproduct produces for the left and the right side two different results. One positive and one negative. Otherwise both have the same sign. So far it is okay. The used formula is, where AB is one line and CD another.

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

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)

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

如果我针对以下给定的GPS坐标计算此值，则在无法进行相交的情况下会得到一个相交.

If I calculate this for the following given GPS coordinates I get an intersection, in a case where no intersection is possible.

A:x:15.4433917 y:47.0697272

A: x: 15.4433917 y: 47.0697272

B:x:15.4433661 y:47.0697722

B: x: 15.4433661 y: 47.0697722

C:x:15.4434363 y:47.0696776

C: x: 15.4434363 y: 47.0696776

D:x:15.442966 y:47.0700098

D: x: 15.442966 y: 47.0700098

如果我在Google Maps Engine上绘制它，我肯定会发现这些线之间绝对没有交点.

If I draw it on Google Maps Engine, I can see that there definitely no intersection between these lines.

dotproductleft:-7.372399999828474E-10和dotproductright:1.1921940000328E-8

The results for dotproductleft: -7.372399999828474E-10 and for dotproductright: 1.1921940000328E-8

它可以很好地用于其他示例，但是在这里我看到它无法正常工作.但是我无法在公式中发现任何错误.

It is working for other examples very well, but here I've seen that it is not working right. But I couldn't spot any error in the formula.

推荐答案

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

The lines which contain any line segment (e.g. AB and CD) will always intersect (unless they are parallel).

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

You want to check if the line segments intersect. This is easy to do by finding the point of intersection and checking if it lies on both line segments.

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

So, using your example, the two lines (on which line segments AB and CD lie on) intersect at P = (15.4434,47.0697). Now, if P lies on AB then the dot product of PA and PB is negative (since the angle between PA and PB is 180° and cos(180°)=-1).

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

If you compute the dot product of PA and PB, you will get a positive number (thus it does not lie on AB). However, the dot product of PC and PD gives you a negative number (thus it lies on CD).

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

Thus, you can check if the line segments intersect if the aforementioned dot products (with the point of intersection) are negative.

这篇关于确定两条线是否相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！