Подсчитайте количество соседних ящиков

Наивное решение требует O (N ^ 2), где N — номер прямоугольника, вот как это сделать быстрее.

Два прямоугольника являются смежными, только если они имеют одну общую координату (обратите внимание, что обратное неверно). Поэтому вы можете посчитать количество смежных блоков быстрее, сначала разбив входные прямоугольники, используя два хэша, один из которых основан на расположении прямоугольника по оси x, а другой — по положению у. В результате один прямоугольник поместится в четыре разных хэш-сегмента в зависимости от его x1, y1, x2 и y2.

пример

Например, прямой (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.0000)    (0.3412,0.4175)
(0.0000,0.4175)    (0.3412,0.6553)
(0.0000,0.6553)    (0.7445,1.0000)
(0.0000,0.4175)    (0.3412,0.6553)

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

Сложность времени

Шаг хеширования требует только времени вычисления O (N), где N — количество прямоугольников, а в результате проверки требуется O (m ^ 2), где m — размер самого большого сегмента, который в большинстве случаев намного меньше N.

Проверка смежности в каждом хешированном сегменте

Затем для всех прямоугольников внутри одного хеша. Проверьте, являются ли два прямоугольника смежными, определив, имеют ли они одинаковое значение x и перекрывающиеся значения в y или наоборот.

Ниже приведен пример проверки, являются ли два прямоугольника смежными:

class Rect {
public:
double x1, x2, y1, 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;
}
}

Runnable Пример

Вот пример кода для проверки смежности:

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

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

Rect(double X1, double Y1, double X2, 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, 9999));
rects.push_back(Rect(0.0000,0.0000, 0.8147,0.1355));
rects.push_back(Rect(0.8147,0.0000, 1.0000,0.1355));
rects.push_back(Rect(0.8147,0.1355, 0.9058,0.8350));
rects.push_back(Rect(0.0000,0.1355, 0.1270,0.9689));
rects.push_back(Rect(0.9058,0.1355, 0.9134,0.2210));

rects.push_back(Rect(0.9058,0.8350, 1.0000,1.0000));
rects.push_back(Rect(0.8147,0.8350, 0.9058,1.0000));
rects.push_back(Rect(0.1270,0.1355, 0.6324,0.3082));
rects.push_back(Rect(0.1270,0.9689, 0.8147,1.0000));
rects.push_back(Rect(0.0000,0.9689, 0.1270,1.0000));

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

rects.push_back(Rect(0.1270,0.3082, 0.6324,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", y, 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]