Syntactic Confectionery Delight PerlMonks

### Re: Lookup closest hash key

by Corion (Pope)
 on Jan 25, 2011 at 08:11 UTC ( #884077=note: print w/replies, xml ) Need Help??

in reply to Lookup closest hash key

Steffen Müller has been working on Algorithm::SpatialIndex, which creates (for example) a quadtree, a structure that can easily tell you what rectangle a point falls in. I'm not sure whether you can massage your data to cover the area with rectangles, but maybe that works or works well enough. Alternatively, maybe one of the Voronoi modules helps you to create the areas where a point is "nearest".

Replies are listed 'Best First'.
Re^2: Lookup closest hash key
by JavaFan (Canon) on Jan 25, 2011 at 09:43 UTC
The OP is only interested in nearest in a one-dimensional space. No need for quadtrees or Voronoi diagrams. Depending how often the OP needs to query his structure, I'd either keep the numbers sorted, or just do a linear pass.
The OP is only interested in nearest in a one-dimensional space.
Actually, I don't think he is. This looks like an XY problem to me, and I think Corion thought the same thing...

Distances between cities is intrinsically a 2-dimensional problem.

We don't know what the rest of the OP's code does, but I assume it's something that could be better integrated with a solution to the question that was asked.

> Distances between cities is intrinsically a 2-dimensional problem.

My understanding was that the distances are calculated starting from a 0km origin, hence it's one dimensional.

And I'm not sure if Corion's suggestions can be easily applied to spherical distances...

Cheers Rolf

Actually, I don't think he is.
Considering the OP actually gave us an example hash, and an example search query, I'm not going to assume he has figured out how to use spherical coordinates as hash keys. (For which neither Voronoi diagrams, nor quadtrees can be used directly).

Create A New User
Node Status?
node history
Node Type: note [id://884077]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (6)
As of 2021-01-17 10:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The STEM quote I most wish I'd made is:

Results (171 votes). Check out past polls.

Notices?