Can i simplify this data structure?

Recommended Posts

I want to store the following lines 4 lines make by 6 points I make two class to define lines and points
class Cliness
{
public:
Cliness(void);
~Cliness(void);
int pt1;  // store the array location of the point which i construct the line
int pt2;  // store another one
};

class Cpointss
{
public:
Cpointss(void);
~Cpointss(void);
int line1;  // store the array location of the line made by this point
int line2; // can be empty if the point only create one line
};


I make two array to store them
std::vector<Cliness>    m_arrayline;
std::vector<Cpointss>    m_arraypoint;


From the above example, i store as the following

m_arrayline[1].pt1 = 1;//line 1 make by point 1 & 2
m_arrayline[1].pt2 = 2;

m_arrayline[2].pt1 = 3;//line 2 make by point 3 & 4
m_arrayline[2].pt2 = 4;

m_arrayline[3].pt1 = 4;//line 3 make by point 4 & 5
m_arrayline[3].pt2 = 5;

m_arrayline[4].pt1 = 5;//line 4 make by point 5 & 6
m_arrayline[4].pt2 = 6;

m_arraypoint[1].line1 = 1;
m_arraypoint[1].line2 = NULL;// point 1 only connect to line1

m_arraypoint[2].line1 = 1;
m_arraypoint[2].line2 = NULL;// point 2 only connect to line1

m_arraypoint[3].line1 = 2;
m_arraypoint[3].line2 = NULL;// point 3 only connect to line2

m_arraypoint[4].line1 = 2;// point 4 connect to both line 2 & 3
m_arraypoint[4].line2 = 3;

m_arraypoint[5].line1 = 3;// point 5 connect to both line 3 & 4
m_arraypoint[5].line2 = 4;

m_arraypoint[6].line1 = 4;
m_arraypoint[6].line2 = NULL;// point 6 only connect to line4


i use this two arrays , because i want to find out which points is used to create a line (from m_arrayline) & find out which line is connected to this point(from m_arraypoint) directly and quickly. By it makes me need to change both arrays if i add a new line on it. How can i simplify it? Thank you

Share on other sites
Um...what happened to your other thread? Did you delete it? (I was under the impression you couldn't delete threads once they'd been replied to.)

I replied to your other thread, but it'd be too much trouble to try to recreate the post. Did you happen to read what I posted earlier?

Share on other sites
Quote:
 Original post by jykUm...what happened to your other thread? Did you delete it? (I was under the impression you couldn't delete threads once they'd been replied to.)I replied to your other thread, but it'd be too much trouble to try to recreate the post. Did you happen to read what I posted earlier?

My fd's account got banned..
Sorry
help me pls

[Edited by - gohkgohk on October 12, 2008 10:16:59 PM]

Share on other sites
It seems to me that you can solve this by using two multimaps instead of two vectors.
// A map to store points in a linemultimap<int, CPoint> lineMap;// A map to store lines connected to a pointmultimap<CPoint, int> pointMap;

The multimaps will allow you to connect as many lines to a point as you wish, and you can also have lines defined by more than two points.

If this approach is suitable for your application depends.
I would say that if every point in your application is connected to at least one line, and if you have a unique name for every line, this approach could serve you well.
Using multimaps is just something I came up with when I read your problem. There may be better ways to solve this out there that I don't know about.

Here is an example of how you could create a line between two points
// insert point1 and point2 into line 1lineMap.insert(make_pair(1, point1));lineMap.insert(make_pair(1, point2));// connect line 1 to point1 and point2pointMap.insert(make_pair(point1, 1));pointMap.insert(make_pair(point2, 1));

In order to use the Point type as a key in a multimap, we have to provide a less-than operator:
struct CPoint{	int x, y;			// The multimap will use this operator internally.	friend bool operator < (const CPoint& lhs, const CPoint& rhs) 	{ 		// If my math skills serve me right this will compare the                // points distances from origo		return sqrt(float(lhs.x * lhs.x + lhs.y * lhs.y)) < sqrt(float(rhs.x * rhs.x + rhs.y * rhs.y)); 	}};

Using these multimaps we can lookup what points is part of a line
void printPointsInLine(int lineNumber){	cout << "Points found in line " << lineNumber << endl;	multimap<int, CPoint>::iterator first = lineMap.find(lineNumber);	if(first != lineMap.end())	{		multimap<int, CPoint>::iterator last = lineMap.upper_bound(lineNumber);		for(;first != last; ++first)		{			cout << first->second.x << ", " << first->second.y << endl;		}	}	cout << endl;}

and what lines is connected to a point
void printLinesConnectedToPoint(const CPoint& point){	cout << "Lines connected to point " << point.x << ", " << point.y << endl;	multimap<CPoint, int>::iterator first = pointMap.find(point);	if(first != pointMap.end())	{		multimap<CPoint, int>::iterator last = pointMap.upper_bound(point);		for(;first != last; ++first)		{			cout << first->second << endl;		}	}	cout << endl;}

Wrapping these two multimaps into an object and write member functions to insert, update and delete lines/points is probably a good idea.

Also note that there is both shortcomings and inefficiencies to this approach, like the fact that points doesn't really belong in any of the maps, and there is no "pool" for all the points. In the example above the points is stored in both the multimaps, which is not exactly memory efficient.

Create an account

Register a new account

• Forum Statistics

• Total Topics
628328
• Total Posts
2982099

• 22
• 9
• 9
• 13
• 11