1

任何人都可以帮助我如何在具有 n 个矩形障碍物的边界框区域中为空间绘制矩形吗？可能有任意数量的轴平行矩形障碍物，这不是一个独特的情况，因此需要考虑不同的极端情况。最好使用最大水平条算法吗？如何？

问题描述：

1.SUB1和SUB2是障碍物，你不会触及SUB1和SUB2的内部，你需要找到所有SUB外部的所有空闲区域，并从中创建矩形。

2.您将需要在空闲区域矩形上找到所有可能的矩形，并相应地从左到右扫过而不与SUB相交；

在这种情况下，最大水平空间矩形的总数应该是 7，或者通常是 3n+2（其中 n 是障碍物的数量）： alt text http://img25.imageshack.us/img25/452/pic1gts.png

替代文字 http://img22.imageshack.us/img22/3417/pic2h.png

替代文字 http://img16.imageshack.us/img16/5818/pic3h.png

替代文字 http://img13.imageshack.us/img13/2151/pic4.png

点击查看图片： http: //img25.imageshack.us/img25/452/pic1gts.png http://img22.imageshack.us/img22/3417/pic2h.png http://img16.imageshack.us/img16 /5818/pic3h.png http://img13.imageshack.us/img13/2151/pic4.png

4

3 回答 3

1

您是在寻找最简单的算法，还是寻找最优最少分割矩形的算法？

从最容易编码的算法开始作为基线，这对于许多应用程序本身来说可能已经足够好了。这很容易编写和理解。

初始化您的矩形列表以仅包含一个，即屏幕矩形。

现在，对于每个障碍物，遍历矩形列表。如果矩形与障碍物相交，则从列表中删除矩形并插入新的、较小的矩形以避开障碍物。这是一个小子问题，只需查看障碍物的哪一部分与矩形相交即可轻松解决。您最终可能会得到 0、1、2、3 或 4 个新的子矩形。（考虑障碍物相交一个角、两个角、所有角、无角无边、无角和1条边、无角和2条边的六种情况。）

对所有障碍物重复此操作，您将得到一个分割矩形列表，这些矩形覆盖您的区域而不会碰到障碍物。它不是最好的少数，但它是一个很好的起点和 10 分钟的编码。

于 2009-03-14T01:44:03.887 回答
0

是的，我正在寻找最少的分割矩形。

我想对你的建议做一点澄清。“初始化您的矩形列表以仅包含一个，即屏幕矩形”。

屏幕矩形是指外部边界画布吗？然后，矩形列表中只有一个矩形。

“现在，对于每个障碍物，遍历矩形列表。如果矩形与障碍物相交，则从列表中删除矩形并插入新的、较小的矩形以避开障碍物。”

要继续进行上述操作，我是否应该根据障碍物的每个共线边缘（4 个边缘 - 左、右、上、下）进行比较？这意味着检查 4 个角点处的每个 SUB1 和 SUB2 边缘以查看它是否与彼此相交或与画布边界框相交。这是正确的吗？

于 2009-03-14T02:04:23.837 回答
0

角拼接数据结构可以为您做到这一点。不过，我不知道任何开源实现。最初的或至少是规范的论文是 Ousterhout（Tcl 成名）： http ://www.eecs.berkeley.edu/Pubs/TechRpts/1983/6352.html

于 2009-03-14T03:39:05.217 回答