解析二维数组矩形 [英] Parse 2D array to rectangles

问题描述

我在寻找一种方式来一个二维数组到尽可能少的矩形转换就像这个例子：

I'm looking for a way to convert a 2D array to the fewest possible rectangles like in this example:

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

到矩形的角落坐标：

to the corner coordinates of the rectangles:

以下的（X1，Y1）;（2次; y2）上模板

following the (x1,y1);(x2;y2) template

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

已经有过类似的问题在这里出现，但遗憾的是，在它的答案提供的链接坏了，我无法检查它了。

There has been a similar question here before but unfortunately, the link provided in its answer is broken, and I cannot check it anymore.

我想做到这一点在C＃中，但任何形式的帮助是AP preciated。

I'd like to do this in C# but any kind of help is appreciated.

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

(It doesn't even have to be the fewest possible rectangles, but the fewer the better :) )

在此先感谢！

推荐答案

我认为你正在试图掩盖在2D平面与矩形的最低要求数量的点的集合。回答<一href="http://stackoverflow.com/questions/3476778/find-k-rectangles-so-that-they-cover-the-maximum-number-of-points">Find ķ矩形，使其覆盖的说，这是一个NP完全问题点的最大数量，并链接到的 http://www.almaden.ibm.com/u/kclarkson/set_cover/p.pdf （这对我的作品），阿谷歌搜索找到的 http://2011.cccg.ca/PDFschedule/papers/paper102.pdf 。

I think that you are trying to cover a set of points in the 2D plane with the minimum required number of rectangles. An answer to Find k rectangles so that they cover the maximum number of points said that this was an NP-complete problem and linked to http://www.almaden.ibm.com/u/kclarkson/set_cover/p.pdf (which works for me) A google search finds http://2011.cccg.ca/PDFschedule/papers/paper102.pdf.

有篇同意矩形覆盖是NP完全问题，但实际上并没有证明这一点，并为此引用显得异常难以捉摸 - <一个href="http://cstheory.stackexchange.com/questions/3957/prove-that-the-problem-of-rectilinear-picture-com$p$pssion-is-np-complete">http://cstheory.stackexchange.com/questions/3957/prove-that-the-problem-of-rectilinear-picture-com$p$pssion-is-np-complete

There papers agree that rectangle covering is NP-complete but do not actually prove it, and the references for this seem to be unusually elusive - http://cstheory.stackexchange.com/questions/3957/prove-that-the-problem-of-rectilinear-picture-compression-is-np-complete

什么我从这些文件是这样的：

What I take from these documents is this:

1），这是不可能的，有越来越的大问题，绝对是最好的答案的一个经济实惠的方式，所以你可能必须要么花费大量的时间来获得确切答案的问题，在某种意义上小，而排气在所有可能的选择或者使用类似分支机构和束缚，也不满足于经济实惠的方法 - 就像贪婪搜索，或束搜索，或限制出入搜索 - 这是不能保证给你绝对是最佳答案

1) It is unlikely that there is an affordable way of getting the absolutely best answer for large problems, so you might have to either spend a lot of time to get exact answers for problems that are in some sense small, by exhausting over all possible alternatives or perhaps using something like branch and bound, or settle for affordable methods - like greedy search, or beam search, or limited discrepancy search - which are not guaranteed to give you the absolutely best answer.

2）在这种情况下，似乎有此问题的更受限制的版本是不NP完全问题。你有可能会读报纸，发现有你的问题的一些细节，这意味着，该方法适用于您。一个例子是构造算法地区矩形： 独立性和最小发电机组 FOR间隔COLLECTIONS *，由Franzblau和克莱特曼 - 我的ACM数字图书馆中发现了这一点，虽然 - 我不知道这是否是普遍接近它适用于受限制的组多边形

2) In this case there seem to be more restricted versions of this problem which are not NP-complete. You might possibly read a paper and find that there is some detail of your problem that means that this method applies to you. One example is "AN ALGORITHM FOR CONSTRUCTING REGIONS WITH RECTANGLES: INDEPENDENCE AND MINIMUM GENERATING SETS FOR COLLECTIONS OF INTERVALS*" by Franzblau and Kleitman - I found this in the ACM Digital Library, though - I don't know if it is generally accessible. It works for a restricted set of polygons.

这篇关于解析二维数组矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！