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.).

Improve this question

1 Answer 1

Reset to default
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.

Improve this answer
2
  • 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
    Commented May 2, 2019 at 7:59
  • You can use the same approach as in [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
    Commented May 2, 2019 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.