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

Question

给定一组点,我正在寻找有关如何有效地找到给定宽度和高度(由红色框表示)到指定点(本例中的点4)的最近可用空间的想法.

还给出了一组不同的点(如下所示),其中盒子不能紧靠第4点,我仍然希望找到最近的空间(如图所示).我判断点4与红框中心之间的距离"最接近".

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

Answer 1

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

首先考虑参考点，矩形必须位于其北部或南部等，或者换句话说，位于上面定义的半平面之一中。

让我们将它们视为轴对齐的矩形，而不是半平面，这些矩形可能具有无限的某些边。

现在，对于每一个边界矩形，尝试将目标矩形放置在其中距离参考点最近的位置。如果它与任何点碰撞，则将该点的边界矩形分成四个新的边界矩形并重复。

所以，总而言之：

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

2）获取第一个元素，看看是否可以在距离参考点最近的位置放置矩形。如果可以的话，问题就解决了。

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

4）重复。