<p>Perhaps this is more computational geometry, but here goes:</p>
<p>I have a 2D <a href="https://en.wikipedia.org/wiki/Signed_distance_function" rel="nofollow noreferrer">SDF</a> describing my shape, but it's fine to think of it as a black/white image (black=&quot;inside&quot; white=&quot;outside&quot;).</p>
<p>I want to generate a small set of rectangles (say, 8 of them) covering the image, which are allowed to overlap, and which minimize the amount of error. Error would be any leftover &quot;black&quot; areas of the image that are not covered.</p>
<p>The image could be convex, have holes, etc. It is general.</p>
<p>I realize that minimal rectangle covering is NP-hard, though that's not exactly what I'm asking for: I'm asking for minimizing error given a finite set of rectangles to work with. Maybe it's just as hard though; not sure.</p>
<p>Anyway, I do not need to find the perfect solution; decent heuristics would be fine.</p>
<p>I could imagine some pretty general &quot;greedy search&quot; traversal of the state space, but wondered if there were any tricks anyone knows of.</p>
<p>Aside: I've also looked at several papers for &quot;rectangular decomposition&quot;, and &quot;minimal dissection&quot;, but those problems generally assume I want disjoint rectangles. Disjoint would be okay, but really I want maximal coverage while allowing overlap.</p>
<p><strong>Edit</strong> Here is an example:</p>
<p>Target image:</p>
<p><a href="https://i.sstatic.net/0AGpl.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/0AGpl.png" alt="target image" /></a></p>
<p>Covering with 4 rectangles (red, green, blue, yellow):</p>
<p><a href="https://i.sstatic.net/neYfG.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/neYfG.png" alt="covered image" /></a></p>
<p>Any uncovered black pixels are the &quot;error&quot;.
No white pixels are allowed to get covered.</p>

CC BY-SA 4.0
2021-02-03T01:46:14.497Z
So you want to fill a shape with the minimum amount of rectangles, as internally as possible. Overlap is ok. You also happen to have this shape as an SDF already. Do these need to be axes aligned rectangles or can they be oriented?
Andrew Wilson
CC BY-SA 4.0
2021-02-03T02:04:36.610Z
@AndrewWilson: I added an image to clarify. Generally what you say is true, but I would amend "as internally as possible" to be "the covering rects *must not* spill out of the 'black' area" (so "fully internally"?). Yes, they do need to be axis-aligned.
jwd
<signed-distance-field>
Good rectangular covering of an SDF
jwd
# Good rectangular covering of an SDF

(Asked by: username_0 on 2021-02-02)

Perhaps this is more computational geometry, but here goes:

I have a 2D [SDF](https://en.wikipedia.org/wiki/Signed_distance_function) describing my shape, but it's fine to think of it as a black/white image (black="inside" white="outside").

I want to generate a small set of rectangles (say, 8 of them) covering the image, which are allowed to overlap, and which minimize the amount of error. Error would be any leftover "black" areas of the image that are not covered.

The image could be convex, have holes, etc. It is general.

I realize that minimal rectangle covering is NP-hard, though that's not exactly what I'm asking for: I'm asking for minimizing error given a finite set of rectangles to work with. Maybe it's just as hard though; not sure.

Anyway, I do not need to find the perfect solution; decent heuristics would be fine.

I could imagine some pretty general "greedy search" traversal of the state space, but wondered if there were any tricks anyone knows of.

Aside: I've also looked at several papers for "rectangular decomposition", and "minimal dissection", but those problems generally assume I want disjoint rectangles. Disjoint would be okay, but really I want maximal coverage while allowing overlap.

**Edit** Here is an example:

Target image:

[![target image](https://i.sstatic.net/0AGpl.png)](https://i.sstatic.net/0AGpl.png)

Covering with 4 rectangles (red, green, blue, yellow):

[![covered image](https://i.sstatic.net/neYfG.png)](https://i.sstatic.net/neYfG.png)

Any uncovered black pixels are the "error".
No white pixels are allowed to get covered.

**Tags:** signed-distance-field

> **Comments:**
> **username_1**: So you want to fill a shape with the minimum amount of rectangles, as internally as possible. Overlap is ok. You also happen to have this shape as an SDF already. Do these need to be axes aligned rectangles or can they be oriented?  
> **username_0**: @username_1: I added an image to clarify. Generally what you say is true, but I would amend "as internally as possible" to be "the covering rects *must not* spill out of the 'black' area" (so "fully internally"?). Yes, they do need to be axis-aligned.  

---

## 0 answers

