求焦点与准线定义的抛物线对应二次贝塞尔曲线第三控制点（Lua）

问题背景 #

在采用扫线法生成Voronoi图的Fortune算法中，需要构造与指定抛物线等价的二次贝塞尔曲线。该抛物线由焦点(fx, fy)和准线dirY定义，曲线端点为A(ax, ay)与B(bx, by)，目标是求解对应的二次贝塞尔曲线第三控制点C(cx, cy)。

初始实现的问题 #

初始编写的Lua函数仅在AB段为水平状态时能正常工作，非水平场景下计算结果错误，代码如下：

function getBezierControlPoint_focus_directrix(fx, fy, ax, ay, bx, by)
    -- (x-h)^2=4*p*(y-k)
    if (ay == by) then
        -- exception: horizontal AB
        local k = (fy + dirY) / 2
        local h = fx
        local cx = h
        local cy = ay + 2*(k-ay)
        return cx, cy -- it works perfect
    else
        local h = fx
        local k = (fy + dirY) / 2
        local cx = (ax+bx)/2
        local f = (k-dirY)/2
        
        -- vertex
        -- h = -b/(2*a)
        -- k = (4*a*c-b*b)/(4*a)
        
        local a = -1/(dirY-ay)
        local b = -2 * a * h
        local c = h * h * a + k
        print ('h', h, -b/(2*a)) -- ok, same
        print ('k', k, (4*a*c-b*b)/(4*a)) -- ok, same
        
        -- derivative value of parabola in point A (ax):
        local day = a*2*ax + b
        local cy = ay + day * (bx-ax)/2
        
        return cx, cy -- not right, here is problem
    end
end

更新后的可用函数 #

基于抛物线与二次贝塞尔曲线的等价关系，更新后的函数可正确处理所有合法场景（焦点与准线重合时直接返回，此时不构成抛物线），代码如下：

function getBezierControlPoint (fx, fy, ax, bx)
    local function f(x) return (x*x-2*fx*x+fx*fx+fy*fy-dirY*dirY) / (2*(fy-dirY)) end
    local function df(x) return (x-fx) / (fy-dirY) end
    if (fy == dirY) then return end -- not parabola
    local ay, by = f(ax), f(bx)
    local ad, dx = df(ax), (bx-ax)/2
    local cx, cy = ax+dx, ay+ad*dx
    return cx, cy
end

使用方式 #

获取控制点后，二次贝塞尔曲线的控制点序列可按如下方式构造：

controlPoints = {ax, ay, cx, cy, bx, by}

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