线与线段相交

Question

如何检测直线（从点 p 开始的 d 和 -d 方向）和线段（点 p1 和 p2 之间）是否在 2D 中相交？如果他们这样做，我怎样才能得到他们的交点。

有很多如何检测两条线段是否相交的示例，但这应该是更简单的情况。

我发现了这个，但我不明白什么是侧面操作员： http://www.loria.fr/~lazard//ARC-Visi3D/Pant-project/files/Line_Segment_Line.html

Answer 1

如果这是一个 2D 任务（直线和线段位于同一平面，并且它们由二维坐标指定），那就很简单。

构造一个垂直于 d（直线方向）的向量，称为 n。

计算点积 n.(p1-p) 和 n.(p2-p)。如果它们具有相同的符号，则没有交集。如果它们的符号相反，则存在交叉点。稍微思考一下，您就可以弄清楚如何用 p、p1-p 和 p2-p 来计算交点的位置。

Answer 2

您可以简单地检查两条线（您的线和线段线）是否相交并评估交点。

第 1 行：(x,y)(t) = p + t*d； 第 2 行：(x,y)(t) = p1 + k*(p2 - p1)

在交叉点： p + t*d = p1 + k*(p2 - p1) - 两个方程（每个 x 和每个 y）

从该方程中，您可以简单地找到 k 和 t 参数。如果 0 < k < 1 the intersection point is in (p1, p2)

如果您知道 k 或 t，您可以简单地计算 (x,y)(t) = p + t*d 的交点或 (x,y)(t) = p1 + k*(p2 - p1)

Answer 3

设

p(x,y)

和

a

其方向，直线方程为

D = a.x+b

哪里

b = y - a.x

令

p1(x1,y1)

和

p2(x2,y2)

为一个线段，对于

D' = a'.x+b'

中的任何

x

，方程为

[x1;x2]

其中

a' = (y2-y1)/(x2-x1)

和

b' = y2 - a'.x2 = y1 - a'.x1

如果

x

之间存在

[x1;x2]

，则

D = D'

存在交集 因此如果

X = (b'-b)/(a-a')

属于

[x1;x2]

然后

Y = a.X+b = a'.X+b

给你交点

P(X,Y)

例如：

让

p(255,255)

，

a = 1

=>

b = 0

让

p1(60,179)

和

p2(168,54)

=>

a' = -125/108

=>

b' = 24596/99

=>

X = (24596/99 - 0)/(1+125/108) = 115,1587983

=>

Y = (24596/99 - 0)/(1+125/108) = 115,1587983

X

介于 60 和 168 之间，因此在

P(X,Y)

处有一个交点

Answer 4

要检测交点，只需将 p1 和 p2 放入直线方程中即可。如果值的符号不同，则它们在线的两侧。

要找到交点，请使用您计算的先前值的权重计算 p1 和 p2 的加权平均值，并将其交换为 p1 和 p2（尽管是绝对值）。

example: p=(3,2) d=(7,6) p1=(9,10) p2=(12,8)
line equation is ax+by+c=0
for a and b you can put (6,-7) so 6x-7y+c=0
to find c, put p in the line equation 6*3-7*2+c=0 so c=-4
so the line equation is 6x-7y-4=0
p1: 6*9-7*10-4=-20
p2: 6*12-7*8-4=12

因此该线与该线段相交，因为符号不同。要找到交点，请通过交换计算值的绝对值来获取加权平均值：

pi=(p1*12+p2*20)/(12+20) = (10.875,8.75)

为了验证你的答案，请将 pi 代入直线方程：

6*10.875-7*8.75-4=0 ok!

这样就上线了。而且它肯定在线段上，因为它是p1和p2的线性组合。有关更多信息，请参阅线性代数书籍。

我尽可能简单地解释了。