CODEWITHSUNDEEP
javadata-structuresgeolocationrange
bw_dev
bw_dev

Reputation: 795

The "in memory" data structures for getting "around me" Geo locations

I need to create method (class) that looks for points of interest, which are located within given distance.

Something like this:

Collection <Position>  getAroundMe(Position myPosition, int distInMeters);

The method should use "in memory data" (not DB).

The Position class is:

Position {
    double latitude;
    double longitude;
}

I wanted to use TreeSet to store points of interest, but I failed to define comparator for two (latitude and longitude) fields.

Your advises, please.

Comment: the "in memory data" is updated rarely, while there is about 1000 invocation of getArroundMe method per minute (currently it works with DB).

Upvotes: 1

Views: 486

Answers (1)

Thomas
Thomas

Reputation: 88707

You'd have to constantly update the map when your position changes so that's probably not an option.

Approach 1

A simple approach might be to maintain two lists sorted by longitude and latitude. When getting the positions with distance x to your current position you could do the following:

  • Get the interval current.longitude +/- x and look up that interval in the longitude list, e.g. by using binary search.
  • Do the same for latitude.
  • Keep only positions present in both intervals.
  • Sort the positions based on distance to your current postion.
  • Use binary search to locate and remove all positions with a distance greater than x.

Approach 2

An alternative, but more complex approach might be a quad tree where you define a rectangular region that contains all the positions, subdivide that into 4 smaller rectangles of equal size, continue subdivision until you reach a reasonable level (not too deep as you'll have exponential growth in squares) and assign the positions to their respective leaf squares.

Then you check which leaf squares are touched by the square box of side length x and with the center at your current position by checking top-down. Doing that you get a list of positions that might be in the circle of diameter x around your position so you'll need to check them and remove all with a greater distance from the result.

Approach 3

Another alternative you could try is the so-called hash grid (see here for example: http://www.gicentre.net/utils/hashgrid/). With that you basically define a hash-function based on the (rough) position, i.e. you truncate the position to some "cell-size" and calculate a hash-value for that lower precision position. You'd end up with nearby positions having the same hash and thus being in the same virtual cell. Since you'd not want to use as many buckets as cells your hash value would probably wrap around eventually and you'd end up with a list of cells in each bucket that are not close to each other.

When checking for positions you first calculate which cells the circle around your current position would touch and then look them up in the hashmap. Then you'd check the positions in those cells as before.

Upvotes: 1

Related Questions