相关疑难解决方法(0)

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

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

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

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( …

我正在为矮人要塞游戏开发一个名为Quickfort的工具.Quickfort将csv/xls格式的电子表格转换为Dwarf Fortress执行的一系列命令,以便在游戏中绘制"蓝图".

我目前正在尝试最佳地解决该工具的2.0版本的区域绘图问题.

考虑以下"蓝图",它定义了二维网格的绘图命令.网格中的每个单元格应该被挖出("d"),被引导("c")或者未被开槽(".").在实际使用中可能存在任意数量的不同绘图命令.

. d . d c c
d d d d c c
. d d d . c
d d d d d c
. d . d d c

为了最大限度地减少需要发送到Dwarf Fortress的指令数量,我想找到一组最大的连续矩形,可以形成这些矩形以完全覆盖或"绘制"所有可绘制的单元格.为了有效,所有给定矩形的单元格必须包含相同的命令.

这是比Quickfort 1.0更快的方法:将每个单元格单独绘制为1x1矩形. 此视频显示了两个版本之间的性能差异.

对于上述蓝图,解决方案如下所示:

. 9 . 0 3 2
8 1 1 1 3 2
. 1 1 1 . 2
7 1 1 1 4 2
. 6 . 5 4 2

上面的每个相同编号的矩形表示连续的矩形.最大的矩形优先于可能在其区域中形成的较小矩形.编号/矩形的顺序并不重要.

我目前的方法是迭代的.在每次迭代中,我通过从单元格的所有4个方向延伸,构建可以从每个网格的可绘制单元格形成的最大矩形的列表.在首先对列表进行排序之后,我从找到的最大矩形开始,将其基础单元格标记为"已绘制",并将矩形记录在列表中.在绘制每个矩形之前,检查其基础单元格以确保它们尚未绘制(与先前的绘图重叠).然后我们再次开始,找到可以形成的最大剩余矩形并绘制它们,直到所有单元格都被绘制为某个矩形的一部分.

我认为这种方法稍微优于愚蠢的暴力搜索,但我浪费了很多周期(重新)计算细胞的最大矩形并检查基础细胞的状态. …

简化后,我要解决以下问题:

你有一个填充0和1的二维数组.找到最小数量的矩形,使它们覆盖所有1.矩形不应重叠.

函数签名可能如下所示: List<Rectangle> FindCoveringRectangles(bool[,] array)

我已经有一个"足够好"的解决方案,但并不总能找到最小数量的矩形.我想知道是否有一些众所周知且有效的算法可用于解决这个问题？

例:

输入数组:

..........
.1.....11.
.......11.
...111....
...111....
...111....
....1111..
....1111..
......11..
..........

(为了便于阅读,将0替换为点)

可能导致以下矩形:

(2,2,2,2),
(2,8,3,9),
(4,4,6,6),
(7,5,8,8),
(9,7,9,8)

(上,左,下,右),基于1

可以有多个解决方案,但其中一个就足够了.

我不确定是否有一种算法可以解决这个问题.

给定数量的矩形从左到右水平并排放置以形成形状.给出每个的宽度和高度.

您如何确定覆盖整个形状所需的最小矩形数？即如何使用尽可能少的矩形重绘这个形状？

我只能考虑尽可能地挤压尽可能多的大矩形,但这似乎效率低下.有任何想法吗？

编辑:给你一个数字n,然后n个大小:2 1 3 2 5

上面将有两个尺寸为1x3和2x5的矩形彼此相邻.我想知道在矩形不能重叠的情况下,最不需要重建多少个矩形.

我需要通过获取其中的"元素"数量来优化网格,并尽可能地将其最小化.当我说元素时,我指的是该网格中的一个部分.这里基本上是"输入"在视觉上看起来像什么:

想到的第一个解决方案是泛洪填充算法,但是,我有一个限制:所有元素必须有4个边,因此,所有元素必须是矩形.

我的第一个有限的方法简单包括逐个元素地循环输入网格,并检查最后一个新创建的元素是否是相同的颜色,并且具有与应该创建的元素相同的alpha - 如果是,则改为创建新元素时,它只会调整最后一个元素以进一步向下延伸1个块.

这是我正在做的一个伪代码示例:

element output_array();
element last_element = null;

for (int x = 0; x < grid_width; x++) {
    for (int y = 0; y < grid_height; y++) {
        color current_input_color = input_grid(x, y);

        if (last_element && last_element.x === x && last_element.color === current_input_color) {
            last_element.span_y++;
        } else {
            last_element = create_element(
                x,                   // element.x      (the x coordinate of the elements top left most grid space)
                y,                   // element.y      (the y coordinate of the elements …

假设我有一堆矩形,其中一些是相交的,有些是孤立的.E. g.

    +--------------- +                     +-------- +
    |                |                     |         |
    |                |                     |         |
    |       A        |                     |   C     |
    |         +---------------- +          |         |
    |         |      |          |          +---------+-------- +
    |         |      |          |          |                   |
    +---------|----- +  B       |          |       D           |
              |                 |          |                   |
              |                 |          +------------------ +
              +---------------- +

    +------------------ +          +-------- +
    |                   |          |         |
    |        E          |          |   X     |
    +-------------------+          |         |
    |                   |          +-------- +
    |                   |                       +------------ +
    | …

我正在尝试渲染多边形,但它们只能使用轴对齐的矩形进行渲染.因此,我正在寻找一种基本上可以使用尽可能少的矩形填充多边形的算法.如果它有助于减少量,则允许矩形彼此重叠.

我已经实现了这种填充算法,这大部分就足够了.垮台是它限制每个像素行的矩形.我最终希望尽可能减少矩形的数量.

考虑这样的图像：

通过按颜色将像素分组到不同的矩形中，可以实现不同的配置，例如：

目标是找到最佳配置之一，即具有尽可能少的矩形的配置（矩形大小并不重要）。

关于如何设计能够解决这个问题的有效算法有什么想法吗？

编辑：我认为最好的答案是@dshin 的答案，因为他们证明这个问题是一个 NP-HARD 问题，所以可能没有任何有效的解决方案能够保证最佳结果。其他答案提供了合理的妥协以获得可接受的解决方案，但这并不总是最佳的。

http://img853.imageshack.us/img853/2475/picture1eu.jpg

我有一个点/坐标的ArrayList表示一个直线多边形.我现在想要使用ArrayList中存储的Points将这个形状分解为矩形.

我已经开始了一个算法,但我无法完成它,我觉得必须有一个更简单的方法:

ArrayList称为"allCoordinates".
ArrayList"xMatch"和"yMatch"是allCoordinates的子集.

算法:

ArrayList yMatch = All matching Coordinates in respect to 'y'

所以在上图的情况下:(
设置1 = [x1,y1] - [x8,y8],
Set2 = [x7,y7] - [x2,y2],
Set3 = [x4,y4] [x5,x5 ],
Set4 = [x3,y3] [x6,x6])

ArrayList xMatch = All matching Coordinates in respect to 'x'

所以在上图的情况下:(
Set 1 = [x1,y1] - [x2,y2],
Set2 = [x3,y3] - [x4,y4],
Set3 = [x5,y5] [x6,x6 ],
Set4 = [x7,y7] [x8,x8])

所以现在我有两个arrayLists,所有垂直边缘和所有水平边缘.现在我需要一些方法来检查它们是否全部连接在一起？就像我说的那样,必须有一个更简单的方法......？

编辑:

我可以澄清一下,必须使用在现有坐标上开始和结束的相交线来形成矩形.例如,可以从(x6,y6)水平绘制一条线,并在边缘(x1,y1) - (x8,y8)上完成.此行将从现有坐标开始,但不会在现有坐标上完成.因此该行无效.

我正在寻找一个算法如下:

给定一组可能重叠的矩形(所有这些都是"未旋转",可以统一表示为(左,上,右,下)连音符等...),它返回一组最小(非旋转)非重叠的矩形,占据相同的区域.

乍一看似乎很简单,但是很容易变得棘手(至少要有效地完成).

这个/ ideas /指针有一些已知的方法吗？

不一定是最小但是启发式小的集合的方法也很有趣,所以产生任何有效输出集的方法也是如此.

当相邻时，我想将许多不重叠的矩形压缩为较大的矩形。

我当前算法的伪代码：

do
   compress horizontally using sweep and prune
   compress horizontal output vertically using sweep and prune
while (this output is small than previous output)

这是清扫和修剪的链接。

这工作得很好，但是我想知道是否有方法导致更少的矩形输出。我认为这比我现在做的还要复杂。