How to approximately cover a (non necessarily convex) polygon with equal non-overlapping squares in python?

Question

I couldn't come up with a well defined optimization objective for what I want, but hopefully I can pass my subjective feeling of what I want through some examples.

The squares always have the same size (e.g., 1000x1000). The polygons may have different sizes. Sometimes the polygons may be big enough for one or more squares to fit inside it, other times the polygon may be small enough that it can be fit inside the square. In the later case one square should be centered at the centroid of the polygon. In the former case one or more non-overlapping squares should cover more or less the polygon. It is fine to not cover the whole area of the polygon. For example, if you need to put a square near the border to cover a small remaining uncovered area then you shouldn't, because most part of the square would be outside the polygon and you would be spending one square for a small increase in the covered area.

Examples with the more or less the expected solution:

Small polygon:

Big polygon:

Note that in the small polygon case it is fine for a lot of square's area be wasted, because we need at least one square. But in the big polygon case it is not fine for a lot of the square's area be wasted.

I know my specs are ill defined, but I hope someone can guess what I want and maybe can define the objective better.

If one could show some code in python to solve it would be great. If you use shapely it will be even better, but it is not required.

The polygon is defined by a list of points (x,y) that are connected in the order that they appear in the list.

Thanks!

Edit: The squares shouldn't be rotated.

At a certain point you're going to have to define a clear rule for how much of a polygon can stick out from under the squares, like a maximum area, or a maximum percentage of the square or polygon's area, or a maximum distance a point can be away from the covered area, or maybe a ratio between the polygon's area and the combined area of the squares covering it. — m69 says ''Пу́тин хуйло́''
This old question has some interesting ideas and links: stackoverflow.com/questions/3516044/… — m69 says ''Пу́тин хуйло́''

Michael Michael · Accepted Answer · 2021-09-22T15:39:09

This will generate a cover of the polygon poly.

import numpy as np
from shapely.geometry import MultiPoint, MultiPolygon, Polygon

def square(x, y, s):
    return Polygon([(x, y), (x+s, y), (x+s, y+s), (x, y+s)])

poly = MultiPoint(np.random.randn(10,2)).convex_hull
grid_size = 0.5
ibounds = np.array(poly.bounds)//grid_size
ibounds[2:4] += 1
xmin, ymin, xmax, ymax = ibounds*grid_size
xrg = np.arange(xmin, xmax, grid_size)
yrg = np.arange(ymin, ymax, grid_size)
mp = MultiPolygon([square(x, y, grid_size) for x in xrg for y in yrg])
solution = MultiPolygon(list(filter(poly.intersects, mp)))

How to approximately cover a (non necessarily convex) polygon with equal non-overlapping squares in python?

1 Answers