用矩形填充直线多边形

Question

给定一个多边形,完全由矩形创建,并由一个点数组定义,其中边始终与轴对齐:

我正在尝试确定一种快速算法,以找到可填充此形状的少量矩形.这是我手工绘制的,用于显示我描述的矩形集合:

编辑: 这是一些简单的处理代码来创建这个形状(好吧,靠近它).

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 );
}

Answer 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)