给定一组点，我正在寻找关于如何有效地找到给定宽度和高度(由红色框表示)到指定点(本例中的点 4)的最近可用空间的想法。
还给出了一组不同的点(如下所示)，其中盒子不能紧挨着点 4，我仍然希望找到最近的空间(如图所示)。我根据点 4 和红框中心之间的距离判断“最近”。
任何帮助或想法将不胜感激。
最佳答案
解决这个问题的关键是考虑每个点将空间划分为四个(重叠的)半平面:北、南、西或东。
首先考虑引用点，矩形必须在其北或南等等，或者换句话说，在上面定义的半平面之一中。
代替半平面，让我们将它们视为轴对齐的矩形，这些矩形可能有无限边。
现在，对于这些边界矩形中的每一个，尝试将目标矩形放置在距离引用点最近的位置。如果它与任何点发生碰撞，则将该点的边界矩形划分为四个新的边界矩形并重复。
所以，总结一下:
1) 按照到引用点的距离排序的边界矩形队列。
2) 获取第一个元素，看看是否可以在离引用点最近的位置放置矩形。如果可以，问题就解决了。
3) 否则，在任意一个碰撞点处划分边界矩形并将得到的四个边界矩形插入队列(过滤掉那些太小的)。
4) 重复。
关于javascript - 在不与现有点碰撞的情况下找到最近的可用空间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44474918/