寻找最近的可用空间而不与现有点发生碰撞

Question

给定一组点，我正在寻找如何高效地找到给定宽度和高度（由红色框表示）的最近可用空间到指定点（本例中为点4）的想法。

也给出了另一组点（如下所示），其中箱子不能紧贴点4，我仍然希望找到最近的空间（如图所示）。我通过点4和红色框中心之间的距离来判断“最近”。

任何帮助或想法将不胜感激。

- Ben

---

如果你以相同大小的实心矩形，并以每个点为中心绘制填充矩形，则所有未着色区域都是矩形中心的有效位置。因此，你可以在形状边界周围走动（可能会有空洞），其中一个点必须是最佳选择。 - maraca

Answer 1

解决此问题的关键是考虑每个点将空间分为四个（重叠的）半平面：北、南、西或东。

首先考虑参考点，矩形必须在它的北部或南部等位置，换句话说，在上述定义的任一半平面中。

让我们把这些半平面看作轴对齐的矩形，它们可能有一些边界处于无限状态。

现在，对于每个边界矩形，尝试将目标矩形放置在最靠近参考点的位置内。如果与任何点碰撞，请在该点处将边界矩形分成四个新的边界矩形并重复进行操作。

因此，总结如下：

1）保持边界矩形队列，按其到参考点的距离排序。

2）获取第一个元素，查看是否可以将矩形放入其中，放在最靠近参考点的位置。如果可以，则问题得以解决。

3）否则，在任何碰撞点处划分边界矩形，并将结果的四个边界矩形推入队列中（过滤掉太小的那些）。

4）重复进行操作。

- salva