Минимальная площадь ограждающих прямоугольников? - PullRequest
Новая
       37

Минимальная площадь ограждающих прямоугольников?

4 голосов
/ 05 ноября 2011

Мне нужна идея алгоритма для решения следующей проблемы (я уже попробовал некоторые личные решения, но они не кажутся оптимальными)

Если задана поверхность с отмеченными и немаркированными зонами (в матричной форме) и 2 прямоугольниками что вы можете манипулировать в любой форме или позиции, найти возможные формы и позиции прямоугольников, чтобы они покрывали все отмеченные зоны, сохраняя при этом площадь поверхности возможна.

1 Ответ

3 голосов
/ 08 ноября 2011

В этом ответе предполагается, что вы не можете поворачивать прямоугольники, а стороны всегда параллельны осям x и y.

Сначала найдите прямоугольник, охватывающий всю область.Алгоритм для этого выглядит следующим образом (при условии, что источник находится на вершине): 

For each marked spot in the matrix:
    if spot.x < rectangle.left:
        rectangle.left = spot.x
    if spot.x > rectangle.right:
        rectangle.left = spot.x
    if spot.y < rectangle.top:
        rectangle.left = spot.x
    if spot.y < rectangle.bottom:
        rectangle.left = spot.x

Затем найдите самый большой горизонтальный разрыв, как этот: 

largest_gap = -1
For each column in matrix:
     last_marked_spot = 0, 0
     For each spot in column:
         if spot.marked:
             if spot.x - last_marked_spot.x > largest_gap:
                 largest_gap = spot.x - last_marked_spot.x
             last_marked_spot = spot

То же самое относится к вертикальному разрыву,Затем проверьте, какой зазор является наибольшим.

Затем разделите прямоугольник, состоящий из всех частей, на две части, используя самый большой зазор в качестве разделителя.Последний шаг - сворачивание двух прямоугольников (с использованием обратного алгоритма сверху).

...