What kind of algorithm/data layout should I use for fast two-dimensional search?

Question

I want to build an embedded device which will take its current location (in latitude, longitude) and output custom serial data about a number of the nearest few points in a list.

• Current location and the points holding the custom data are represented by latitude and longitude, although could be projected to another coordinate system in preprocessing.

• Nearest doesn't need to be too accurate. The points are fairly sparse - tens of miles apart in general and where two are close-by it unlikely to matter much which order they are presented in. And I'm only interested in points within the nearest 50 miles or so.#

• The list is intended to be static, albeit updated periodically. No dynamic changes are expected.

I'm currently thinking of using an Arduino with GPS/SD card shield, but am struggling to come up with a sensible way of storing the data which doesn't need an exhaustive search (which I assume will be too slow and use too much memory).

Is there a common pattern to do this? Obviously postgis, etc. do this sort of thing, but they're far too bloaty to run on an Arduino and similar techniques will suffer the same issues.

I'm expecting to need to do some sort of preprocessing such that I get a tree lookup or similar, but can't see how this would work in more than one dimension.

Answer 1

Assuming you're matching current pos against a set of known points, storing points in a QuadTree should cut down search time to O(log n).

By being clever with subdivisions and storing 5-10 items in the leaves, it should be efficient in terms of memory space too.

Answer 2

A Z-Order curve might be a useful representation of a quad-tree in your low memory, low performance situation.

Basically, it computes an 1-dimensional ordering of your points, which preserves locality. Once you know where to start, you search linearly in memory, skipping over entries not in your search rectangle. Wikipedia has a description of how to do that.

This might get you of the hook of maintaining a quad-tree.

Answer 3

A k-d tree appears to be a good fit for this problem. In particular, the nearest neighbour search seems relatively straightforward:

The nearest neighbour search (NN) algorithm aims to find the point in the tree that is nearest to a given input point. This search can be done efficiently by using the tree properties to quickly eliminate large portions of the search space.

Searching for a nearest neighbour in a k-d tree proceeds as follows:

1. Starting with the root node, the algorithm moves down the tree recursively, in the same way that it would if the search point were being inserted (i.e. it goes left or right depending on whether the point is lesser than or greater than the current node in the split dimension).

2. Once the algorithm reaches a leaf node, it saves that node point as the "current best"

3. The algorithm unwinds the recursion of the tree, performing the following steps at each node:

   1. If the current node is closer than the current best, then it becomes the current best.

   2. The algorithm checks whether there could be any points on the other side of the splitting plane that are closer to the search point than the current best. In concept, this is done by intersecting the splitting hyperplane with a hypersphere around the search point that has a radius equal to the current nearest distance. Since the hyperplanes are all axis-aligned this is implemented as a simple comparison to see whether the distance between the splitting coordinate of the search point and current node is lesser than the distance (overall coordinates) from the search point to the current best.

      1. If the hypersphere crosses the plane, there could be nearer points on the other side of the plane, so the algorithm must move down the other branch of the tree from the current node looking for closer points, following the same recursive process as the entire search.

      2. If the hypersphere doesn't intersect the splitting plane, then the algorithm continues walking up the tree, and the entire branch on the other side of that node is eliminated.

4. When the algorithm finishes this process for the root node, then the search is complete.

Creating a suitably seek-able flat-file format to store said k-d tree is left as an exercise for the reader.

Answer 4

I have implemented this kind of search for a common database with no special geographical indexing features. The trick is to divide the possible areas into tiles at ever-increasing zoom levels. For example, at the zoom level 0, you have the tile 0. At zoom level 1, you have tiles 1,2,3,4. At zoom level 2, you have tiles 5,6,7,8, 9,10,11,12, 13,14,15,16, 17,18,19,20. So, each tile in zoom level N is broken into four smaller tiles in zoom level N+1.

Then for each row you have columns tile0, tile1, tile2, tile3, ..., tile19 (assuming 20 zoom levels total). Or actually, you could omit tile0 as it's always 0. Each of these tileN columns is indexed by a standard B-tree index.

Then you need the algorithm for quickly deciding which is the tile corresponding to an arbitrary (x,y) coordinate at zoom level N. I don't recall now how I implemented this algorithm, but I recall it was somewhat tricky but the algorithm ended up being extremely fast.

In case the (x,y) coordinate is near the edge of the tile, the neighboring tile may contain a solution that is better than the best solution in the current tile. So, in general, you need to include four tiles in your search at zoom level N. You need to implement the function that calculates these four tiles.

If you have zoom levels 0, 1, 2, ..., 19 you start by searching the four suitable tiles at zoom level 19, then at 18, then at 17, ... until you have big enough result set.

Answer 5

A geohash is a good solution here. You can make the length according to the precision you need, and on your SD card make the geohash the filename. That will let you read a few files to get all points within a certain proximity, then filter/sort from there.

Answer 6

I have successfully implemented a couple of projects using R-Trees for this purpose.

One implementation is here which in turn is a partially ported version of a java libary (jsi).