search

mourner / kdbush

A fast static index for 2D points
ISC License
638 stars 69 forks source link

`.within()` queries using different radii in each dimension #35

Closed duhaime closed 3 years ago

duhaime commented 3 years ago

This is a fantastic library--thank you for your great work!

I just ran into a situation where I had Date().getTime() objects in one dimension and floats scaled 1:100 in the other dimension, and couldn't figure out why my .within() queries were not returning results. It seems the query radius is currently uniform across both dimensions, so a value that might make sense for one of my dimensions did not make sense for the other!

It could be interesting to allow for one search radius in one dimension and another radius in the other dimension in case other fools like myself bump into this kind of situation. This challenge can of course be overcome by using a .range() query or by scaling one's data, but it could be nice to perform radius-driven queries without scaling one's data!

mourner commented 3 years ago

It seems the query radius is currently uniform across both dimensions, so a value that might make sense for one of my dimensions did not make sense for the other!

I think it's generally not a good option to use within(x, y, distance) in case of dimensions of different meanings, because Euclidean distance isn't very meaningful in this case — if you're requesting points within a radius, what units the radius is in? I would rather not increase the API complexity for a use case that's already confusing — it's better to just use range queries.

duhaime commented 3 years ago

I understand entirely. I guess my thought was that users who are mousing over points in a scatterplot generally perceive the spatial field through which they are mousing (the canvas or svg) with Euclidean intuitions--if mousing over radius r in pixels away from a point selects that point, they expect that radius to be constant in each dimension--but the data of a scatterplot rarely preserves Euclidean distance. So a range query doesn't obey their intuition of the space (as in that case a particular point may be selectable in a boxy, non-Euclidean way), while a within query does obey their intuition of the space but may require scaling. That said, one doesn't need the API to change to enable the behavior I'm after.