algorithm - 在具有图元(圆形、四边形)的二维空间中为任意点 [x,y] 查找对象的最近自由位置

Question

我有一个 2D 空间，其中包含任意数量的对象(它们是圆形或四边形 - 这无关紧要)，在每个时间刻度中具有不同的大小和不同的位置。我想为任何基元(示例图片中的绿色圆圈)找到一个 y 位置，使其不与任何其他对象相交。

请看这张图片以更好地理解:

我想找到一种快速(!)算法，可以处理具有任意排列的任意数量对象的复杂情况。

如果有任何算法、建议、想法等，我将不胜感激。

更新:对象的顺序是随机的，即对象 N+1 并不总是在对象 N 的顶部或右侧。所有对象的大小和位置都是随机的——它们不在严格的网格中。

Answer 1

沿 x 轴运行扫描线算法并使用 y 轴上的树跟踪对象。

这个想法是为 x 轴生成一个“事件”列表。事件是当你遇到一个对象或当你摆脱一个对象。如果您使用的圆将是 centerX + radius 和 centerX - radius。您对这些事件进行排序。这个想法是，在这些点之间你可以假设没有什么大的变化。是的，边缘会移动一点，但您可以轻松地适应它。

现在您将沿 y 轴保留边缘的间隔树。当您遇到新对象时，您会在树中标记间隔(O(logN) 操作)。当您到达对象的末尾时，您将间隔标记为空闲。然后您尝试为您的对象找到一个足够大的间隔(同样是 O(logN))。

如果您想要更细粒度的值(假设您希望您的圆在经过另一个圆时具有圆形路径)，您将需要进行一些插值。基本上，您知道标记内容的边缘在哪里，将其追踪回标记它的对象并计算调整(基本上是交点)。

当您的对象是一条线时，这非常有效，因为您不会跟踪对象前后的可用空间。为了使其正常工作，在障碍物周围添加一层脂肪。例如，在你的演示中，圆圈使障碍物的圆角随着你的拟合圆的半径而增加。如果您使用四边形，则使用您尝试拟合的四边形或圆形的尺寸扩展四边形。