6

假设我有一组 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 !!! （请查看新图片）

我该如何解决？

4

3 回答 3

7

一个简单的解决方案需要 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]
于 2013-06-26T18:52:42.617 回答
1

假设您对 (x0, y0, x1, y1) 坐标为的框 B 感兴趣： (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);

您浏览整个框列表（带有 for 循环），然后选择以下框：

(((ay0 <= by1 && ay1 >= by0) && (ax1 == bx0 || ax0 == bx1) || // touch on x axis
 ((ax0 <= bx1 && ax1 >= bx0) && (ay1 == by0 || ay0 == by1))   // touch on y axis
于 2013-06-26T18:54:21.920 回答
0

在您描述框共享角的场景中，因此如果您计算所有框角，那么您可以看到哪些是接触的

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

可能有一个更有效/优雅的解决方案，这个有点天真。

于 2013-06-26T18:52:55.120 回答