440,276 Members | 2,063 Online
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
5 Replies

 P: n/a "John" 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" wrote in message news:... "John" 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" 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" wrote in message news:... "John" 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.