3
$\begingroup$

I have a 2D SDF 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

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

covered image

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

$\endgroup$
7
  • $\begingroup$ Welcome to scicomp! I do not know a good solution for you. You might get more and better feedback from this community if you provide a small example sketch of what a good cover would look like. $\endgroup$ – MPIchael Feb 2 at 12:51
  • $\begingroup$ @MPIchael: added an example $\endgroup$ – jwd Feb 2 at 18:35
  • $\begingroup$ are you working on a fixed resolution, or is your signed distance function given analytically? $\endgroup$ – MPIchael Feb 2 at 18:51
  • $\begingroup$ @MPIchael: Well, the SDF is not always a "true" SDF - it might be the result of doing some cheap union/intersect/subtract operations of various primitives. So, the 0 isosurface will be preserved, but the distance value at any point will potentially be an under-estimate. But you can always "ray march" to find the edge from a starting point+direction. $\endgroup$ – jwd Feb 2 at 19:37
  • $\begingroup$ @MPIchael: but to be clear, it is not a pixel grid I'm working with (though I can turn it into one if needed); the SDF is a function, even if it is only an approximation of the true distance. $\endgroup$ – jwd Feb 2 at 19:40
1
$\begingroup$

(I do not claim any optimality, or that I have thought of every detail)

1. Downsample and brute force: You project your black and white map onto a low resolution. On this lower resolution, you may represent any rectangle by two points marking the upper left and lower right corner. If your resolution is low enough, you can iterate through all non-redundant combinations of points, test if they overlap with white areas (i.e. at the enclosed islands), and if not, then you may efficently calculate their area. As you have four rectangles the skaling of the problem will be very bad, but for low resolution you might get away with it.

2. Heuristic: 'growing' rectangles: You pick four locations that lie within the black area. For each of these locations, you 'grow' rectangles outwards until they touch any white area. If you only hit white in x- or y- direction you may still grow into the other one.

You repeat the above process for a large number of seeding points (preferrably in parallel), and then pick the winner. You might also do variations in that you only pick the first point, optimize the corresponding maximally grown rectangle, and then move to the second one etc.

3. Projection : You go to a high resolution grid, and integrate for every row and column, how many black and white pixels there are. In the vertical profile you get for the integration along your rows, and the horizontal profile you get from integrating your columns you can easily determine the maxima, which would be a good place for starting to place (or grow) a rectangle. Then, when you place the second one, you do the same process but take into account the area that you already covered with the first one. You will have to do some corrections for corner cases, but it might save you a lot (numerical) work. I apologize in advance for the following sketch of what i mean:

shitty sketch of horizontal and vertical integrals

As I said, this does not really solve your problem, but might be starting points for constructing a heuristic.

$\endgroup$
1
  • $\begingroup$ Thank you for this, it is useful to me. I probably will have a quadtree over the data (haven't written this part yet), and so maybe starting at "big" black nodes in that tree as seed locations could be good, too, along the lines of your #2. $\endgroup$ – jwd Feb 4 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.