Decent (r-tree, quad-tree or similar) library in ruby for searching spatial data

I have a database of 20k+ cities with latitude and longitude and I need to make lot of nearest point queries (which city is the nearest to certain lat,long point) against this dataset.

I guess an R-Tree or开发者_Go百科 QuadTree would be a perfect data structure for this, but I haven't been able to find a working ruby implementation. Do you know any?

I've found the kd-tree gem which helped me solve the above task

Or try:

https://github.com/iterationlabs/rquad