Оптимально поместите кусок пирога в прямоугольник

Question

Учитывая прямоугольник (w, h) и круговой срез с радиусом, меньшим или равным меньшему с обеих сторон (w, h), начальным и конечным углом, как я могу оптимально разместить срез впрямоугольник так, чтобы он заполнял комнату лучше всего (с оптической точки зрения, а не математически)?

В настоящее время я помещаю центр кусочка пирога в центр прямоугольника и использую половину меньшего изобе стороны прямоугольника как радиус.Это оставляет много места для определенных конфигураций.

Примеры, чтобы прояснить, что мне нужно, исходя из предварительного условия, что срез рисуется как единичный круг (то есть 0 градусов на положительной оси X, затем часы-wise):

• Начальный угол 0 и конечный угол PI приведут к заполненной нижней половине прямоугольника и пустой верхней половине.Хорошим решением здесь было бы переместить центр вверх на 1/4 * ч.
• Начальный угол 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)

Пример вывода:

альтернативный текст http://i42.tinypic.com/3338iuu.png

альтернативный текст http://i43.tinypic.com/dztohu.png

Answer 2

Вместо псевдокода я использовал python, но он должен быть применим. Для этого алгоритма я предполагаю, что startAngle < endAngle и оба находятся в пределах [-2 * PI, 2 * PI]. Если вы хотите использовать оба в [0, 2 * PI] и позволить startAngle> endAngle, я бы сделал:

if (startAngle > endAngle):
   startAngle = startAngle - 2 * PI

Итак, алгоритм, который приходит на ум, - это рассчитать границы единичной дуги, а затем масштабировать, чтобы соответствовать вашему прямоугольнику.

Первая часть сложнее. Вам необходимо рассчитать 4 числа:

Left: MIN(cos(angle), 0)
Right: MAX(cos(angle), 0)
Top: MIN(sin(angle),0)
Bottom: MAX(sin(angle),0)

Конечно, угол - это диапазон, поэтому он не так прост, как этот. Тем не менее, вам действительно нужно включить до 11 баллов в этот расчет. Начальный угол, конечный угол и, возможно, кардинальные направления (их 9 от -2 * PI до 2 * PI.) Я собираюсь определить boundingBoxes как списки из 4 элементов, упорядоченные [left, right, top, bottom]

def IncludeAngle(boundingBox, angle)
   x = cos(angle)
   y = sin(angle)
   if (x < boundingBox[0]):
      boundingBox[0] = x
   if (x > boundingBox[1]):
      boundingBox[1] = x
   if (y < boundingBox[2]):
      boundingBox[2] = y
   if (y > boundingBox[3]):
      boundingBox[3] = y
def CheckAngle(boundingBox, startAngle, endAngle, angle):
   if (startAngle <= angle and endAngle >= angle):
      IncludeAngle(boundingBox, angle)

boundingBox = [0, 0, 0, 0]
IncludeAngle(boundingBox, startAngle)
IncludeAngle(boundingBox, endAngle)
CheckAngle(boundingBox, startAngle, endAngle, -2 * PI)
CheckAngle(boundingBox, startAngle, endAngle, -3 * PI / 2)
CheckAngle(boundingBox, startAngle, endAngle, -PI)
CheckAngle(boundingBox, startAngle, endAngle, -PI / 2)
CheckAngle(boundingBox, startAngle, endAngle, 0)
CheckAngle(boundingBox, startAngle, endAngle, PI / 2)
CheckAngle(boundingBox, startAngle, endAngle, PI)
CheckAngle(boundingBox, startAngle, endAngle, 3 * PI / 2)
CheckAngle(boundingBox, startAngle, endAngle, 2 * PI)

Теперь вы вычислили ограничивающую рамку дуги с центром 0,0 и радиусом 1. Чтобы заполнить поле, нам нужно решить линейное уравнение:

boundingBox[0] * xRadius + xOffset = 0
boundingBox[1] * xRadius + xOffset = w
boundingBox[2] * yRadius + yOffset = 0
boundingBox[3] * yRadius + yOffset = h

И мы должны решить для xRadius и yRadius. Вы заметите, что здесь есть два радиуса. Причина этого заключается в том, что для заполнения прямоугольника мы должны умножить на разные величины в двух направлениях. Поскольку ваш алгоритм запрашивает только один радиус, мы просто выберем меньшее из двух значений.

Решение уравнения дает:

xRadius = w / (boundingBox[1] - boundingBox[0])
yRadius = h / (boundingBox[2] - boundingBox[3])
radius = MIN(xRadius, yRadius)

Здесь вы должны проверить, что boundingBox[1] - boundingBox[0] является 0, и установить xRadius в бесконечность в этом случае. Это даст правильный результат, так как yRadius будет меньше. Если у вас нет бесконечности, вы можете просто установить ее на 0, а в функции MIN проверить на 0 и использовать другое значение в этом случае. xRadius и yRadius не могут быть оба 0, потому что оба sin и cos должны быть равны 0 для всех включенных выше углов, чтобы это имело место.

Теперь мы должны разместить центр дуги. Мы хотим, чтобы это было сосредоточено в обоих направлениях. Теперь мы создадим еще одно линейное уравнение:

(boundingBox[0] + boundingBox[1]) / 2 * radius + x = xCenter = w/2
(boundingBox[2] + boundingBox[3]) / 2 * radius + y = yCenter = h/2

Решение для x и y, центр дуги, дает

x = w/2 - (boundingBox[0] + boundingBox[1]) * radius / 2
y = h/2 - (boundingBox[3] + boundingBox[2]) * radius / 2

Это должно дать вам центр дуги и радиус, необходимый для помещения наибольшего круга в данный прямоугольник.

Я не тестировал ни один из этого кода, поэтому этот алгоритм может иметь огромные дыры, или, возможно, крошечные, вызванные опечатками. Я хотел бы знать, работает ли этот алгоритм.

редактирование:

Объединение всего кода дает:

def IncludeAngle(boundingBox, angle)
   x = cos(angle)
   y = sin(angle)
   if (x < boundingBox[0]):
      boundingBox[0] = x
   if (x > boundingBox[1]):
      boundingBox[1] = x
   if (y < boundingBox[2]):
      boundingBox[2] = y
   if (y > boundingBox[3]):
      boundingBox[3] = y
def CheckAngle(boundingBox, startAngle, endAngle, angle):
   if (startAngle <= angle and endAngle >= angle):
      IncludeAngle(boundingBox, angle)

boundingBox = [0, 0, 0, 0]
IncludeAngle(boundingBox, startAngle)
IncludeAngle(boundingBox, endAngle)
CheckAngle(boundingBox, startAngle, endAngle, -2 * PI)
CheckAngle(boundingBox, startAngle, endAngle, -3 * PI / 2)
CheckAngle(boundingBox, startAngle, endAngle, -PI)
CheckAngle(boundingBox, startAngle, endAngle, -PI / 2)
CheckAngle(boundingBox, startAngle, endAngle, 0)
CheckAngle(boundingBox, startAngle, endAngle, PI / 2)
CheckAngle(boundingBox, startAngle, endAngle, PI)
CheckAngle(boundingBox, startAngle, endAngle, 3 * PI / 2)
CheckAngle(boundingBox, startAngle, endAngle, 2 * PI)

if (boundingBox[1] == boundingBox[0]):
   xRadius = 0
else:
   xRadius = w / (boundingBox[1] - boundingBox[0])
if (boundingBox[3] == boundingBox[2]):
   yRadius = 0
else:
   yRadius = h / (boundingBox[3] - boundingBox[2])

if xRadius == 0:
   radius = yRadius
elif yRadius == 0:
   radius = xRadius
else:
   radius = MIN(xRadius, yRadius)

x = w/2 - (boundingBox[0] + boundingBox[1]) * radius / 2
y = h/2 - (boundingBox[3] + boundingBox[2]) * radius / 2

редактирование:

Одна из проблем заключается в том, что sin[2 * PI] не будет точно 0 из-за ошибок округления. Я думаю, что решение состоит в том, чтобы избавиться от CheckAngle вызовов и заменить их чем-то вроде:

def CheckCardinal(boundingBox, startAngle, endAngle, cardinal):
   if startAngle < cardinal * PI / 2 and endAngle > cardinal * PI / 2:
      cardinal = cardinal % 4
      if cardinal == 0:
         boundingBox[1] = 1
      if cardinal == 1:
         boundingBox[3] = 1
      if cardinal == 2:
         boundingBox[0] = -1
      if cardinal == 3:
         boundingBox[2] = -1
CheckCardinal(boundingBox, startAngle, endAngle, -4)
CheckCardinal(boundingBox, startAngle, endAngle, -3)
CheckCardinal(boundingBox, startAngle, endAngle, -2)
CheckCardinal(boundingBox, startAngle, endAngle, -1)
CheckCardinal(boundingBox, startAngle, endAngle, 0)
CheckCardinal(boundingBox, startAngle, endAngle, 1)
CheckCardinal(boundingBox, startAngle, endAngle, 2)
CheckCardinal(boundingBox, startAngle, endAngle, 3)
CheckCardinal(boundingBox, startAngle, endAngle, 4)

Вам все еще нужно IncludeAngle(startAngle) и IncludeAngle(endAngle)

Answer 3

Я бы разделил проблему на три этапа:

1. Найдите ограничивающую рамку единичного кругового среза (или, если указан радиус, фактический круговой срез с центром в (0, 0)).
2. Установите ограничивающий прямоугольник в вашем прямоугольнике.
3. Используйте информацию о подгонке ограничительной рамки, чтобы отрегулировать центр и радиус кругового среза.

Когда у меня будет время, я могу рассказать об этом подробнее.

Answer 4

Просто рассмотрите круг и забудьте о заполнении. Границы будут либо центром круга, конечными точками, либо точками в 0, 90, 180 или 270 градусах (если они существуют в этом срезе). Максимумы и минимумы этих семи точек будут определять ваш ограничивающий прямоугольник.

Что касается размещения его в центре, вычислите среднее значение для максимума и минимума как для прямоугольника, так и для кругового среза, и сложите или вычтите разность этих величин в зависимости от того, который вы хотите переместить.