algorithm - 算法..找到最近的相邻矩形..在所有 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对象能够找到与另一个对象的最小距离，Displacement这要归功于minDistance(...)

现在您可以轻松地执行以下操作：

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 编写它只是为了举一个简单的例子，但是每种语言的方法都可以相同..

您可以通过将计算距离的方式拆分为不同的主要方向来轻松地以不同的方式处理每个方向，因此您可以执行我在上一个片段中所做的相同工作，但针对每个轴进行拆分。