矩形平面中矩形的最近边

Question

我有一个 2D 平面（带有离散点），其中包含任意大小的矩形，并且所有矩形均轴对齐。我有它们的坐标（左上）和尺寸（长度和宽度）。

假设我在这个平面上选择一个矩形，我想找到距离这个矩形最近的边（它也与矩形相邻边的至少一个投影相交）。这是一个例子：

我的第一个解决方案是逐条检查每个矩形的每条边并计算其到给定矩形每条边的距离。但这似乎在计算上非常昂贵（特别是在图形上下文中考虑这一点，即每一帧输入）

其次是检查这个矩形是否与另一个（AABB）碰撞，如果没有，那么通过它们左上角坐标的相对位置，我可以确定哪一个是该对的最接近的边缘。

有人可以提出更好的解决方案吗？

注 1：您可以假设除了给定的矩形之外，没有其他矩形可以相交（与任何其他矩形）。

Answer 1

我会首先找到碰撞的矩形，然后找到最接近的矩形。这是一个应该有效的算法：

array[N,4] # N rectangles, with X coordinate, Y coordinate, width and heigth
distance = inf # Initialize distance with high value    
i = chosenRectangle
closest = 0 # Initialize index of closest rectangle

# Vertical colliding
for j=1,N
    if (i/=j) and (array[j,1] > array[i,1] - array[j,3]) and (array[j,1] < array[i,1] + array[i,3]) then
        evaluate distanceTemp # Distance between rectangles i and j
        if distanceTemp < distance then
            distance = distanceTemp 
            closest = j
        end if
    end if
end for

# Same for horizontal colliding, without reinitialization