c++ - 计算相邻盒子的数量

Question

假设我有一组 1000 个框的 (X,Y) 坐标。

         (    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++ 计算每个相邻框的数量。我该怎么做？

示例

在这张图片中，box-7 的相邻框总数为 6，box-3 为 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，它显示-

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，它显示-

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]