相关疑难解决方法(0)

我有一组矩形,我想"减少"这个集合,所以我有最少的矩形来描述与原始集合相同的区域.如果可能的话,我希望它也快,但我更关心的是尽可能减少矩形的数量.我现在有一种方法,大部分时间都可以使用.

目前,我从最左上角的矩形开始,看看我是否可以在保持矩形的同时向右和向下展开它.我这样做,直到它不能再展开,删除并拆分所有相交的矩形,并在列表中添加展开的矩形.然后我再次使用下一个左上角的矩形开始该过程,依此类推.但在某些情况下,它不起作用.例如:

使用这组三个矩形,正确的解决方案最终会有两个矩形,如下所示:

但是,在这种情况下,我的算法从处理蓝色矩形开始.这会向下扩展并分割黄色矩形(正确).但是当处理黄色矩形的剩余部分时,它不是向下扩展,而是首先向右扩展并收回先前分离的部分.然后处理最后一个矩形,它不能向右或向下扩展,因此保留原始的矩形集.我可以调整算法,先向下扩展然后向右扩展.这将解决这种情况,但它会在翻转的类似场景中导致同样的问题.

编辑:只是为了澄清,原始的矩形集不重叠,不必连接.如果连接了矩形的子集,则完全覆盖它们的多边形可以在其中具有孔.

我正在为矮人要塞游戏开发一个名为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个方向延伸,构建可以从每个网格的可绘制单元格形成的最大矩形的列表.在首先对列表进行排序之后,我从找到的最大矩形开始,将其基础单元格标记为"已绘制",并将矩形记录在列表中.在绘制每个矩形之前,检查其基础单元格以确保它们尚未绘制(与先前的绘图重叠).然后我们再次开始,找到可以形成的最大剩余矩形并绘制它们,直到所有单元格都被绘制为某个矩形的一部分.

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