Re: Need suggestion on data structure
From: Programmer Dude (Chris_at_Sonnack.com)
Date: Fri, 23 Jan 2004 14:01:58 -0600
> 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). Any suggestion is appreciated.
You've gotten answers dealing with small numbers of points. If
you have many, many points, perhaps a sparse matrix implementation
would be fun and useful.
Typical implementation uses two linked lists as row and column
"headers", with linked lists going into the matrix where needed.
Here's a diagram: http://www.sonnack.com/Pub/sparse_matix.gif
A little trig will give you the range of coordinates that are close
to any given point, so your second operation would involve defining
the "closeness" range and searching for points in that range.
-- |_ CJSonnack <Chris@Sonnack.com> _____________| How's my programming? | |_ http://www.Sonnack.com/ ___________________| Call: 1-800-DEV-NULL | |_____________________________________________|_______________________|