如何检查线段和从某一点开始沿着与水平线成角度的光线之间的相交？

Question

给定一条线段，即两个点(x1,y1)和(x2,y2)，一个点P(x,y)和一个角度theta。我们如何确定这条线段和从点P以水平角度theta发出的射线是否相交？如果它们相交，如何找到交点？

- Paagalpan

Answer 1

让我们标记点q = (x1, y1)和q + s = (x2, y2)。因此，s = (x2 - x1, y2 - y1)。然后问题看起来像这样： 设r = (cos θ, sin θ)。那么通过p的射线上的任意点都可以表示为p + t r（对于标量参数0 ≤ t），线段上的任意点都可以表示为q + u s（对于标量参数0 ≤ u ≤ 1）。

如果我们可以找到t和u使得p + t r = q + u s，则两条直线相交： 请参见此答案以查找此点（或确定是否不存在此点）。

然后，您的线段与射线相交如果0 ≤ t且0 ≤ u ≤ 1。

- Gareth Rees

Answer 2

这里是其他答案中给出的算法的C#代码：

    /// <summary>
    /// Returns the distance from the ray origin to the intersection point or null if there is no intersection.
    /// </summary>
    public double? GetRayToLineSegmentIntersection(Point rayOrigin, Vector rayDirection, Point point1, Point point2)
    {
        var v1 = rayOrigin - point1;
        var v2 = point2 - point1;
        var v3 = new Vector(-rayDirection.Y, rayDirection.X);


        var dot = v2 * v3;
        if (Math.Abs(dot) < 0.000001)
            return null;

        var t1 = Vector.CrossProduct(v2, v1) / dot;
        var t2 = (v1 * v3) / dot;

        if (t1 >= 0.0 && (t2 >= 0.0 && t2 <= 1.0))
            return t1;

        return null;
    }

- ezolotko

---

这只是射线与线段相交测试的一部分。您没有考虑射线和线段平行的可能性。在这种情况下，点积dot(v2, v3)将为0（或非常接近于0）。 - Thash

很遗憾，这还不够。在这种情况下，如果射线起点和线段端点共线，则它们可能相交（还要注意射线起点实际上可能在线段内部）。解决计算几何中的特殊情况是有趣的 :) - Thash

@SyaifulNizamYahya 双精度浮点数是沿着光线从原点到交点的距离。您可以通过以下方式获取交点：rayOrigin + rayDirection * distance，其中rayDirection已经被标准化（长度为1）。 - ezolotko

也许如果您将摘要更改为“返回射线起点和交点之间的距离”，会更好。 - Syaiful Nizam Yahya

@SyaifulNizamYahya，我澄清了摘要评论，谢谢。 - ezolotko

Answer 3

感谢Gareth提供的好答案。这里是Python实现的解决方案。请随意删除测试并复制粘贴实际函数。我遵循了出现在https://rootllama.wordpress.com/2014/06/20/ray-line-segment-intersection-test-in-2d/中的方法说明。

import numpy as np

def magnitude(vector):
   return np.sqrt(np.dot(np.array(vector),np.array(vector)))

def norm(vector):
   return np.array(vector)/magnitude(np.array(vector))

def lineRayIntersectionPoint(rayOrigin, rayDirection, point1, point2):
    """
    >>> # Line segment
    >>> z1 = (0,0)
    >>> z2 = (10, 10)
    >>>
    >>> # Test ray 1 -- intersecting ray
    >>> r = (0, 5)
    >>> d = norm((1,0))
    >>> len(lineRayIntersectionPoint(r,d,z1,z2)) == 1
    True
    >>> # Test ray 2 -- intersecting ray
    >>> r = (5, 0)
    >>> d = norm((0,1))
    >>> len(lineRayIntersectionPoint(r,d,z1,z2)) == 1
    True
    >>> # Test ray 3 -- intersecting perpendicular ray
    >>> r0 = (0,10)
    >>> r1 = (10,0)
    >>> d = norm(np.array(r1)-np.array(r0))
    >>> len(lineRayIntersectionPoint(r0,d,z1,z2)) == 1
    True
    >>> # Test ray 4 -- intersecting perpendicular ray
    >>> r0 = (0, 10)
    >>> r1 = (10, 0)
    >>> d = norm(np.array(r0)-np.array(r1))
    >>> len(lineRayIntersectionPoint(r1,d,z1,z2)) == 1
    True
    >>> # Test ray 5 -- non intersecting anti-parallel ray
    >>> r = (-2, 0)
    >>> d = norm(np.array(z1)-np.array(z2))
    >>> len(lineRayIntersectionPoint(r,d,z1,z2)) == 0
    True
    >>> # Test ray 6 --intersecting perpendicular ray
    >>> r = (-2, 0)
    >>> d = norm(np.array(z1)-np.array(z2))
    >>> len(lineRayIntersectionPoint(r,d,z1,z2)) == 0
    True
    """
    # Convert to numpy arrays
    rayOrigin = np.array(rayOrigin, dtype=np.float)
    rayDirection = np.array(norm(rayDirection), dtype=np.float)
    point1 = np.array(point1, dtype=np.float)
    point2 = np.array(point2, dtype=np.float)

    # Ray-Line Segment Intersection Test in 2D
    # http://bit.ly/1CoxdrG
    v1 = rayOrigin - point1
    v2 = point2 - point1
    v3 = np.array([-rayDirection[1], rayDirection[0]])
    t1 = np.cross(v2, v1) / np.dot(v2, v3)
    t2 = np.dot(v1, v3) / np.dot(v2, v3)
    if t1 >= 0.0 and t2 >= 0.0 and t2 <= 1.0:
        return [rayOrigin + t1 * rayDirection]
    return []

if __name__ == "__main__":
    import doctest
    doctest.testmod()

- Daniel Farrell

---

测试用例 6 不正确。它是测试用例 5 的重复。

- Magnuti

Answer 4

注意：此解决方案不需要创建向量类或定义向量乘除法，但实现起来较长。它还避免了除以零的错误。如果您只想要一段代码块并且不关心推导过程，请滚动到帖子底部。

假设我们有一个由x、y和theta定义的射线，以及由x1、y1、x2和y2定义的直线。

首先，让我们画出两条从射线起点指向线段端点的射线。伪代码如下：

theta1 = atan2(y1-y, x1-x);
theta2 = atan2(y2-y, x2-x);

接下来我们要检查这个射线是否在这两个新射线之间。它们都有相同的起点，所以我们只需要检查角度。

为了方便起见，让我们将所有角度偏移，使theta1在x轴上，然后将所有内容放回到-π到π的范围内。伪代码如下：

dtheta = theta2-theta1; //this is where theta2 ends up after shifting
ntheta = theta-theta1; //this is where the ray ends up after shifting
dtheta = atan2(sin(dtheta), cos(dtheta))
ntheta = atan2(sin(ntheta), cos(ntheta))

（注意：对角度的正弦和余弦进行atan2计算只是将角度范围重置为-pi到pi之间，而不改变角度。）

现在想象一条线从theta2的新位置（dtheta）画到theta1的新位置（0弧度）。这就是线段最终停留的位置。

当且仅当theta在theta1和theta2之间时，射线与线段相交，这与ntheta在dtheta和0弧度之间相同。以下是相应的伪代码：

sign(ntheta)==sign(dtheta)&&
abs(ntheta)<=abs(dtheta)

这将告诉您两条线是否相交。以下是一种伪代码块:

theta1=atan2(y1-y, x1-x);
theta2=atan2(y2-y, x2-x);
dtheta=theta2-theta1;
ntheta=theta-theta1;
dtheta=atan2(sin(dtheta), cos(dtheta))
ntheta=atan2(sin(ntheta), cos(ntheta))
return (sign(ntheta)==sign(dtheta)&&
abs(ntheta)<=abs(dtheta));

现在我们知道两个点相交了，我们需要找到相交点。我们将从一个完全干净的状态开始工作，因此我们可以忽略本部分之前的任何代码。要找到相交点，您可以使用以下方程组并解出xp和yp，其中lb和rb分别是线段和射线的y截距。

y1=(y2-y1)/(x2-x1)*x1+lb
yp=(y2-y1)/(x2-x1)*xp+lb
y=sin(theta)/cos(theta)*x+rb
yp=sin(theta)/cos(theta)*x+rb

这将得出xp和yp的以下公式：

xp=(y1-(y2-y1)/(x2-x1)*x1-y+sin(theta)/cos(theta)*x)/(sin(theta)/cos(theta)-(y2-y1)/(x2-x1));
yp=sin(theta)/cos(theta)*xp+y-sin(theta)/cos(theta)*x

使用lm=(y2-y1)/(x2-x1)和rm=sin(theta)/cos(theta)可以缩短计算时间。

xp=(y1-lm*x1-y+rm*x)/(rm-lm);
yp=rm*xp+y-rm*x;

您可以通过检查线或射线是否垂直来避免除以零错误，然后将每个x和y互换。以下是相应的伪代码：

if(x2-x1==0||cos(theta)==0){
    let rm=cos(theta)/sin(theta);
    let lm=(x2-x1)/(y2-y1);
    yp=(x1-lm*y1-x+rm*y)/(rm-lm);
    xp=rm*yp+x-rm*y;
}else{
    let rm=sin(theta)/cos(theta);
    let lm=(y2-y1)/(x2-x1);
    xp=(y1-lm*x1-y+rm*x)/(rm-lm);
    yp=rm*xp+y-rm*x;
}

TL;DR：

简而言之：

bool intersects(x1, y1, x2, y2, x, y, theta){
    theta1=atan2(y1-y, x1-x);
    theta2=atan2(y2-y, x2-x);
    dtheta=theta2-theta1;
    ntheta=theta-theta1;
    dtheta=atan2(sin(dtheta), cos(dtheta))
    ntheta=atan2(sin(ntheta), cos(ntheta))
    return (sign(ntheta)==sign(dtheta)&&abs(ntheta)<=abs(dtheta));
}
point intersection(x1, y1, x2, y2, x, y, theta){
    let xp, yp;
    if(x2-x1==0||cos(theta)==0){
        let rm=cos(theta)/sin(theta);
        let lm=(x2-x1)/(y2-y1);
        yp=(x1-lm*y1-x+rm*y)/(rm-lm);
        xp=rm*yp+x-rm*y;
    }else{
        let rm=sin(theta)/cos(theta);
        let lm=(y2-y1)/(x2-x1);
        xp=(y1-lm*x1-y+rm*x)/(rm-lm);
        yp=rm*xp+y-rm*x;
    }
    return (xp, yp);
}

- Matthew Smith

---

你是不是想说这两条新的射线从所有三条射线的起点指向线段的起点和终点？如果你包括到达“这导致xp和yp的以下公式”的中间步骤，那也可能会有所帮助。 - Ellie Kesselman

你能否写出更多关于xx和yp的计算，特别是中间步骤？ - Ellie Kesselman

@EllieKesselman 是的，这两个新射线与原始射线共享一个起点，并指向线段的端点。由于射线延伸到无限远，你只需要知道如何确定交点是否发生在原始射线之间即可。 - Matthew Smith