3

我正在寻找一种将二维数组转换为尽可能少的矩形的方法，如下例所示：

       X
    12345678
    --------
  1|00000000
  2|00011100
  3|00111000
Y 4|00111000
  5|00111000
  6|00000000

到矩形的角坐标：

遵循 (x1,y1);(x2;y2) 模板

rectangle #1 (4,2);(6,2)
rectangle #2 (3,3);(5,5)

之前这里有一个类似的问题，但不幸的是，其答案中提供的链接已损坏，我无法再检查它。

我想在 C# 中执行此操作，但感谢任何形式的帮助。

（它甚至不必是尽可能少的矩形，但越少越好:)）

提前致谢！

4

2 回答 2

2

我认为您正在尝试用最少的矩形数量覆盖 2D 平面中的一组点。Find k rectangles so they cover the maximum number of points的答案说这是一个 NP 完全问题并链接到http://www.almaden.ibm.com/u/kclarkson/set_cover/p.pdf（其中对我有用）谷歌搜索发现h​​ttp://2011.cccg.ca/PDFschedule/papers/paper102.pdf。

有论文同意矩形覆盖是 NP 完全的，但实际上并没有证明它，并且对此的参考似乎异常难以捉摸 - https://cstheory.stackexchange.com/questions/3957/prove-that-the-problem- of-rectilinear-picture-compression-is-np-complete

我从这些文件中得到的是：

1) 不太可能有一种经济实惠的方式来获得大问题的绝对最佳答案，因此您可能不得不花费大量时间通过耗尽所有可能的方法来为某种意义上的小问题获得准确答案替代方案，或者可能使用分支定界之类的方法，或者选择负担得起的方法——比如贪婪搜索、光束搜索或有限差异搜索——这些都不能保证给你绝对最好的答案。

2）在这种情况下，这个问题似乎有更多的受限版本，它们不是 NP 完全的。您可能会阅读一篇论文并发现您的问题有一些细节，这意味着该方法适用于您。一个例子是 Franzblau 和 Kleitman 的“用矩形构造区域的算法：独立和最小生成集用于区间集合*”——不过，我在 ACM 数字图书馆中找到了这个——我不知道它是否通常可以访问。它适用于一组受限的多边形。

于 2012-09-30T05:01:06.470 回答
-1

这可能会帮助您入门。如果将二进制数据转换为数字，则会得到：

0
28
56
56
56
0

因此，只要有连续相等的数字，就会有一个矩形。

于 2012-09-30T02:38:36.130 回答