c++ - 搜索具有最小矩形长度和的一组点。算法是什么？

Question

美好的一天。

我的任务是在 2D 空间中找到到矩形的距离总和最小的一组点。例如，对于两个矩形，结果将是下一个区域 ( picture )。该区域中的任何点都具有 A 和 B 矩形的最小长度之和。哪种算法适合寻找一个区域，其中所有点的长度和都最小？矩形的数量可以不同，它们是随机放置的。它们甚至可以相互重叠。矩形的边与坐标轴平行，不能旋转。 区域必须是矩形或线或点。

Answer 1

提示:

矩形的距离图(将任意点 (x,y) 映射到距矩形最近距离的函数)由四个斜面(斜率 45°)、四个四分之一的圆锥体和矩形本身组成，在地面上，形成一个连续的表面。

要获得全局距离图，“足以”对各个矩形的距离图求和。将产生一个相当复杂的表面。根据几何形状，最小值可能在单个顶点、整个边或整个面上实现。

全局 map 的构建似乎比line arrangement 更难，由于圆锥补丁。在一般情况下这是一个非常困难的问题，尽管轴对齐约束可能会缓解它。