它们将按从左上角到右下角的顺序从大到小排序。
此外，即使我需要完美的正方形，在最后一些非均匀缩放也是允许的，只要它们仍然保持它们的相对面积，并且非均匀缩放是以最少的量完成的。
我可以使用什么算法来实现这一点？
如何用正方形图块填满固定的矩形？
3
它们将按从左上角到右下角的顺序从大到小排序。
此外，即使我需要完美的正方形，在最后一些非均匀缩放也是允许的，只要它们仍然保持它们的相对面积，并且非均匀缩放是以最少的量完成的。
我可以使用什么算法来实现这一点？
- Joan Venge
12
这似乎很难甚至不可能，特别是在排序标准方面。我知道的装箱算法几乎没有控制正方形大小或长宽比的余地。树状图更容易，但也许您有想要正方形的原因。 - David Eisenstat
谢谢大家，GCD是什么？我刚刚发现它被称为树状图。我想我可以用它。我只是觉得完美的平方看起来更好。此外，在我的情况下，我没有那么多项目，最多100个。 - Joan Venge
如果您愿意放弃排序，可能有可能优化为一棵树，以实现近似1:1的纵横比的树状图。 - David Eisenstat
实际上，如果WPF允许您指定树形结构，则不需要新的控件。 - David Eisenstat
@Spektre，除了一切都应该尽可能接近正方形之外，没有其他限制，如果可能的话，排序应该从左上角到右下角，从大到小。就像我发送的那些图片一样。如果你谷歌加密市值地图，你可以看到许多变化，它们不试图成为正方形，但我认为这很酷。 - Joan Venge
显示剩余7条评论
2个回答
4
由于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";
}
- David Eisenstat
5
1不像正方形。 - Spektre
@Spektre：“允许一些非均匀缩放”。 - David Eisenstat
引用原文：“the non-uniform scaling is done with the least possible amount” 我在你的输出中没有看到任何正方形... - Spektre
@Spektre 这似乎是一个难题。欢迎发表您自己的答案。 - David Eisenstat
我想回答，但是输入方面有很多需要澄清的地方，如果没有这些信息，回答后意识到 OP 作者想要不同的输入组合就是浪费时间...此外，从他对 GCD 的问题来看，他似乎也缺乏必要的数学技能（尽管声望很高）...但这可能只是语言上的差异...有时我也不理解英语中的一些数学符号。 - Spektre
2
好的，假设我们使用整数位置和大小（没有浮点运算）来均匀地将矩形分成正方形网格（尽可能大的正方形），单元格的大小将是矩形大小的最大公约数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。
为了保持简单，我避免使用任何库、动态分配或容器来进行计算本身...
- Spektre
7
非常感谢！我将尝试将其移植到C#。但是，这能让我传递一个代表每个方格权重的项目列表吗？（是否归一化）例如，这样我可以拥有带有权重1、5、10、20的框，并且它们相对于它们的重量正确地表示。 - Joan Venge
1哦，抱歉我在 OP 中这样写：“代表我的物品，每个物品都有不同的重量，这将影响它们相对于其他物品的大小。”基本上所有这些重量值的总和将是承载正方形的整个空间的总面积。每个正方形将按比例使用其重量的面积，因此重量值为2的正方形的面积将是重量值为1的正方形的两倍大。这很难添加吗？ - Joan Venge
@JoanVenge 分享具体的样本输入！ - Spektre
@JoanVenge 这不是具体的输入...如果你甚至不愿意创建一个简单的单个样本输入，你怎么能指望别人回答呢？ - Spektre
我在原始帖子和评论中已经解释了一切。我不知道你还想让我如何描述它。 - Joan Venge
显示剩余2条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接