基于Lua实现两点与切线确定圆：无解判断及局限性问询

任务 #

给定A、B两点及由两点T1、T2定义的切线，构造过A、B两点且与该切线相切的圆G。该问题属于阿波罗尼奥斯问题中的PPL（两点与直线）场景。

求解步骤 #

• 求直线AB与切线T（T1T2）的交点P；
• 构造以AB中点为圆心、AB一半长度为半径的圆C；
• 求从点P到圆C的切线，切点为D；
• 取PD为半径，构造以P为圆心的圆；
• 求该圆与切线T的交点E1、E2；
• 分别以A、B、E1和A、B、E2为三点构造外接圆G1、G2；
• G1、G2即为问题的两个解。

示意图：

辅助函数 #

function tangentCircle (cx, cy, cr, px, py) -- circle, point
    local dx, dy = px-cx, py-cy
    local dist = math.sqrt(dx*dx+dy*dy)
    if dist <= cr then return end
    local a, b = math.atan2 (dy, dx), math.acos (cr/dist)   
    local x1 = cx + cr * math.cos (a-b)
    local y1 = cy + cr * math.sin (a-b)
    local x2 = cx + cr * math.cos (a+b)
    local y2 = cy + cr * math.sin (a+b)
    return x1, y1, x2, y2
end

function linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4)
    local dx1, dy1 = x2 - x1, y2 - y1
    local dx2, dy2 = x4 - x3, y4 - y3
    local det = dx2 * dy1 - dx1 * dy2
    if det == 0 then return end
    local c1 = x1 * y2 - y1 * x2
    local c2 = x3 * y4 - y3 * x4
    local x = (c1 * dx2 - c2 * dx1) / det
    local y = (c1 * dy2 - c2 * dy1) / det
    return x, y
end

function circleWithTwoPoints (x1, y1, x2, y2)
    local cx = (x1 + x2) / 2
    local cy = (y1 + y2) / 2
    local cr = math.sqrt((cx - x1)^2 + (cy - y1)^2)
    return cx, cy, cr
end


function intersectCircleCenterLine(cx, cy, cr, tx1, ty1, tx2, ty2)
    local angle = math.atan2 (ty2-ty1, tx2-tx1)
    local ex1, ey1 = cx + cr * math.cos (angle), cy + cr * math.sin (angle)
    local ex2, ey2 = cx + cr * math.cos (angle+math.pi), cy + cr * math.sin (angle+math.pi)
    return ex1, ey1, ex2, ey2
end

function nearestPointOnLine(tx1, ty1, tx2, ty2, cx, cy)
    local dx = tx2 - tx1
    local dy = ty2 - ty1
    local t = ((cx - tx1) * dx + (cy - ty1) * dy) / (dx * dx + dy * dy)
    local nx = tx1 + t * dx
    local ny = ty1 + t * dy
    return nx, ny
end

function circleFromThreePoints(x1, y1, x2, y2, x3, y3)
    local function distance(x1, y1, x2, y2)
        return math.sqrt((x1-x2)^2 + (y1-y2)^2)
    end

    local a = distance(x2, y2, x3, y3)
    local b = distance(x1, y1, x3, y3)
    local c = distance(x1, y1, x2, y2)
    local s = (a + b + c) / 2
    local gr = (a * b * c) / (4 * math.sqrt(s * (s - a) * (s - b) * (s - c)))
    local A = x1*(y2-y3) - y1*(x2-x3) + x2*y3 - x3*y2
    local B = (x1*x1 + y1*y1)*(y3-y2) + (x2*x2 + y2*y2)*(y1-y3) + (x3*x3 + y3*y3)*(y2-y1)
    local C = (x1*x1 + y1*y1)*(x2-x3) + (x2*x2 + y2*y2)*(x3-x1) + (x3*x3 + y3*y3)*(x1-x2)
    local D = 2*((x1-x2)*(y3-y2) - (y1-y2)*(x3-x2))

    local gx = B / D
    local gy = C / D
    return gx, gy, gr
end

主函数 #

function circlesFromTwoPointsAndTangent(ax, ay, bx, by, tx1, ty1, tx2, ty2)
    local px, py = linesIntersect(ax, ay, bx, by, tx1, ty1, tx2, ty2)
    print ('px, py', px, py) -- must be -10, 0, ok

    if px then
        -- two solutions
        local cx, cy, cr = circleWithTwoPoints (ax, ay, bx, by)
        print ('cx, cy, cr', cx, cy, cr) -- must be 65, 75, 49.497475, ok

        local dx1, dy1, dx2, dy2 = tangentCircle (cx, cy, cr, px, py)
        print ('dx1, dy1', dx1, dy1) -- must be 17.7115, 89.6218, ok
        print ('dx2, dy2', dx2, dy2) -- must be 79.6218, 27.7115, ok

        --  radius from P to D or from P to E
        local pr = math.sqrt ((dx1-px)^2+(dy1-py)^2)
        print ('pr', pr) -- must be 93.808315

        local ex1, ey1, ex2, ey2 = intersectCircleCenterLine(px, py, pr, tx1, ty1, tx2, ty2)
        local gx1, gy1, gr1 = circleFromThreePoints(ax, ay, bx, by, ex1, ey1)
        print ('gx1, gy1, gr1', gx1, gy1, gr1)
        -- must be 83.8083, 56.1917, 56.191685, ok

        local gx2, gy2, gr2 = circleFromThreePoints(ax, ay, bx, by, ex2, ey2)
        print ('gx2, gy2, gr2', gx2, gy2, gr2)
        -- must be -103.80831519647 243.80831519647 243.80831519647 ok

        return gx1, gy1, gr1, gx2, gy2, gr2
    else -- parallel
        local cx, cy, cr = circleWithTwoPoints (ax, ay, bx, by)

        local ex, ey = nearestPointOnLine(tx1, ty1, tx2, ty2, cx, cy)

        local gx, gy, gr = circleFromThreePoints(ax, ay, bx, by, ex, ey)

        return gx, gy, gr
    end
end

示例代码 #

local x1, y1 = 30, 40
local x2, y2 = 100, 110
local tx1, ty1 = -100, 0
local tx2, ty2 = 100, 0 -- horizontal line

local gx1, gy1, gr1, gx2, gy2, gr2 = circlesFromTwoPointsAndTangent(x1, y1, x2, y2, tx1, ty1, tx2, ty2)

print ('circle 1', gx1, gy1, gr1) -- must be 83.8083    56.1917 56.191685
print ('circle 2', gx2, gy2, gr2) -- must be -103.808   243.808 243.808315

问题解答 #

1. 如何判断方案无可行解？ #

• 直线AB与切线T相交时：若tangentCircle函数返回nil，说明点P到圆C的距离小于等于圆C半径，不存在从P到圆C的切线，此时无可行解。对应A、B两点在切线T同侧，且所有过A、B的圆都无法与T相切。
• 直线AB与切线T平行时：若AB中点到T的距离小于AB半长，构造出的圆无法满足与T相切的条件，此时无可行解；另外若A、B、E三点共线（E为AB垂直平分线与T的垂足），circleFromThreePoints会因计算异常返回无效值，也代表无解。

2. 输入的局限性 #

该实现对水平/竖直线无特殊兼容问题，所有计算基于通用逻辑，但存在以下局限：

• 数值精度问题：依赖浮点数运算，当点坐标接近或出现极端值时，可能因精度误差导致结果偏离，甚至出现除零、开根号负数等异常。
• 特殊场景未处理：A、B两点重合，或A/B在切线T上时，现有逻辑未做特殊判断，会导致计算错误（如circleWithTwoPoints得到半径为0，circleFromThreePoints处理共线三点时出错）。
• 无解时无明确标识：主函数在无可行解时未返回明确的错误标识，调用者需额外检查返回值是否为nil才能判断结果有效性。
• 平行场景未验证解的有效性：平行时直接构造圆，但未验证该圆是否真的与T相切，若AB中点到T的距离不足，构造出的圆不满足要求。

内容的提问来源于stack exchange，提问作者darkfrei