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

Question

Предположим, что у меня есть набор (X, Y) координат 1000 коробок.

  ( x1, y1) ( x2, y2)  Area 

     (0.0000,0.0000) (0.3412,0.4175) 0.1424 
     (0.7445,0.0000) (1.0000,0.6553) 0.1674 
     (0.7445,0.6553) (1.0000,1.0000) 0.0881 
     (0.0000,0.6553) (0.7445,1.0000) 0.2566 
     (0.3412,0.0000) (0.7445,0.4175) 0.1684 
     (0.3412,0.4175) (0.7445,0.6553) 0.0959 
     (0.0000,0.4175) (0.3412,0.6553) 0.0812 ....etc 

Я хотел бы рассчитать количество смежных ящиков для каждого из них с помощью c/C++. Как мне это сделать?

Пример

В этой картине, общее количество смежных блоков для коробки-7 равно шесть, для коробки-3 равно три. Как я могу считать их с помощью C++?

отредактированные и обновление с новыми значениями

Давайте попробуем для 16 с ценностно

1 0.0000 0.0000  0.8147 0.1355 
2 0.8147 0.0000  1.0000 0.1355 
3 0.8147 0.1355  0.9058 0.8350 
4 0.0000 0.1355  0.1270 0.9689 
5 0.9058 0.1355  0.9134 0.2210 
6 0.9058 0.8350  1.0000 1.0000 
7 0.8147 0.8350  0.9058 1.0000 
8 0.1270 0.1355  0.6324 0.3082 
9 0.1270 0.9689  0.8147 1.0000 
10 0.0000 0.9689  0.1270 1.0000 
11 0.9134 0.1355  1.0000 0.2210 
12 0.9134 0.2210  1.0000 0.8350 
13 0.9058 0.2210  0.9134 0.8350 
14 0.6324 0.1355  0.8147 0.3082 
15 0.6324 0.3082  0.8147 0.9689 
16 0.1270 0.3082  0.6324 0.9689 

Для этих значений единичный квадрат стали, как это изображе-

И обновленный код-

#include <iostream> 
    #include <cstdlib> 
    #include <vector> 

    using namespace std; 

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

     bool isAdjacent(Rect rect) { 

    //for x-axis 
      if (x1 == rect.x2 || x2 == rect.x1) {  
    // 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; 
        } 
    }    
    // for y-axis  

       if (y1 == rect.y2 || y2 == rect.y1) { 
       if (x1 >= rect.x1 && x1 < rect.x2) { 
        return true; 
        } 
        if (x2 > rect.x1 && x2 <= rect.x2) { 
        return true; 
        } 
       } 

       return false; 

    } 
    }; 

int main() { 

     vector<Rect> rects;  

     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 b; 
     cin>>b; 

     for (int x = 0; x < rects.size(); ++x) { 


     if (rects[b].isAdjacent(rects[x])) { 


    if (x==b) { 
     continue; //this is our rectangle , so do not count it. 
    } 


      adj_count++; 
     cout << "rect["<<(b+1)<<"] is adjacent with rect["<<(x+1)<<"]"<<endl; 


    } 
     } 
     cout<<"adjacent count of rect["<<(b+1)<<"] is = "<<adj_count<<endl; 


     return 0; 
    } 

Проблема

Теперь для прямоугольника # 1 это shows-

rect[1] is adjacent with rect[2] 
rect[1] is adjacent with rect[4] 
rect[1] is adjacent with rect[14] 
adjacent count of rect[1] is = 3 

мимо прямоугольника # 8 и 9 & 10 !! (Пожалуйста, проверьте новую картину)

И для прямоугольника # 2 это shows-

rect[2] is adjacent with rect[1] 
rect[2] is adjacent with rect[3] 
rect[2] is adjacent with rect[11] 
adjacent count of rect[2] is = 3 

Он не попадает в прямоугольник # 5 и 7 & 6 !!! (Пожалуйста, ознакомьтесь с новым рисунком)

Как это исправить?

Answer 1

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

Два прямоугольника смежны, только если они имеют одну общую координату (обратите внимание, что обратное неверно). Поэтому вы можете подсчитать количество соседних ящиков быстрее, сначала разбив прямоугольники ввода на два хэша, один на основе местоположения x прямоугольника, а другой на основе местоположения y. В результате один прямоугольник будет вписываться в четыре разных хэш-ведра на основе его x1, y1, 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.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; 
    } 
} 

---

исполняемого Пример

Здесь обеспечивает образец код для проверки смежности:

#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] 

Answer 2

В сценарии вы описываете коробки акций углов, так что если вы вычисляться все углы коробки, то можно увидеть, соприкасались те

// O(n) 
foreach box b { 
    // compute b's other 2 corners and save them 
} 

// 16 * O(n^2) = O(n^2) 
foreach box b { 
    foreach box other { 
     // match if any of b's corners match any of others points 
    } 
} 

Существует, вероятно, гораздо более эффективное/элегантное решение, это несколько наивно.

Answer 3

Допустим, вы заинтересованы в коробке B, для которых (x0, y0, x1, y1) координаты: (B.x0, B.y0, B.x1, B.y1)

Затем с:

ax0 = min(x0,x1); 
ax1 = max(x0,x1); 
ay0 = min(y0,y1); 
ay1 = max(y0,y1); 
bx0 = min(B.x0,B.x1); 
bx1 = max(B.x0,B.x1); 
by0 = min(B.y0,B.y1); 
by1 = max(B.y0,B.y1); 

вы идете через весь список ящиков (с для цикла) и выбрать те, для которых:

(((ay0 <= by1 && ay1 >= by0) && (ax1 == bx0 || ax0 == bx1) || // touch on x axis 
((ax0 <= bx1 && ax1 >= bx0) && (ay1 == by0 || ay0 == by1)) // touch on y axis