4

I have a set of features (a few hundreds, can grow to a couple of thousands), which have a latitude and longitude. They are not stored in a database because they change frequently (another system is keeping track of them and feeding them to systems including the one in question).

I want to just keep them in memory because the information is very volatile (the objects will be moving on the map).

What is the best Java API I can use to query the closest N features of a certain type to a specific point?

I was looking at either JTS or GeoTools (which uses JTS under the hood), but couldn't find any examples of "find the nearest N features" (maybe I was looking at the wrong thing or searched with the wrong keywords).

JTS seems to have a KDTree that I gather is an efficient data structure for what I need? But no idea how to go from there.

The answer to Finding N nearest points to point using JTS? seems to indicate that more work is needed to do it, but there surely must be a way to do it from the APIs available that I am just missing, because this is such a common requirement (closest restaurants, closest ATMs etc.).

PolyGeo
  • 65,136
  • 29
  • 109
  • 338
jbx
  • 199
  • 1
  • 6

1 Answers1

4

While JTS does have a KdTree implementation, which is the most efficient spatial index for points, that class does not yet have a nearest-neighbours capability.

The STRtree class does have a k-nearest-neighbours method, but unfortunately that implementation is not dynamic, so may not work for your use case.

So you may have to use the approach given in Finding N nearest points to point using JTS?.

Keep in mind the caveat about geodetic distance vs planar distance. If geodetic distance is required you may need a more sophisticated algorithm.

dr_jts
  • 5,038
  • 18
  • 15
  • I do have a function (I had ported it from JS that I found somewhere on a question here) that calculates distance using the earth radius etc. (I think it assumes the Earth is a sphere) so I think that is not a problem. Assuming that is available, can you update your answer with the right steps (just pseudo code) to find the nearest features of interest from a KDTree? Otherwise what if I built the STRtree from scratch from the data I have available each time I have a new query would that be a bad idea? (I have only a few thousand features of interest) – jbx May 02 '19 at 07:59
  • You can use the same approach as in [https://gis.stackexchange.com/questions/158635] but use a KDtree. As for rebuilding a tree on each query, that is going to be slower than simply iterating over all data items. – dr_jts May 02 '19 at 17:57