# Algorithm for dividing a polygon into rectangles?

I have a polygon as a set of coordinates (fex [(0,0), (1,0), etc.). I'd like to find a way to divide this into as few rectangles as possible. The background for this is that I wish to have a user interface where the user can select a specific area on a map (a polygon). The frontend will send the coordinates describing that polygon to a backend server. The backend server will talk to an external API to figure out locations within the polygon that the user drew. The complicating factor for me is that the external API only accepts queries with a rectangle, so I need to translate the polygon into a set of rectangles that covers the area that the user is interested in. The external API is rate limited so I'd like to have as few rectangles as possible.

I've drawn a couple of examples to illustrate what I mean:

As i don't want an infinite number of squares I'm OK with including some area outside of the polygon the user drew (but preferably as little as possible). In the second example I've divided the polygon into 9 squares.

Any ideas for how to approach this?

• In the first example, those are rectangles, not squares. Also if you are ok with covering an area outside the polygon, what prevents you from drawing one big rectangle covering the whole polygon? Nov 25 at 9:49
• Thanks for commenting. I'll edit my question after writing this comment to clarify that it's rectangles I want, not squares. For your second question: I do want as few hits outside of the user polygon as possible (up to some point that makes sense).
– L42
Nov 25 at 9:52
• It sounds to me like you're going to need to quantify the amount of non-polygon area covered by rectangles that you're willing to tolerate, somehow. Nov 25 at 10:11
• To throw out a number I would be happy if the area covered by the rectangles contained the entire polygon, and that the non-polygon area would be a maximum of 10% of the total rectangle area.
– L42
Nov 25 at 10:24
• I just found en.wikipedia.org/wiki/Polygon_covering which gave me some interesting references to read.
– L42
Nov 25 at 14:17