I am looking for a way to approximate a geographic region with a few bounding boxes. I know I can get a single box to cover the whole region, but some of my shapes are quite strange (gerrymandered, in some cases).

I'd like to know if there's a way to approximate a shape as a (small) collection of axis-aligned rectangles to make a tighter collection of bounding boxes.

For example, I know I can draw a rectangular box around a roughly "C" shaped region, but I can make a much better approximation with 3 rectangles like so:

    |              |
    |    |
    |    |
    | +~~+--------+
    +-+~~+        |


  • The rectangles should contain the entire original shape.
  • It's fine if the rectangles overlap.


  • I'd really like to stay under 10 rectangles. (Maybe an increased penalty for each additional rectangle?)
  • I'd also like to have under 25% of the original shape's area as extraneously included by the rectangles, but if it takes too many shapes to do so, I'll go with fewer shapes.

Is there a recognized method for doing this to arbitrary shapes? To certain classes of shapes?

  • I'm pretty sure you've seen the packing polygons question. The approach--if not the specific method--I described there will work here, provided you make your question a little more precise and quantitative. You need to stipulate how the program should determine the quality of any approximation. I would guess that fewer rectangles are better and that a smaller error (difference in areas) is better, but what is still missing is some indication of how it should trade off between the two objectives. Can you clarify that issue?
    – whuber
    Commented Aug 28, 2014 at 15:50
  • @whuber I have indeed seen that question (nice work!). You identified the trade-off correctly. I've updated the question, but I have a hard time conceptualizing the results of any quantitative weighting algorithm I've tried to invent in the last half hour. Commented Aug 28, 2014 at 16:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.