只有两个矩形有一个共同的坐标时才会相邻(注意反面不正确).因此,您可以通过首先使用两个哈希对输入矩形进行分区来更快地计算相邻框的数量,一个基于矩形的x位置,另一个基于y位置.结果,一个矩形将基于其x1,x2和y2适合四个不同的散列桶.

例

例如,将rect(0.0000,0.0000)(0.3412,0.4175)散列到bucketX(0.000),bucketX(0.3412),bucketY(0.0000)和bucketY(0.4175)中.

从OP中的输入,bucketX(0.000)和bucketX(1.000)将具有以下矩形：

bucketX(0.0000):
   (0.0000,0.4175)
   (0.0000,0.6553)
   (0.0000,1.0000)
   (0.0000,0.6553)

bucketX(1.0000):
   (0.7445,0.6553)
   (0.7445,1.0000)

时间复杂性

散列步骤仅需要O(N)计算时间,并且得到的检查需要O(m ^ 2),其中m是最大桶的大小,在大多数情况下小于N.

检查每个散列桶内的邻接

然后,对于同一个哈希桶中的所有矩形.通过确定它们是否具有相同的x值和y中的重叠值来检查两个矩形是否相邻,反之亦然.

以下是检查两个矩形是否相邻的示例：

class Rect {
public:
  double x1,y2; // assuming x1 <= x2 and y1 <= y2

  ...

  bool isAdjacent(Rect rect) {
    if (x1 == rect.x1 || x1 == rect.x2 ||
        x2 == rect.x1 || x2 == rect.x2) {
      // use only < when comparing y1 and rect.y2 avoids sharing only a corner
      if (y1 >= rect.y1 && y1 < rect.y2) {
        return true;
      }
      if (y2 > rect.y1 && y2 <= rect.y2) {
        return true;
      }
      if (rect.y1 >= y1 && rect.y1 < y2) {
        return true;
      }
      if (rect.y2 > y1 && rect.y2 <= y2) {
        return true;
      }
    }
    if (y1 == rect.y1 || y1 == rect.y2 ||
        y2 == rect.y1 || y2 == rect.y2) {
      if (x1 >= rect.x1 && x1 < rect.x2) {
        return true;
      }
      if (x2 > rect.x1 && x2 <= rect.x2) {
        return true;
      }
      if (rect.x1 >= x1 && rect.x1 < x2) {
        return true;
      }
      if (rect.x2 > x1 && rect.x2 <= x2) {
        return true;
      }
    }
    return false;
  }
}

一个可运行的例子

这里提供邻接检查的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <vector>

class Rect {
public:
  double x1,y2; // assuming x1 <= x2 and y1 <= y2

  Rect(double X1,double Y2) {
    if (X1 < X2) {
      x1 = X1; x2 = X2;
    } else {
      x2 = X1; x1 = X2;
    }
    if (Y1 < Y2) {
      y1 = Y1; y2 = Y2;
    } else {
      y2 = Y1; y1 = Y2;
    }
  }

  double area() {
    return (x2 - x1) * (y2 - y1);
  }

  bool isAdjacent(Rect rect) {
    if (x1 == rect.x1 || x1 == rect.x2 ||
        x2 == rect.x1 || x2 == rect.x2) {
      // use only < when comparing y1 and rect.y2 avoids sharing only a corner
      if (y1 >= rect.y1 && y1 < rect.y2) {
        return true;
      }
      if (y2 > rect.y1 && y2 <= rect.y2) {
        return true;
      }
      if (rect.y1 >= y1 && rect.y1 < y2) {
        return true;
      }
      if (rect.y2 > y1 && rect.y2 <= y2) {
        return true;
      }
    }
    if (y1 == rect.y1 || y1 == rect.y2 ||
        y2 == rect.y1 || y2 == rect.y2) {
      if (x1 >= rect.x1 && x1 < rect.x2) {
        return true;
      }
      if (x2 > rect.x1 && x2 <= rect.x2) {
        return true;
      }
      if (rect.x1 >= x1 && rect.x1 < x2) {
        return true;
      }
      if (rect.x2 > x1 && rect.x2 <= x2) {
        return true;
      }
    }
    return false;
  }
};

int main() {

  std::vector<Rect> rects;

  rects.push_back(Rect(9999,9999,9999));
  rects.push_back(Rect(0.0000,0.1355));
  rects.push_back(Rect(0.8147,0.8350));
  rects.push_back(Rect(0.0000,0.9689));
  rects.push_back(Rect(0.9058,0.2210));

  rects.push_back(Rect(0.9058,1.0000));
  rects.push_back(Rect(0.8147,1.0000));
  rects.push_back(Rect(0.1270,0.3082));
  rects.push_back(Rect(0.1270,1.0000));
  rects.push_back(Rect(0.0000,1.0000));

  rects.push_back(Rect(0.9134,0.2210));
  rects.push_back(Rect(0.9134,0.8350));
  rects.push_back(Rect(0.9058,0.8350));
  rects.push_back(Rect(0.6324,0.3082));
  rects.push_back(Rect(0.6324,0.9689));

  rects.push_back(Rect(0.1270,0.9689));


  int adj_count = 0;
  int y = 1;
  for (int x = 0; x < rects.size(); ++x) {
    if (x == y) continue;
    if (rects[y].isAdjacent(rects[x])) {
      printf("rect[%d] is adjacent with rect[%d]\n",y,x);
    }
  }
  y = 2;
  for (int x = 0; x < rects.size(); ++x) {
    if (x == y) continue;
    if (rects[y].isAdjacent(rects[x])) {
      printf("rect[%d] is adjacent with rect[%d]\n",x);
    }
  }
}

输出是：

rect[1] is adjacent with rect[2]
rect[1] is adjacent with rect[4]
rect[1] is adjacent with rect[8]
rect[1] is adjacent with rect[14]
rect[2] is adjacent with rect[1]
rect[2] is adjacent with rect[3]
rect[2] is adjacent with rect[5]
rect[2] is adjacent with rect[11]