由于Hiroshi Nagamochi和Yuusuke Abe提出了一种快速近似算法,我在C++中实现了它,并注意确保最坏情况下的O(n log n)时间复杂度和最坏情况下的递归深度为O(log n)。如果n≤100,则这些预防措施可能是不必要的。
#include <algorithm>
#include <iostream>
#include <random>
#include <vector>
namespace {
struct Rectangle {
double x;
double y;
double width;
double height;
};
Rectangle Slice(Rectangle &r, const double beta) {
const double alpha = 1 - beta;
if (r.width > r.height) {
const double alpha_width = alpha * r.width;
const double beta_width = beta * r.width;
r.width = alpha_width;
return {r.x + alpha_width, r.y, beta_width, r.height};
}
const double alpha_height = alpha * r.height;
const double beta_height = beta * r.height;
r.height = alpha_height;
return {r.x, r.y + alpha_height, r.width, beta_height};
}
void LayoutRecursive(const std::vector<double> &reals, const std::size_t begin,
std::size_t end, double sum, Rectangle rectangle,
std::vector<Rectangle> &dissection) {
while (end - begin > 1) {
double suffix_sum = reals[end - 1];
std::size_t mid = end - 1;
while (mid > begin + 1 && suffix_sum + reals[mid - 1] <= 2 * sum / 3) {
suffix_sum += reals[mid - 1];
mid -= 1;
}
LayoutRecursive(reals, mid, end, suffix_sum,
Slice(rectangle, suffix_sum / sum), dissection);
end = mid;
sum -= suffix_sum;
}
dissection.push_back(rectangle);
}
std::vector<Rectangle> Layout(std::vector<double> reals,
const Rectangle rectangle) {
std::sort(reals.begin(), reals.end());
std::vector<Rectangle> dissection;
dissection.reserve(reals.size());
LayoutRecursive(reals, 0, reals.size(),
std::accumulate(reals.begin(), reals.end(), double{0}),
rectangle, dissection);
return dissection;
}
std::vector<double> RandomReals(const std::size_t n) {
std::vector<double> reals(n);
std::exponential_distribution<> dist;
std::default_random_engine gen;
for (double &real : reals) {
real = dist(gen);
}
return reals;
}
} // namespace
int main() {
const std::vector<Rectangle> dissection =
Layout(RandomReals(100), {72, 72, 6.5 * 72, 9 * 72});
std::cout << "%!PS\n";
for (const Rectangle &r : dissection) {
std::cout << r.x << " " << r.y << " " << r.width << " " << r.height
<< " rectstroke\n";
}
std::cout << "showpage\n";
}
好的,假设我们使用整数位置和大小(没有浮点运算)来均匀地将矩形分成正方形网格(尽可能大的正方形),单元格的大小将是矩形大小的最大公约数GCD。
然而,您想要比这少得多的正方形,所以我会尝试以下方法:
尝试所有从1到矩形较小尺寸的正方形尺寸a
对于每个a
,计算剩余矩形的朴素正方形网格大小,一旦切掉a*a
正方形
因此,它只是在2个矩形上再次使用GCD,这些矩形将在切掉a*a
正方形后创建。如果所有3个尺寸的最小值a
和2个矩形的GCD大于1(忽略零面积矩形),则将a
视为有效解决方案,因此请记住它。
在for
循环之后使用最后找到的有效a
因此,只需将a*a
正方形添加到输出中,并对从切掉a*a
正方形后剩余的原始矩形进行递归,再次执行整个过程。
这里是一个简单的C++ / VCL / OpenGL示例:
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
#include "gl_simple.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
class square // simple square
{
public:
int x,y,a; // corner 2D position and size
square(){ x=y=a=0.0; }
square(int _x,int _y,int _a){ x=_x; y=_y; a=_a; }
~square(){}
void draw()
{
glBegin(GL_LINE_LOOP);
glVertex2i(x ,y);
glVertex2i(x+a,y);
glVertex2i(x+a,y+a);
glVertex2i(x ,y+a);
glEnd();
}
};
int rec[4]={20,20,760,560}; // x,y,a,b
const int N=1024; // max square number
int n=0; // number of squares
square s[N]; // squares
//---------------------------------------------------------------------------
int gcd(int a,int b) // slow euclid GCD
{
if(!b) return a;
return gcd(b, a % b);
}
//---------------------------------------------------------------------------
void compute(int x0,int y0,int xs,int ys)
{
if ((xs==0)||(ys==0)) return;
const int x1=x0+xs;
const int y1=y0+ys;
int a,b,i,x,y;
square t;
// try to find biggest square first
for (a=1,b=0;(a<=xs)&&(a<=ys);a++)
{
// sizes for the rest of the rectangle once a*a square is cut of
if (xs==a) x=0; else x=gcd(a,xs-a);
if (ys==a) y=0; else y=gcd(a,ys-a);
// min of all sizes
i=a;
if ((x>0)&&(i>x)) i=x;
if ((y>0)&&(i>y)) i=y;
// if divisible better than by 1 remember it as better solution
if (i>1) b=a;
} a=b;
// bigger square not found so use naive square grid division
if (a<=1)
{
t.a=gcd(xs,ys);
for (t.y=y0;t.y<y1;t.y+=t.a)
for (t.x=x0;t.x<x1;t.x+=t.a)
if (n<N){ s[n]=t; n++; }
}
// bigest square found so add it to result and recursively process the rest
else{
t=square(x0,y0,a);
if (n<N){ s[n]=t; n++; }
compute(x0+a,y0,xs-a,a);
compute(x0,y0+a,xs,ys-a);
}
}
//---------------------------------------------------------------------------
void gl_draw()
{
glClear(GL_COLOR_BUFFER_BIT);
glDisable(GL_DEPTH_TEST);
glDisable(GL_TEXTURE_2D);
// set view to 2D [pixel] units
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
glTranslatef(-1.0,-1.0,0.0);
glScalef(2.0/float(xs),2.0/float(ys),1.0);
// render input rectangle
glColor3f(0.2,0.2,0.2);
glBegin(GL_QUADS);
glVertex2i(rec[0] ,rec[1]);
glVertex2i(rec[0]+rec[2],rec[1]);
glVertex2i(rec[0]+rec[2],rec[1]+rec[3]);
glVertex2i(rec[0] ,rec[1]+rec[3]);
glEnd();
// render output squares
glColor3f(0.2,0.5,0.9);
for (int i=0;i<n;i++) s[i].draw();
glFinish();
SwapBuffers(hdc);
}
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner)
{
// Init of program
gl_init(Handle); // init OpenGL
n=0; compute(rec[0],rec[1],rec[2],rec[3]);
Caption=n;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormDestroy(TObject *Sender)
{
// Exit of program
gl_exit();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender)
{
// repaint
gl_draw();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormResize(TObject *Sender)
{
// resize
gl_resize(ClientWidth,ClientHeight);
}
//---------------------------------------------------------------------------
并预览实际硬编码矩形:
窗口标题中的数字8是产生的正方形数量。
请注意,这只是解决此问题的非常简单的起始示例。我没有进行过广泛的测试,因此可能会在涉及质数或不幸的长宽比时导致正方形数量非常高...例如,如果矩形大小的GCD为1(质数)...在这种情况下,您应该调整初始矩形大小(+/-1或其他)
代码中的重要部分只是compute()
函数和保存输出正方形s[n]
的全局变量...请注意,compute()
不清除列表(以允许递归),因此您需要在其非递归调用之前设置n=0
。
为了保持简单,我避免使用任何库、动态分配或容器来进行计算本身...