两线段的交集或重叠

给定两个由两个点定义的线段，如何最有效地确定它们的交集或重叠？

交集被定义为两个线段相交，实际接触。 重叠被定义为两端点具有相同的 x 值或相同的 y 值，但同时至少一个端点位于另一条线段的点之间。

我之所以问这个问题，是因为我想找到一种计算两者并返回交点的例程，即使它具有相同位置的两个点（交点而不是重叠）。

使用 Lua，我计算重叠的函数是：

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

另外使用 Lua，我计算交点的函数是：

local function doLinesIntersect( a, b, c, d )
    -- 参数转换
    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}

    -- 计算 ua 和 ub 的分母相同，因此存储此计算
    local _d = (L2.Y2 - L2.Y1) * (L1.X2 - L1.X1) - (L2.X2 - L2.X1) * (L1.Y2 - L1.Y1)

    -- 确保没有被零除 - 这也表示线条平行
    -- 如果 n_a 和 n_b 都等于零，线段将彼此在上方
    -- 其他（巧合）的。未执行此检查，因为它不是这个实现所必需的
    if (_d == 0) then
        return false
    end

    -- 对于可读性，n_a 和 n_b 被计算为独立的值
    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)

    -- 计算线段可能相交的中间分数点
    local ua = n_a / _d
    local ub = n_b / _d

    -- 如果线段相交，分数点将在 0 和 1 之间（含）
    -- 如果分数计算大于 1 或小于 0，则需要更长的线段才能相交。
    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