线段相交问题

Question

如何检测在二维空间中，一条线段（由点p1和p2组成）与一条直线（由点p出发，方向为d或-d）是否相交？如果相交，如何得到它们的交点？

虽然有很多例子可以检测两条线段是否相交，但这应该是更简单的情况。

我找到了这个链接，但我不理解什么是边缘运算符： http://www.loria.fr/~lazard//ARC-Visi3D/Pant-project/files/Line_Segment_Line.html

- bittersoon

---

请在留言中写下您对行和段的表达，以便我们对答案进行对齐。谢谢！ - Dr. belisarius

Answer 1

如果这是一个二维任务（线段和线在同一平面上，由二维坐标指定），那么很容易。

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

计算点积n.(p1-p)和n.(p2-p)。如果它们具有相同的符号，则没有交点。如果它们具有相反的符号，则存在交点。经过一点思考，您可以想出如何用p、p1-p和p2-p来计算交点的位置。

- Eugene Smith

---

为什么需要构造一个垂直于d的向量？在后续的解释中似乎没有使用它... - static_rtti

我认为你在后续点积中所称的“d”实际上是法向方向。 - static_rtti

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或t，则可以从（x，y）（t）= p + t * d或 （x，y）（t）= p1 + k *（p2-p1）轻松计算交点。

- Andrew

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

如果在 [x1;x2] 范围内存在一个 x，使得 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)

- hoang

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)

为了验证你的答案，在线性方程中加入π。

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

所以它在直线上。而且它绝对是在线段上，因为它是p1和p2的线性组合。更多信息请参考线性代数书籍。

我尽量以简单的方式解释了。

- Mokhabadi