Find the nearest location in an STRtree

Question

I'm using the nettopologysuite (a port of the JTS Topology Suite). I'm using the SRTtree implementation to store a list of timezones and a corresponding coordinates (based on this suggestion ). I took the list of cities from geonames, pulled out the timezone of the city and the coordinates and I'm storing them in the STRtree. the problem I'm having is that this implementation doesn't provide a "Nearest" function. In order to do a query I have to provide a starting point and a circumference. Currently I'm incrementing the circumference by .1 in a loop until I find some results and then i take the first one. Is there a better way of doing this?

Here's what I'm doing:

    public static SRTtree Cities { get; set; }

    public static string GetTimezone(double lat, double lng)
    {
        var envelope = new Envelope(new Coordinate(lat, lng));

        IList results;

        do
        {
            envelope.ExpandBy(.1);
            results = Cities.Query(envelope);
        } while (results.Count == 0);

        return results[0] as string;
    }

score 2 · Answer 1 · answered Apr 22 '13 at 19:28

2

JTS 1.13 provides the STRTree.nearestNeighbour method to perform this operation. I don't know if that's been ported to NTS yet, but if not perhaps you can request it.

answered Apr 22 '13 at 19:28

dr_jts

211
1
5

score 0 · Answer 2 · edited May 23 '17 at 11:59

If the only query you need to run is "Get the nearest location", using an R-Tree might not be the best choice. I could think of two alternatives:

Compute the distance to every location using the Harvesine formula and find the minimal distance. If you don't have too many coordinates this could be the optimal solution. See "Proximity Search" for more details.
Use a data structure that allows searching for nearest coordinates, such as KD-Tree. Note that the KD-Tree implementation in NetTopologySuite is not suitable for your use case.

Find the nearest location in an STRtree

2 Answers2