How do you check for intersection between a line segment and a line ray emanating from a point at an angle from horizontal?

Question

Given a line segment, that is two points (x1,y1) and (x2,y2), one point P(x,y) and an angle theta. How do we find if this line segment and the line ray that emanates from P at an angle theta from horizontal intersects or not? If they do intersect, how to find the point of intersection?

score 32 · Accepted Answer · edited May 23 '17 at 12:32

Let's label the points q = (x1, y1) and q + s = (x2, y2). Hence s = (x2 − x1, y2 − y1). Then the problem looks like this:

Let r = (cos θ, sin θ). Then any point on the ray through p is representable as p + t r (for a scalar parameter 0 ≤ t) and any point on the line segment is representable as q + u s (for a scalar parameter 0 ≤ u ≤ 1).

The two lines intersect if we can find t and u such that p + t r = q + u s:

See this answer for how to find this point (or determine that there is no such point).

Then your line segment intersects the ray if 0 ≤ t and 0 ≤ u ≤ 1.

ezolotko · Answer 2 · 2018-12-23T14:12:16.143

9

Here is a C# code for the algorithm given in other answers:

    /// <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;
    }

edited Dec 23 '18 at 14:12

answered Aug 21 '15 at 18:13

ezolotko

1,705
1
21
21

This is only one part of the ray vs line segment intersection test. You didn't consider the possibility of the ray and the line segment being parallel. In that case the dot product dot(v2, v3) will be 0 (or really close to 0). – Thash Aug 10 '16 at 12:41
@Thash - thank you, I have added that check. Didn't check it though, so I hope it's working correct. – ezolotko Aug 10 '16 at 19:45
1

@ezolotko unfortunately, this is still not enough. In this case, they can intersect if the ray origin and line segment endpoints are collinear (also note that the ray origin could actually be inside the line segment). Solving special cases in computational geometry is fun :) – Thash Aug 10 '16 at 21:42
I dont understand. The intersection point is a double? I would expect intersection point to be a point. – Syaiful Nizam Yahya Dec 22 '18 at 03:22
1

@SyaifulNizamYahya The double value is the distance to the intersection point from the ray origin along the ray. You can get the intersection point this way: rayOrigin + rayDirection * distance, given rayDirection is normalized (has length of 1). – ezolotko Dec 22 '18 at 09:00
1

Maybe it would be better if you change the summary to like "Returns the distance between rayorigin and intersection point" – Syaiful Nizam Yahya Dec 22 '18 at 13:04
1

Thank to you, I finally got it working. See here https://stackoverflow.com/questions/53893292/how-to-calculate-ray-line-segment-intersection-preferably-in-opencv-and-get-its/53896859#53896859 – Syaiful Nizam Yahya Dec 22 '18 at 15:54
1

@SyaifulNizamYahya I clarified the summary comment, thank you. – ezolotko Dec 23 '18 at 14:12

Daniel Farrell · Answer 3 · 2015-03-30T12:10:58.633

Thanks Gareth for a great answer. Here is the solution implemented in Python. Feel free to remove the tests and just copy paste the actual function. I have followed the write-up of the methods that appeared here, 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()

How do you check for intersection between a line segment and a line ray emanating from a point at an angle from horizontal?

3 Answers3

Linked