Sign in to follow this  
gohkgohk

Can i simplify this data structure?

Recommended Posts

I want to store the following lines 4 lines make by 6 points a 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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by jyk
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?


My fd's account got banned..
No..i hv not read your reply
Sorry
help me pls

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

Share this post


Link to post
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 line
multimap<int, CPoint> lineMap;

// A map to store lines connected to a point
multimap<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 1
lineMap.insert(make_pair(1, point1));
lineMap.insert(make_pair(1, point2));
// connect line 1 to point1 and point2
pointMap.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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this