算法..找到最近的相邻矩形..在所有 4 个方向

Question

哪种空间搜索算法..将有助于查询给定矩形..在所有4个方向（即顶部、左侧、底部、右侧）的最近相邻矩形。

1：距离是从矩形的一侧到另一个矩形的相对侧的正交距离。

2：矩形实际上代表表单上的 GUI 组件。

Answer 1

在java中以OOP风格进行操作，假设轴从左下角开始并增加：

class Displacement
{
  float top, bottom, left, right;
  Rectangle r;

  Displacement(Rectangle r)
  {
    this.r = r;

    top = Math.max(r.y1, r.y2);
    bottom = Math.min(r.y1, r.y2);
    left = Math.min(r.x1, r.x2);
    right = Math.max(r.x1, r.x2);
  }

  float minDistance(Displacement d)
  {
    float min = 10000.0f;

    if (Math.abs(top - d.bottom) < min)
      min = Math.abs(top - d.bottom);
    if (Math.abs(bottom - d.top) < min)
      min = Math.abs(bottom - d.top;
    if (Math.abs(left - d.right) < min)
      min = Math.abs(left - d.right);
    if (Math.abs(right - d.left) < min)
      min = Math.abs(right - d.left);

    return min;
  }
}

所以现在你有一个用矩形实例化的对象计算矩形的最小和最大跨度，这个Displacement对象是借助 minDistance(...) 能够找到与另一个 Displacement 的最小距离

现在您可以轻松地执行类似的操作：

class DistanceFinder
{
  ArrayList<Displacement> displs = new ArrayList<Displacement>();

  void addRect(Rectangle r)
  {
    displs.add(new Displacement(r));
  }

  Rectangle findNearest(Rectangle r)
  {
     Displacement current = new Displacement(r);
     Displacement nearest = null;
     float min = 10000.0f

     for (Displacement d : displs)
     {
       float curDist = current.minDistance(d);

       if (curDist < min)
       {
         nearest = d;
         min = curDist;
       }
     }
     return current;
  }
}

我用 Java 编写它只是为了快速提供一个例如，但方法在每种语言中都可以相同..

您可以通过将计算距离的方式拆分为不同的方向，轻松地以不同的方式处理每个方向，这样您就可以执行我在前面的代码片段中所做的相同工作，但拆分为每个轴。