Заполнение прямолинейного многоугольника прямоугольниками

Учитывая многоугольник, созданный полностью из прямоугольников и определяемый массивом точек, где ребра всегда выровнены с осью:

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

EDIT: Вот несколько простых processing код для создания этой формы (ну, рядом с ней).

float[] xpts = {0,    50,  50,  100, 100, 150, 150, 250, 250, 300, 300, 325, 325, 300, 300, 250, 250, 210, 210, 250, 250, 125, 125, 25, 25,   50,  50,  0 };
float[] ypts = {100, 100,  80,   80, 10,   10,  80, 80,  75,  75, 80,   80,  200, 200, 300, 300, 275, 275, 260, 260, 200, 200, 270, 270, 165, 165, 125, 125};


void setup( )
{
  size( 350, 350 );
}

void draw( )
{

stroke( 0 );
strokeWeight( 1.5 );

float px = xpts[0];
float py = ypts[0];
for (int i=1; i < xpts.length; i++)
{
  float nx = xpts[i];
  float ny = ypts[i];
  line( px, py, nx, ny );


  px = xpts[i];
  py = ypts[i];
}
float nx = xpts[0];
float ny = ypts[0];

line( px, py, nx, ny );
}

Ответ 1

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

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

Вот некоторый псевдокод:

function makeRects(Rect r, Polygon p)

  if p is empty
    if r is inside your original polygon
      add r to results

  else
    choose good splitter s

    makeRects(left part of r relative to s, left part of p relative to s)
    makeRects(right part of r relative to s, right part of p relative to s)

Ответ 2

Мне очень нравится проблема NP. Это означает, что есть несколько алгоритмов, которые могут быстро заполнить вашу форму прямоугольниками, если количество прямоугольников для вас не имеет особого значения, но если вы настаиваете на наименьшем числе, то вам лучше забыть о слове "быстро" ". На самом деле вы даже должны забыть о слове" наименьший "и вместо этого использовать" маленький", поскольку определение того, является ли множество наименьшим, уже могло быть огромной проблемой для алгоритма.

Ответ 3

Интересное обсуждение и решение здесь: http://www.gamedev.net/topic/460561-decomposing-a-rectilinear-polygon/