A kdtree is a data structure that makes it possible to quickly solve the nearest neighbor problem. This is a native 2d kdtree suitable for production use with millions of points.
Adam Doppelt
gem "kdtree", "~> 0.3"