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]

Re: Need suggestion on data structure

"John" <johnw822003@ya hoo.com> wrote:
[color=blue]
> 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.[/color]

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]

Re: Need suggestion on data structure

"David Fisher" <nospam@nospam. nospam.nospam> wrote in message news:<gNCPb.21$ KS1.2706@nasal. pacific.net.au> ...[color=blue]
> "John" <johnw822003@ya hoo.com> wrote:
>[color=green]
> > 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.[/color]
>
> 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[/color]

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]

Re: Need suggestion on data structure

"John" <johnw822003@ya hoo.com> wrote:
[color=blue][color=green]
> > 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[/color][/color]
?)[color=blue][color=green]
> >
> > 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[/color]
>
> 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.[/color]

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]

Re: Need suggestion on data structure

"David Fisher" <nospam@nospam. nospam.nospam> wrote in message news:<SIJPb.52$ KS1.2983@nasal. pacific.net.au> ...[color=blue]
> "John" <johnw822003@ya hoo.com> wrote:
>[color=green][color=darkred]
> > > 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[/color][/color]
> ?)[color=green][color=darkred]
> > >
> > > 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[/color]
> >
> > 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.[/color]
>
> 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[/color]

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]

Re: Need suggestion on data structure

John wrote:[color=blue]
>
>
> 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.
>[/color]

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
kbuchegg@gascad .at