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?