Intersection or overlap of two line segments

Question

Given two line segments, each defined by two points, how can I determine their intersection or overlap most efficiently?

Intersection being defined as the two segments crossing each other, in actual contact. Overlapping being defined as both having the same x value or the same y value at each end point but also at least one end being between the points of the other line.

I'm asking this as I am interested to find a routine which calculates both and returns the intersection as a line segment, even if it has both points at the same location (intersection rather than overlap).

Using Lua, the function I have for calculating overlap is:

local function getParallelLineOverlap( ax, ay, bx, by, cx, cy, dx, dy )
    local function sortAB( a, b )
        return math.min( a, b ), math.max( a, b )
    end

    ax, bx = sortAB( ax, bx )
    cx, dx = sortAB( cx, dx )

    local OverlapInterval = nil
    if (bx - cx >= 0 and dx - ax >=0 ) then
        OverlapInterval = { math.max(ax, cx), math.min(bx, dx) }
    end

    return OverlapInterval
end

Also using Lua, the function I have for calculating intersection is:

local function doLinesIntersect( a, b, c, d )
    -- parameter conversion
    local L1 = {X1=a.x,Y1=a.y,X2=b.x,Y2=b.y}
    local L2 = {X1=c.x,Y1=c.y,X2=d.x,Y2=d.y}

    -- Denominator for ua and ub are the same, so store this calculation
    local _d = (L2.Y2 - L2.Y1) * (L1.X2 - L1.X1) - (L2.X2 - L2.X1) * (L1.Y2 - L1.Y1)

    -- Make sure there is not a division by zero - this also indicates that the lines are parallel.
    -- If n_a and n_b were both equal to zero the lines would be on top of each
    -- other (coincidental).  This check is not done because it is not
    -- necessary for this implementation (the parallel check accounts for this).
    if (_d == 0) then
        return false
    end

    -- n_a and n_b are calculated as seperate values for readability
    local n_a = (L2.X2 - L2.X1) * (L1.Y1 - L2.Y1) - (L2.Y2 - L2.Y1) * (L1.X1 - L2.X1)
    local n_b = (L1.X2 - L1.X1) * (L1.Y1 - L2.Y1) - (L1.Y2 - L1.Y1) * (L1.X1 - L2.X1)

    -- Calculate the intermediate fractional point that the lines potentially intersect.
    local ua = n_a / _d
    local ub = n_b / _d

    -- The fractional point will be between 0 and 1 inclusive if the lines
    -- intersect.  If the fractional calculation is larger than 1 or smaller
    -- than 0 the lines would need to be longer to intersect.
    if (ua >= 0 and ua <= 1 and ub >= 0 and ub <= 1) then
        local x = L1.X1 + (ua * (L1.X2 - L1.X1))
        local y = L1.Y1 + (ua * (L1.Y2 - L1.Y1))
        return {x=x, y=y}
    end

    return false
end

you are talking about line segments, not lines... lines have infinite length — Piglet, Aug 03 '17 at 09:09
Possible duplicate of [How do you detect where two line segments intersect?](https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect) — MBo, Aug 03 '17 at 13:49

darkfrei · Answer 1 · 2021-08-01T20:08:30.067

Here is my solution:

function get_intersection (ax, ay, bx, by, cx, cy, dx, dy) -- start end start end
    local d = (ax-bx)*(cy-dy)-(ay-by)*(cx-dx)
    if d == 0 then return end  -- they are parallel
    local a, b = ax*by-ay*bx, cx*dy-cy*dx
    local x = (a*(cx-dx) - b*(ax-bx))/d
    local y = (a*(cy-dy) - b*(ay-by))/d
    if x <= math.max(ax, bx) and x >= math.min(ax, bx) and
        x <= math.max(cx, dx) and x >= math.min(cx, dx) then
        -- between start and end of both lines
        return {x=x, y=y}
    end
end

Intersection or overlap of two line segments

1 Answers1