fill region with minimum number of rectangles

4 次查看（过去 30 天）
Shane
Shane 2015-8-12
回答： Walter Roberson 2015-8-13
I have a image/matrix as shown in the attached picture.
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.

请先登录，再回答此问题。

回答（1 个）

Walter Roberson
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.

类别

在 Help Center 和 File Exchange 中查找有关 Image Arithmetic 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by