0%

矩形的近似密铺

pic1

不知道有没有这方面的轮子 于是就自己造了一个轮子

准备工作

定义Rect

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Rect : IComparable<Rect>
{
public int X { get; set; }
public int Y { get; set; }
public int Width { get; set; }
public int Height { get; set; }
//颜色是做可视化用的
public Color Color { get; set; }
//是否被放置
public bool Done { get; set; }

public Rect(int x, int y, int width, int height)
{
Random rd = new Random();

X = x;
Y = y;
Width = width;
Height = height;
Done = false;
Color = Color.FromArgb(255, (byte)rd.Next(0, 255), (byte)rd.Next(0, 255), (byte)rd.Next(0, 255));
}

//比较函数 要实现 IComparable<Rect>.CompareTo([AllowNull] Rect other)
//为什么是比较高度呢? 后面会提到
public int CompareTo([AllowNull] Rect other)
{
if (Height > other.Height)
{
return -1;
}
else if (Height < other.Height)
{
return 1;
}
else
{
return 0;
}
}
}

定义Tessellation函数

1
2
3
4
static public void Tessellation(int RgnLeft, int RgnTop, int RgnW, int RgnH, int RectNum, ref Rect[] rects)
{

}

理论研究

放置

如图是我们待填充的区域 称为Rgn

pic2

现在我们往里面放一个rect

pic3

分割

除了黑色的rect 图中还有蓝色的空余不规则图形

那我们这才放了一个 还得继续放 放在哪 当然是放在蓝色空闲区域 那我们得先把他变规则

为了让这个不规则图形变规则 我们用一条黑线 分成两部分

那么为什么不是竖着分而是横着分呢 因为在今天的案例(案例就是没有案例)中 我们的数据倾向于横着铺 如果你的数据是竖着 那就需要做相应的更改

分出的两个区域 各信息如下 (其中RectX表示放入该矩形的各信息)

RgnLeft RgnTop RgnW RgnH
Rgn1 RgnLeft + RectW RgnTop RgnW - RectW RectH
Rgn2 RgnLeft RgnTop + RectH RgnW RgnH - RectH

现在往Rgn1里面放矩形

pic4

到这里 你应该懂了 后面的操作 就是无限套娃

是的 递归

递归出口

这很好想

  • 放不进去的时候 返回
  • 矩形用完的时候 返回

放置顺序

看图

pic5

矩形的高度太小 导致第一行什么也放不进去

故而 我们第一行应该优先放高度大的

在执行Tessellation函数前 我们应该把矩形按照高度逆序排序

这也是Rect类中 CompareTo函数的由来

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
static public void Tessellation(int RgnLeft, int RgnTop, int RgnW, int RgnH, int RectNum, ref Rect[] rects)
{
if (RectNum != 0)
{
//遍历
for (int i = 0; i < RectNum; i++)
{
//放得进去 而且还没放
if (!rects[i].Done && rects[i].Width <= RgnW && rects[i].Height <= RgnH)
{
//递归出口
if (i >= RectNum || i < 0)
{
return;
}
if (i == RectNum && rects[i].Done)
{
return;
}

//放置该矩形
rects[i].X = RgnLeft;
rects[i].Y = RgnTop;
rects[i].Done = true;

//继续处理分割出的两个Rgn
Tessellation(RgnLeft + rects[i].Width, RgnTop, RgnW - rects[i].Width, rects[i].Height, RectNum, ref rects);
Tessellation(RgnLeft, RgnTop + rects[i].Height, RgnW, RgnH - rects[i].Height, RectNum, ref rects);

//处理完毕 返回
break;
}
}
}
}

完整实现

算法 + 可视化

Github仓库 https://github.com/F-Unction/RectAlmostTessellation

求个Star $QAQ$

下面是Gif效果图

pic5