c++ - 将相似的框分组

Question

我有一组 (X,Y) 坐标，可以将单位正方形分割成子矩形。假设我的坐标是 -

         (    x1,    y1)    (    x2,    y2)      

         (0.0000,0.0000)    (0.3412,0.4175)   
         (0.7445,0.0000)    (1.0000,0.6553)   
         (0.7445,0.6553)    (1.0000,1.0000)   
         (0.0000,0.6553)    (0.7445,1.0000)   
         (0.3412,0.0000)    (0.7445,0.4175)   
         (0.3412,0.4175)    (0.7445,0.6553)   
         (0.0000,0.4175)    (0.3412,0.6553)....etc (total 10,000 coordinates)

举个例子，我只取了 16 组数据，这些坐标像这样分割我的正方形-

相似框的定义

那些具有相似邻居数的框被认为是相似框。对于上面的图像，box[8]、box[13] 等有 4 最近邻。所以它们被认为是相似的盒子。

下图应该很清楚-

::我的问题::

从图中我们可以看出-

对于 box[8] 最近的框是:

box(1)(有 4 个邻居)

box[4](也有 4 个邻居)

box[14](有 4 个邻居)

box[16](有 4 个邻居)

所以在这种情况下最近的框的邻居之和 = 4+4+4+4 =16

对于 box[13] ，最近的框是:

box[3](有 6 个邻居)

box[5](也有 4 个邻居)

box[6](有 3 个邻居)

box[12](有 3 个邻居)

所以在这种情况下最近的框的邻居之和 = 6+4+3+3 =16

这里(相似框)box[8] 和 box[13] 的邻居总数 = 16+16 =32。

同样，我想将所有具有 4 个邻居的框分组，并找到离它们最近的框的邻居之和。并对每个相似的组继续。

我的代码

这是我的代码。

#include <iostream>
#include <cstdlib>
#include <vector>
#include <stdio.h>

using namespace std;

class Rect {
public:
double x1, x2, y1, y2; // coordinates

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

};



void isNearest(int b){

vector<Rect> rects;     
                //Rect(  x1 ,  y1  ,   x2  ,  y2   ) 
  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 nearBox_count = 0;

  double TotalArea=0;


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

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


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


nearBox_count++;

printf("box[%d] is nearest to box[%d]  \n", (b+1), (x+1));

}
}

printf("Total number of nearest box for [%d] is %d  \n",(b+1),nearBox_count );
printf("\n");

}


int main() {

  for (int i = 0; i < 16; ++i)
  {
    isNearest(i);
  }

return 0;
}

它给出了这样的正确结果-

box[1] is nearest to box[2]  
box[1] is nearest to box[4]  
box[1] is nearest to box[8]  
box[1] is nearest to box[14]  
Total number of nearest box for [1] is 4  

box[2] is nearest to box[1]  
box[2] is nearest to box[3]  
box[2] is nearest to box[5]  
box[2] is nearest to box[11]  
Total number of nearest box for [2] is 4  

box[3] is nearest to box[2]  
box[3] is nearest to box[5]  
box[3] is nearest to box[7]  
box[3] is nearest to box[13]  
box[3] is nearest to box[14]  
box[3] is nearest to box[15]  
Total number of nearest box for [3] is 6  

box[4] is nearest to box[1]  
box[4] is nearest to box[8]  
box[4] is nearest to box[10]  
box[4] is nearest to box[16]  
Total number of nearest box for [4] is 4  

box[5] is nearest to box[2]  
box[5] is nearest to box[3]  
box[5] is nearest to box[11]  
box[5] is nearest to box[13]  
Total number of nearest box for [5] is 4  

box[6] is nearest to box[7]  
box[6] is nearest to box[12]  
box[6] is nearest to box[13]  
Total number of nearest box for [6] is 3  

box[7] is nearest to box[3]  
box[7] is nearest to box[6]  
box[7] is nearest to box[9]  
box[7] is nearest to box[15]  
Total number of nearest box for [7] is 4  

box[8] is nearest to box[1]  
box[8] is nearest to box[4]  
box[8] is nearest to box[14]  
box[8] is nearest to box[16]  
Total number of nearest box for [8] is 4  

box[9] is nearest to box[7]  
box[9] is nearest to box[10]  
box[9] is nearest to box[15]  
box[9] is nearest to box[16]  
Total number of nearest box for [9] is 4  

box[10] is nearest to box[4]  
box[10] is nearest to box[9]  
Total number of nearest box for [10] is 2  

box[11] is nearest to box[2]  
box[11] is nearest to box[5]  
box[11] is nearest to box[12]  
Total number of nearest box for [11] is 3  

box[12] is nearest to box[6]  
box[12] is nearest to box[11]  
box[12] is nearest to box[13]  
Total number of nearest box for [12] is 3  

box[13] is nearest to box[3]  
box[13] is nearest to box[5]  
box[13] is nearest to box[6]  
box[13] is nearest to box[12]  
Total number of nearest box for [13] is 4  

box[14] is nearest to box[1]  
box[14] is nearest to box[3]  
box[14] is nearest to box[8]  
box[14] is nearest to box[15]  
Total number of nearest box for [14] is 4  

box[15] is nearest to box[3]  
box[15] is nearest to box[7]  
box[15] is nearest to box[9]  
box[15] is nearest to box[14]  
box[15] is nearest to box[16]  
Total number of nearest box for [15] is 5  

box[16] is nearest to box[4]  
box[16] is nearest to box[8]  
box[16] is nearest to box[9]  
box[16] is nearest to box[15]  
Total number of nearest box for [16] is 4  

虽然它可以识别最近的盒子并计算邻居的数量，但我无法弄清楚如何将相似的盒子分组(如上所述)并找到总和。

我被困在这里了。谁能帮帮我？

更新的代码片段

vector<CheckRect> rects;

unsigned isNearest(unsigned b, vector<unsigned>& neighbours) {

  unsigned nearBox_count = 0;

  for (unsigned x = 0; x < rects.size(); ++x) {
    if (rects[b].isAdjacent(rects[x])) {
      if (x==b) continue; //this is our box , so do not count it.
      nearBox_count++;
      printf("box[%d] is nearest to box[%d]  \n", (b+1), (x+1));
      neighbours.push_back(x);
    }
  }

  printf("Total number of nearest box for [%d] is %d  \n",
        (b+1), nearBox_count );
  printf("\n");

  return nearBox_count;
}

int main(){

cin>>N;

for(int b=0; b<N; b++){

  ifstream inputFile1("RectCoordinates.txt"); //input from the file previously generated
  int rect_number;
  double xa0,ya0,xa1,ya1;
  int neighbours;
  isNearest( b, &neighbours);// This is the line that causing my ERROR


  }
 vector<unsigned> nearBox_count(rects.size());
  vector< vector<unsigned> > neighbours(rects.size());
  for (unsigned i = 0; i < rects.size(); ++i) {
    nearBox_count[i] = isNearest(i, neighbours[i]);
  }

  // Calculate the sums of neighbouring boxes
  vector<unsigned> neighCount(rects.size(), 0);
  for (unsigned i = 0; i < rects.size(); i++) {
    for (unsigned j = 0; j < neighbours[i].size(); j++) {
      neighCount[i] += nearBox_count[neighbours[i][j]];
    }
  }

  // Calculate your result
  map<unsigned,unsigned> finalCount;
  for (unsigned i = 0; i < rects.size(); i++)
  {
    if (finalCount.count(nearBox_count[i]) == 0)
      finalCount[nearBox_count[i]] = neighCount[i];
    else
      finalCount[nearBox_count[i]] += neighCount[i];
  }

  // Print the result
  for (map<unsigned,unsigned>::iterator it = finalCount.begin();
        it != finalCount.end(); ++it) {
    printf("Sum neighbours for the neighbours of similar boxes with %d "
           "neighbours is %d\n", it->first, it->second);
  }

  return 0;
}

给我错误-

ss.cpp: In function ‘int main()’:
ss.cpp:102:29: error: invalid initialization of reference of type ‘std::vector<unsigned int>&’ from expression of type ‘unsigned int’
ss.cpp:22:10: error: in passing argument 2 of ‘unsigned int isNearest(unsigned int, std::vector<unsigned int>&)’

我该如何解决？

Answer 1

与其尝试在某些数据结构中维护矩形之间的关系，不如让矩形对象本身变得智能并了解它的邻居数量以及它们是谁可能是一个更好的主意。

例如(用于说明想法的不完整原型(prototype)):

class Rect {
public:
//methods
Rect(double X1, double Y1, double X2, double Y2);

//const access
double getX1() const;
double getX2() const;
double getY1() const;
double getY2() const;

int numNeighbors() const { return neighbors.size();}
int sumOfNeighbors() const { int res(0); for(size_t i=0;i< neighbors.size();++i) res += neighbors[i]->numNeighbors(); return res;}
std::vector<Rect*> getNeighbors() {return neighbors};

void addNeighbor(Rect* newNeighbor) {neighbors.push_back(newNeighbor);}

//data
private:

double x1, x2, y1, y2; // coordinates
std::vector<Rect*> neighbors;
};

有了这样的 rect 类，你可以为每个矩形添加邻居，检索它自己的每个 rect 的所有邻居，以及它们的所有邻居 - 所有关系都在 rect 本身而不是一些外部对象中维护，主程序的代码应该非常最小。

填充矩形后，您可以简单地遍历它们，选择具有所需邻居数量的矩形，并对它们执行任何操作。