Tiling fixed-size rectangles to cover a given set of points

user_8278700 0
Viewed 596

The problem - given a list of planar points [p_1, ..., p_n] and the dimensions of some rectangle w, h, find the minimal set of rectangles w, h that cover all points (edit - the rectangles are not rotated).

My inital solution was:

  • find the bounding-box of all points
  • divide the width and height of the bounding-box by the w, h of the given rectangle and round the number up to get the number of instances of the rectangle in x and y
  • to further optimize, go through all rectangles and delete the ones that have zero points inside them.

An example in Python:

def tile_rect(points, rect):
    w, h = rect
    xs = [p.x for p in points]
    ys = [p.y for p in points]
    bbox_w = abs(max(xs) - min(xs))
    bbox_h = abs(max(ys) - min(ys))
    n_x, n_y = ceil(bbox_w / w), ceil(bbox_h / h)
    rect_xs = [(min(xs) + n * w for n in range(n_x)]
    rect_ys = [(min(ys) + n * h for n in range(n_y)]
    rects = remove_empty(rect_xs, rect_ys)
    return rects

How can I do better? What algorithm can I use to decrease the number of rectangles?

optimization algorithm python
3 Answers

To discretize the problem for integer programming, observe that given a rectangle we can slide it in the +x and +y directions without decreasing the coverage until the min x and the min y lines both have a point on them. Thus the integer program is just the standard min cover:

minimize sum_R x_R
subject to
for every point p, sum_{R contains p} x_R >= 1
x_R in {0, 1}

where R ranges over all rectangles whose min x is the x of some point and whose min y is the y of some point (not necessarily the same point).

Demo Python:

import random
from ortools.linear_solver import pywraplp

w = 0.1
h = 0.1
points = [(random.random(), random.random()) for _ in range(100)]
rectangles = [(x, y) for (x, _) in points for (_, y) in points]
solver = pywraplp.Solver.CreateSolver("min cover", "SCIP")
objective = solver.Objective()
constraints = [solver.RowConstraint(1, pywraplp.inf, str(p)) for p in points]
variables = [solver.BoolVar(str(r)) for r in rectangles]
for (x, y), var in zip(rectangles, variables):
    objective.SetCoefficient(var, 1)
    for (px, py), con in zip(points, constraints):
        if x <= px <= x + w and y <= py <= y + h:
            con.SetCoefficient(var, 1)
solver.Objective().SetMinimization()
solver.Solve()

scale = 6 * 72
margin = 72
print(
    '<svg width="{}" height="{}">'.format(
        margin + scale + margin, margin + scale + margin
    )
)
print(
    '<text x="{}" y="{}">{} rectangles</text>'.format(
        margin // 2, margin // 2, round(objective.Value())
    )
)
for x, y in points:
    print(
        '<circle cx="{}" cy="{}" r="3" fill="none" stroke="black"/>'.format(
            margin + x * scale, margin + y * scale
        )
    )
for (x, y), var in zip(rectangles, variables):
    if var.solution_value():
        print(
            '<rect x="{}" y="{}" width="{}" height="{}" fill="none" stroke="rgb({},{},{})"/>'.format(
                margin + x * scale,
                margin + y * scale,
                w * scale,
                h * scale,
                random.randrange(192),
                random.randrange(192),
                random.randrange(192),
            )
        )
print("</svg>")

Example output:

enter image description here

user_21446690

Assuming an approximate, rather than optimal solution is acceptable, how about a routine generally like:

Until no points are left:
  (1) Find the convex hull of the remaining points.
  (2) Cover each point/s on the hull so the
      covering rectangles extend "inward."
      (Perhaps examine neighbouring hull points
      to see if a rectangle can cover more than one.)
  (3) Remove the newly covered points.

Clearly, the orientation of the covering rectangles has an effect on the procedure and result. I think there is a way to combine (1) and (3), or possibly rely on a nested convex hull, but I don't have too much experience with those.

user_20347870

This is can be transformed into a mostly standard set cover problem. The general steps are as follows, given n points in the plane.

  • First, generate all possible maximally inclusive rectangles, of which there are at most n^2, named R. The key insight is that given a point p1 with coordinates (x1, y1), use x1 as the leftmost bound for a set of rectangles. For all other points p2 with (x2,y2) where x1 <= x2 <= x1+w and where y1-h <= y2 <= y1+h, generate a rectangle ((x1, y2), (x1+w, y2+h)).
  • For each rectangle r generated, count the points included in that rectangle cover(r).
  • Choose a subset of the rectangles R, s, such that all points are in Union(r in s) cover(r)

Now, the tricky part is that last step. Fortunately, it is a standard problem and there are many algorithms suggested in the literature. For example, combinatorial optimization solvers (such as SAT solvers, MIP solvers, and Constraint programming solvers) can be used.

Note that the above re-formulation only works if it is ok for rectangles to cover each other. It might be the case that the generated set of rectangles is not enough to find the least set of rectangles that do not overlap.

user_339650
Related