P: n/a

Hi:
I'd like to implement a simple map, which is a 2D 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  
Share this Question
P: n/a

"John" <jo*********@yahoo.com> wrote: I'd like to implement a simple map, which is a 2D 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  
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 2D 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 2D 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  
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 2D 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  
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 2D 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 2D 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  
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 2D 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   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 1555
 replies: 5
 date asked: Jul 22 '05
