C++

Forum

 
Adjacent Cell

Cplusc (453)
I have a grid in which every cell build up of 3 nodes. I need to find the neighboring cell of every single cell in the grid. The point is if two cells share the same edge they are adjacent. Based on this strategy I wrote the following code and it's working fine but as you can see it's not an efficient code as in one point i have 4 loops with one if condition. I know this can be done with using something like mapping and set but I can't figure out how. I would be grateful if you could help me with this.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

typedef std::vector<int>         VecInt_t;
typedef std::vector<VecInt_t>    VecVecInt_t;

void elm_adj(VecVecInt_t& connect);
int concat(int a, int b);

int main()
{
	VecVecInt_t Connectivity{ {0,1,3},{1,4,3},{1,5,4},{1,2,5},{3,7,6},{3,4,7},{4,5,7},{5,8,7} };
	elm_adj(Connectivity);
}

int concat(int a, int b)
{
	std::string s1 = std::to_string(a);
	std::string s2 = std::to_string(b);

	std::string s = s1 + s2;
	int c = stoi(s);

	return c;
}

void VecVec_no_duplicates_unique(VecVecInt_t& Vec)
{
	for (size_t i = 0; i < Vec.size(); i++) {
		std::sort(Vec[i].begin(), Vec[i].end());
		Vec[i].erase(std::unique(Vec[i].begin(), Vec[i].end()), Vec[i].end());
	}
}

void elm_adj(VecVecInt_t& connect) {

	VecVecInt_t arr(connect.size());

	for (int i = 0; i < connect.size(); i++) {

		int a = concat(connect[i][0], connect[i][1]);
		int b = concat(connect[i][1], connect[i][0]);
		int c = concat(connect[i][1], connect[i][2]);
		int d = concat(connect[i][2], connect[i][1]);
		int e = concat(connect[i][0], connect[i][2]);
		int f = concat(connect[i][2], connect[i][0]);
		arr[i].push_back(a);
		arr[i].push_back(b);
		arr[i].push_back(c);
		arr[i].push_back(d);
		arr[i].push_back(e);
		arr[i].push_back(f);
	}

	//for (int i = 0; i < arr.size(); i++) {
	//	for (int j = 0; j < arr[i].size(); j++) { // print all string in first vector of 'arr'
	//		std::cout << arr[i][j] << " ";
	//	}
	//	std::cout << std::endl;
	//}

	VecVecInt_t Elm_Adj(connect.size());

	int row = 0;
	int col = 0;

	for (int i = 0; i < arr.size(); i++) {
		for (row = 1; row < connect.size(); row++) {
			for (int j = 0; j < 6; j++) {

				for (col = 0; col < 6; col++) {

					if (arr[i][j] == arr[row][col]) {
						Elm_Adj[i].push_back(i);
						Elm_Adj[i].push_back(row);
					}
				}

			}
		}
	}

	VecVec_no_duplicates_unique(Elm_Adj);

	for (int i = 0; i < Elm_Adj.size(); i++) {
		for (int j = 0; j < Elm_Adj[i].size(); j++) {

			std::cout << Elm_Adj[i][j] << " ";
		}
		std::cout << std::endl;
	}
}

Last edited on
jonnin (11340)
you just need a map of cell1 and cell2 identification and a true / false whether they are touching or not as a lookup table. Then its just one operation to check it. This assumes that the structure can't change -- the the blocks move around you have to figure it out... and whether you return true or false if someone puts the same cell in twice.
Last edited on
Cplusc (453)
@jonnin how I can do this?
you just need a map of cell1 and cell2 identification and a true / false 
whether they are touching or not as a lookup table.


Last edited on
jonnin (11340)
bool adjacent[numcells][numcells]{};
then take the output of your slow code and shovel it into there.
say you find that 2 and 3 are adjacent:
-> adjacent[2][3] = true;
and so on.
you can do it from a file, or hard coded, whatever fits your needs.
you can even write a program that populates it that you run one time only, take its output, and put that into the code forever after...
Topic archived. No new replies allowed.