python - 平铺固定大小的矩形以覆盖给定的一组点

Question

问题 - 给定平面点列表 [p_1, ..., p_n]和一些矩形的尺寸 w, h ，求最小矩形集 w, h覆盖所有点(编辑 - 矩形不旋转)。
我最初的解决方案是:

找到所有点的边界框

将边界框的宽度和高度除以 w, h给定矩形的数量并将数字向上取整以获得 x 中矩形的实例数和 y

要进一步优化，请遍历所有矩形并删除其中包含零点的矩形。

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

我怎样才能做得更好？我可以使用什么算法来减少矩形的数量？

Answer 1

为了离散整数规划的问题，观察给定一个矩形，我们可以在 +x 和 +y 方向上滑动它，而不会减少覆盖范围，直到最小 x 和最小 y 线上都有一个点。因此整数程序只是标准的最小覆盖:

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

哪里 R范围覆盖所有矩形，其最小 x 是某个点的 x，其最小 y 是某个点的 y(不一定是同一点)。
演示 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>")

示例输出: