Need suggestion on data structure

[John]

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

 

[David Fisher]

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

 

[John]

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

 

[David Fisher]

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

 

[John]

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

 

[Karl Heinz Buchegger]

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.