fill region with minimum number of rectangles
2 ビュー (過去 30 日間)
古いコメントを表示
I have a image/matrix as shown in the attached picture.
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/148000/image.jpeg)
My goal is to recreate the white area in the image with rectangles. That is, I want to recreate the image by defining a bunch of rectangles (and keep each rectangle separate). However, I want to automatically determine the fewest number of rectangles as possible, and create those N rectangles.
The image will always be of this type, nothing but right angle transitions, though the pattern will vary.
Any good ideas/tips on where to start? This seems complex to me.
0 件のコメント
回答 (1 件)
Walter Roberson
2015 年 8 月 13 日
This is a Multidimensional Constrained Knapsack Problem and it is NP-Complete (that is, in the category of "very hard" problems that get more expensive faster than any fixed polynomial.)
The problem is in proving that any given solution is the minimum number of rectangles. Solutions can be proposed that are "pretty good" and easy to implement, but proving that there is no way that you could do better is the difficult part.
0 件のコメント
参考
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!