Group the similar boxes

Question

I have a set of (X,Y) coordinates which split a unit square into sub-rectangles. Suppose my coordinates are -

         (    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)

As an example I took only 16 set of data and these coordinates splits my square like this-

Definition of similar box

Those boxes who has the similar number of neighbors are consider as the similar box. For the image above the the box[8], box[13] etc has 4 nearest neighbor. So they are considered as similar boxes.

The image below should make this clear-

::MY PROBLEM::

From the image we can see-

For box[8] the nearest boxes are:

box(1) (which has 4 neighbors)

box[4] (which also has 4 neighbors)

box[14] (has 4 neighbors)

box[16] (has 4 neighbors)

So in this case the sum of the neighbors of nearest boxes = 4+4+4+4 =16

Again for box[13] the nearest boxes are:

box[3] (which has 6 neighbors)

box[5] (which also has 4 neighbors)

box[6] (has 3 neighbors)

box[12] (has 3 neighbors)

So in this case the sum of the neighbors of nearest boxes = 6+4+3+3 =16

And here the total of neighbors for (similar boxes) box[8] and box[13] = 16+16 =32.

Similarly I want to group all the boxes which have 4 neighbors and find the sum of the neighbors of their nearest boxes. And continue for each similar groups.

My Code

Here is my code.

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

It gives the correct result like this-

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  

Although it can identify the nearest boxes and count the number of neighbors but I could not figure out how can I group the similar boxes (as stated above) and find the sum.

And I am stuck here. Can anyone help me?

Updated Code Snippet

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

Gives me the error-

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>&)’

How can I fix it?

Answer 1

Rather then trying to maintain relationship between rectangles in some data structures, it might be a better idea to make rectangle object itself smart and aware of number of it neighbors and who they are.

For example (incomplete proptotype to illustrate idea):

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

With such rect class you can add neighbors to each rectangle, retrieve its own all neighbors of each rect, and all of their neighbors - all relationships are maintained within rect itself rather then some external object, code of main program should be very minimal.

Once you populate rects, you can simply iterate though them, pick ones having required number of neighbors, and do whatever operation on them.

Answer 2

I guess if you want to drastically simplify all of this you can use Mr. Kobelevskiy's recommendation:

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

using namespace std;

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

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

~Rect()
{
};

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
std::vector<Rect*> neighbors;

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

};

vector<Rect*> rects;

void CalculateAdjacentsForRect(unsigned int rects_element){

    for (unsigned int x = 0; x < rects.size(); x++) {
        if (rects[rects_element]->isAdjacent(rects[x])) {
            if (x==rects_element) {
                continue; //this is our box , so do not count it.
            }
            rects[rects_element]->addNeighbor(rects[x]);
        }
    }
}

const int MAX_ADJACENT_RECTS = 10;

int main() {

                    //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));

    for (unsigned int i = 0; i < rects.size(); i++)
    {
        CalculateAdjacentsForRect(i);
    }

    for (unsigned int i = 0; i < rects.size(); i++)
    {
        cout << "\nRect" << i << " has a neighbor sum of " << rects[i]->sumOfNeighbors();
    }

    cout << "\n";

    for (int ix = 0; ix < MAX_ADJACENT_RECTS; ix++)
    {
        int num_rects_with_this_num_of_adjacents = 0;
        int num_adjacents_total_for_similar_rects = 0;
        for (unsigned int i = 0; i < rects.size(); i++) {
            if ( rects[i]->numNeighbors() == ix ) {
               num_rects_with_this_num_of_adjacents++;
               num_adjacents_total_for_similar_rects += rects[i]->sumOfNeighbors();
            }
        }
        cout << "\nThere are " << num_rects_with_this_num_of_adjacents << " rects with " << ix << " adjacent rects. They have a cum neighbor sum of " << num_adjacents_total_for_similar_rects;
    }

    return 0;
}