1

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:

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

Constraints:

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

Trade-off:

  • 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?

Michael come lately
  • 534
  • 4
  • 18
  • 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 Aug 28 '14 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. – Michael come lately Aug 28 '14 at 16:31

0 Answers0