algorithm - 最佳地将饼图切片放置在矩形中

Question

给定一个矩形 (w, h) 和一个半径小于或等于两边 (w, h) 中较小者的饼图切片、起始角和终止角，我如何才能将切片最佳地放置在矩形，以便它最好地填充房间(从光学角度，而不是数学角度)？

我目前将饼图切片的中心放在矩形的中心，并使用两个矩形边中较小边的一半作为半径。这为某些配置留出了足够的空间。

基于将切片绘制为单位圆(即正 X 轴上的 0 度，然后顺时针运行)的前提条件，阐明我所追求的示例:

• 起始角度为 0 和结束角度为 PI 将导致矩形的下半部分填充，上半部分为空。一个好的解决方案是将中心向上移动 1/4*h。
• 起始角为 0 度和结束角为 PI/2 将导致填充矩形的右下四分之一。这里一个好的解决方案是将中心点移动到矩形的左上角，并将半径设置为两个矩形边中较小的一个。

这对于我所描绘的情况来说相当容易，但是当开始和结束角度是任意的时它会变得复杂。我正在寻找一种算法，该算法以最佳填充矩形的方式确定切片的中心和半径。伪代码会很棒，因为我不是一个大数学家。

Answer 1

圆弧边界框的极值采用以下格式:

x + x0 * r = 0
x + x1 * r = w
y + y0 * r = 0
y + y1 * r = h

值 x0、x1、y0 和 y1 是通过取最多 7 个点的最小值和最大值找到的:跨越的任何切点(即 0、90、180 和 270 度)和终点两条线段。

给定圆弧 (x0, y0), (x1, y1) 的轴对齐边界框的极值，半径和中心点可以计算如下:

r = min(w/(x1-x0), h/(y1-y0)
x = -x0 * r
y = -y0 * r

这是一个用 Lua 编写的实现:

-- ensures the angle is in the range [0, 360)
function wrap(angle)
    local x = math.fmod(angle, 2 * math.pi)
    if x < 0 then
        x = x + 2 * math.pi
    end
    return x
end

function place_arc(t0, t1, w, h)
    -- find the x-axis extrema
    local x0 = 1
    local x1 = -1
    local xlist = {}
    table.insert(xlist, 0)
    table.insert(xlist, math.cos(t0))
    table.insert(xlist, math.cos(t1))
    if wrap(t0) > wrap(t1) then
        table.insert(xlist, 1)
    end
    if wrap(t0-math.pi) > wrap(t1-math.pi) then
        table.insert(xlist, -1)
    end
    for _, x in ipairs(xlist) do
        if x < x0 then x0 = x end
        if x > x1 then x1 = x end
    end

    -- find the y-axis extrema
    local ylist = {}
    local y0 = 1
    local y1 = -1
    table.insert(ylist, 0)
    table.insert(ylist, math.sin(t0))
    table.insert(ylist, math.sin(t1))
    if wrap(t0-0.5*math.pi) > wrap(t1-0.5*math.pi) then
        table.insert(ylist, 1)
    end
    if wrap(t0-1.5*math.pi) > wrap(t1-1.5*math.pi) then
        table.insert(ylist, -1)
    end
    for _, y in ipairs(ylist) do
        if y < y0 then y0 = y end
        if y > y1 then y1 = y end
    end

    -- calculate the maximum radius the fits in the bounding box
    local r = math.min(w / (x1 - x0), h / (y1 - y0))

    -- find x & y from the radius and minimum extrema
    local x = -x0 * r
    local y = -y0 * r

    -- calculate the final axis-aligned bounding-box (AABB)
    local aabb = {
        x0 = x + x0 * r,
        y0 = y + y0 * r,
        x1 = x + x1 * r,
        y1 = y + y1 * r
    }

    return x, y, r, aabb
end

function center_arc(x, y, aabb, w, h)
    dx = (w - aabb.x1) / 2
    dy = (h - aabb.y1) / 2
    return x + dx, y + dy
end

t0 = math.rad(60)
t1 = math.rad(300)
w = 320
h = 240
x, y, r, aabb = place_arc(t0, t1, w, h)
x, y = center_arc(x, y, aabb, w, h)
print(x, y, r)

示例输出: