Group the similar boxes
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 %dn", 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?
As well as attempt to calculate your value, I have made a few minor changes to your code.
Since all your list indices are never negative and it is likely you will have a very large number of rectangles in the future, I would suggest making all your int s into unsigned . This has the added advantage of suppressing certain compiler warnings about comparing signed and unsigned integers in the code bellow.
The second change I suggest you make is to declare rects only once instead of every time you iterate through isNearest . In the code bellow, I have achieved this by making rects a global variable and creating a separate function to initialise it. By making rects a global variable, you can now replace all your 16 s with rects.size() (reduce any chance of forgetting to change one 16 when you add in your full dataset).
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <map>
#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;
}
};
vector<Rect> 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;
}
void initRects(void) {
//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));
}
void readRects(const string& filename) {
ifstream fpInput(filename.c_str());
double dTemp[4];
while (true) {
for (unsigned i = 0; i < 4; i++) fpInput >> dTemp[i];
if (!fpInput.good()) break;
rects.push_back(Rect(dTemp[0], dTemp[1], dTemp[2], dTemp[3]));
}
fpInput.close();
}
int main() {
// Initialize the vector rects
//initRects();
readRects("RectCoordinates.txt");
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 %dn", it->first, it->second);
}
return 0;
}
Update: The above code can now be used by either specifying the Rect s inside the source file or loaded from an external file. In the modified example above, the input file is RectCoordinates.txt :
0.0000 0.0000 0.8147 0.1355
0.8147 0.0000 1.0000 0.1355
0.8147 0.1355 0.9058 0.8350
0.0000 0.1355 0.1270 0.9689
0.9058 0.1355 0.9134 0.2210
0.9058 0.8350 1.0000 1.0000
0.8147 0.8350 0.9058 1.0000
0.1270 0.1355 0.6324 0.3082
0.1270 0.9689 0.8147 1.0000
0.0000 0.9689 0.1270 1.0000
0.9134 0.1355 1.0000 0.2210
0.9134 0.2210 1.0000 0.8350
0.9058 0.2210 0.9134 0.8350
0.6324 0.1355 0.8147 0.3082
0.6324 0.3082 0.8147 0.9689
0.1270 0.3082 0.6324 0.9689
The above outputs the results:
Sum neighbours for the neighbours of similar boxes with 2 neighbours is 8
Sum neighbours for the neighbours of similar boxes with 3 neighbours is 32
Sum neighbours for the neighbours of similar boxes with 4 neighbours is 165
Sum neighbours for the neighbours of similar boxes with 5 neighbours is 22
Sum neighbours for the neighbours of similar boxes with 6 neighbours is 25
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.
我想如果你想大幅度简化所有这些，你可以使用Kobelevskiy先生的建议：
#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;
}
上一篇: 客户端服务器安装包.NET
下一篇: 分组类似的盒子