By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,276 Members | 2,063 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,276 IT Pros & Developers. It's quick & easy.

Need suggestion on data structure

P: n/a
Hi:

I'd like to implement a simple map, which is a 2-D plane with many
points, e.g., 100. The points are not evenly distributed, i.e., some
points may have two neighbor points; some may have 5 or 6 neighbor
points. Could anyone suggest me a data structure for it.

Thanks in advance.

John
Jul 22 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a
"John" <jo*********@yahoo.com> wrote:
I'd like to implement a simple map, which is a 2-D plane with many
points, e.g., 100. The points are not evenly distributed, i.e., some
points may have two neighbor points; some may have 5 or 6 neighbor
points. Could anyone suggest me a data structure for it.


I assume you mean "map" as in geography, rather than std::map (STL) ...

What is the map going to be used for (what operations will be required ?)

Using the word "neighbours" sounds like it is a grid with integral
coordinates (like a bitmap), as opposed to arbitrary floating point
coordinates - is that right ?

David F
Jul 22 '05 #2

P: n/a
"David Fisher" <no****@nospam.nospam.nospam> wrote in message news:<gN***************@nasal.pacific.net.au>...
"John" <jo*********@yahoo.com> wrote:
I'd like to implement a simple map, which is a 2-D plane with many
points, e.g., 100. The points are not evenly distributed, i.e., some
points may have two neighbor points; some may have 5 or 6 neighbor
points. Could anyone suggest me a data structure for it.


I assume you mean "map" as in geography, rather than std::map (STL) ...

What is the map going to be used for (what operations will be required ?)

Using the word "neighbours" sounds like it is a grid with integral
coordinates (like a bitmap), as opposed to arbitrary floating point
coordinates - is that right ?

David F


Thanks.
Yes. It is a geographic map, a 2-D plane with many points. Each point
has coordinates, (x,y). But the points are not evenly distributed. So
it is not a uniform grid. The operations are: insertion( add new
points), deletion( remove existing points), lookup( given a point,
output its coordinates), and searching (given a point, ouput its
neighbor points). Hope I have clearly described the problem. Any
suggestion is appreciated.

John
Jul 22 '05 #3

P: n/a
"John" <jo*********@yahoo.com> wrote:
I assume you mean "map" as in geography, rather than std::map (STL) ...

What is the map going to be used for (what operations will be required ?)
Using the word "neighbours" sounds like it is a grid with integral
coordinates (like a bitmap), as opposed to arbitrary floating point
coordinates - is that right ?

David F


Thanks.
Yes. It is a geographic map, a 2-D plane with many points. Each point
has coordinates, (x,y). But the points are not evenly distributed. So
it is not a uniform grid. The operations are: insertion( add new
points), deletion( remove existing points), lookup( given a point,
output its coordinates), and searching (given a point, ouput its
neighbor points). Hope I have clearly described the problem. Any
suggestion is appreciated.


I am still not clear on "neighbour points" in this context - does this mean,
all points within a certain radius ?

There are a few different data structures which might be useful (probably
off topic now :-o ):

- a 2D grid of "bins" (a list of points for each grid cell), similar to a
hash table - point x, y maps to bin[x / CELL_SIZE][y / CELL_SIZE]. To search
for points near point P, iterate through the points in P's bin and the 8
adjacent bins (assuming you are only interesting in points within a distance
of CELL_SIZE from P)
- Quad Trees are a great recursive data structure for uneven distributions
of points ("bins" are only good for reasonably scattered distributions).
These are like a binary tree in two dimensions (with four children instead
of two)
- search for "spatial data structures" with google for others

Hope this is helpful,

David F
Jul 22 '05 #4

P: n/a
"David Fisher" <no****@nospam.nospam.nospam> wrote in message news:<SI***************@nasal.pacific.net.au>...
"John" <jo*********@yahoo.com> wrote:
I assume you mean "map" as in geography, rather than std::map (STL) ...

What is the map going to be used for (what operations will be required ?)
Using the word "neighbours" sounds like it is a grid with integral
coordinates (like a bitmap), as opposed to arbitrary floating point
coordinates - is that right ?

David F


Thanks.
Yes. It is a geographic map, a 2-D plane with many points. Each point
has coordinates, (x,y). But the points are not evenly distributed. So
it is not a uniform grid. The operations are: insertion( add new
points), deletion( remove existing points), lookup( given a point,
output its coordinates), and searching (given a point, ouput its
neighbor points). Hope I have clearly described the problem. Any
suggestion is appreciated.


I am still not clear on "neighbour points" in this context - does this mean,
all points within a certain radius ?

There are a few different data structures which might be useful (probably
off topic now :-o ):

- a 2D grid of "bins" (a list of points for each grid cell), similar to a
hash table - point x, y maps to bin[x / CELL_SIZE][y / CELL_SIZE]. To search
for points near point P, iterate through the points in P's bin and the 8
adjacent bins (assuming you are only interesting in points within a distance
of CELL_SIZE from P)
- Quad Trees are a great recursive data structure for uneven distributions
of points ("bins" are only good for reasonably scattered distributions).
These are like a binary tree in two dimensions (with four children instead
of two)
- search for "spatial data structures" with google for others

Hope this is helpful,

David F


Hi David:
Thanks a lot.

|---------------------------------------|
| |
| b* |
| * * * |
| |
| * 1* 2* |
| |
| 4* P* 3* |
| |
| * 5* 6* |
| |
| * * c* * |
| |
| * * * |
|---------------------------------------|

I use the figure above to clarify the meaning of "neighbor". The above
figure is a 2-D plane. A "*" indicates a point. The neighbors of point
P are 1,2,3,4,5,and 6, but not b and c, since points b and c are too
far from P. So I may specify a radius.
To make the problem easier, I only need two operations: lookup( given
a point,
output its coordinates), and searching (given a point, ouput its
neighbor points). I think that insertion and deletion may be too
difficult, since points change. Any suggestion is appreciated.

John
Jul 22 '05 #5

P: n/a
John wrote:


Hi David:
Thanks a lot.

|---------------------------------------|
| |
| b* |
| * * * |
| |
| * 1* 2* |
| |
| 4* P* 3* |
| |
| * 5* 6* |
| |
| * * c* * |
| |
| * * * |
|---------------------------------------|

I use the figure above to clarify the meaning of "neighbor". The above
figure is a 2-D plane. A "*" indicates a point. The neighbors of point
P are 1,2,3,4,5,and 6, but not b and c, since points b and c are too
far from P. So I may specify a radius.
To make the problem easier, I only need two operations: lookup( given
a point,
output its coordinates), and searching (given a point, ouput its
neighbor points). I think that insertion and deletion may be too
difficult, since points change. Any suggestion is appreciated.


One more thing: Is the number of points fixed or does it change a lot
(during one program run). The reason is: It's easy to come up with
a data structure that simply stores the neighborhood information for
a point. You create it once (and update it if necc.) and
simply use that instead of scanning the neighborhood each time you
need that information. If the points stay constant during a program run,
this is probably the fastest thing.
If on the other hand the points are constantly moving you need a more dynamic
approach.

--
Karl Heinz Buchegger
kb******@gascad.at
Jul 22 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.