Algorithm ..to find nearest Neighboring Rectangles ..in all 4 directions

Question

Which Spatial Search Algorithm..would help in querying the nearest neighboring rectangle ..for a Given Rectangle ..in all 4 directions(ie Top ,Left,Bottom ,Right).

1: The distance is orthogonal from one side of the rectangle..to the opposite side of the other rect.

2: Rectangles actually represent GUI components on a form.

Answer 1

Doing it OOP style in java, assuming axis that start from lower left corner and increasing:

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;
  }
}

So now you have an object that instantiated with a rectangle calculates the minimal and maximals spans of the rectangle, this Displacement object is able to find the minimum distance with another Displacement thanks to minDistance(...)

Now you can easily do something like that:

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;
  }
}

I wrote it in Java just to give a quick example but the approach can be the same in every language..

you can easily treat every direction in a different way by splitting the way you calculate distance over different cartinal directions, so you can do the same work I did in previous snippet but splitted for every axis.