Esa's Google Maps API v3 experiments

Indexing LatLng points by Quadtree QT.js

Quadtree is a fast and fascinating spatial indexing technique

Quadtree in Wikipedia

The root node is the whole world tile. (zoom level 0) The node is split down to four quadrants identified by number 0, 1, 2 or 3 (from top left in Z shape). The selected quadrant is split to four quadrants again identified by number 0, 1, 2 or 3 and so on...

The quadtree key string is a quaternary (base 4) number.

A quadtree of length 30, defines better than four centimeter grid on earth surface. That kind of tile grid would mean mapping the world in actual size on your screen. We can make use of much shorter quadtrees but 30 is a good value for maximum length in web mapping. [April 2011]. It defines a single pixel at zoom level 22.

Climb the tree

Just shorten the string from the end to climb down the tree. Quite simple, isn't it.

A single digit place in the string represents one zoom level in accuracy. Shorten eight digits from the end and the accuracy was degraded 1/256. In other words. Two points that share a tile on zoom level say 17, will share a pixel at zoom level 9. The first nine digits of their quadtree strings are equal.

You can make collision detecting by comparing substrings of two points. If you cut the strings to the current zoom level plus eight, the strings are equal if they share a pixel. Cut one more digits and you find adjacent pixels. Cut two more digits from the end before comparision and you find points in the same 8px x 8px square.

Try clicking on map. Zoom in and out. See fractals?

Quadtree visualized

Clicking the map on left creates an endless looking series of squares representing key lengths 1...30. The biggest square visualizes the area that is defined by the first digit. The smallest square is formed with the full 30 long quadtree key. You cannot see the smallest one:) That is much smaller than a pixel. Visualizing is a built in option in QT.quadToBounds() function of the library.

Compressing

I included base4 <-> base36 conversion functions in the QT.js library because it is so simple in JavaScript. A base36 encoded string of a 30-digit quadtree looks like this:

Note that you cannot cut a base-36 string like you cut a quaternary string.

Base36 was not planned for a certain purpose but it is there waiting for ideas.

Is it a point or an area?

Well, kind of both.

QT.quadToLatLng() returns the geographic LatLng point. It is the top left of the imaginary square.

QT.quadToBounds() returns LatLngBounds of the imaginary square.

Source