Leaflet.Quadtree

Leaflet plugin that implements a quadtree for efficient retrieval of visible features' properties

To see the plugin in action just click one of the following links:

Huge number of elements: 1 million markers are created in random places and the quadtree is used to fetch the visible ones and add them to the map when it's moved. You can find the demo here (Alert: The browser tab might report itself as not working when creating the markers, just wait for it to finish)
Visible feature properties retrieval: Sample data is loaded into the map and the quadtree is used to efficiently crawl the features of each visible element. You can find the demo here
Marker culling: On each click a numbered marker is created, the quadtree is updated and the visible elements' numbers are shown. You can find the demo here
Quadtree construction: On each click a marker is created and the resulting quadtree is shown. You can find the demo here

Usage

Create a marker or a polygon and add it to the quadtree. It can even be your own class, it only has to implement the getLatLng() or the getBounds() methods.

// create the quadtree with the options you want
var quadtree = L.quadtree({maxObjectsPerLevel: 4});
...

// add the markers to the quadtree
quadtree.add(marker);
...

//retrieve the visible markers or polygons inside some bounds
//map bounds are used in the examples but any bounds can be used
var bounds = map.getBounds();
var colliders = quadtree.getColliders(bounds);

Documentation

Constructor

Constructs a quadtree object

var quadtree = L.quadtree(options);

Options

Property	Description	Type	Default
maxObjectsPerLevel	Maximum number of markers or polygons per level. When the number of objects on a level is greater than the one specified here the node is split into 4 child nodes.	Integer	10
maxLevels	Maximum number of levels of the quadtree. When the quadtree reaches this depth the leaf nodes are not split anymore	Integer	8

Add element to the quadtree

Adds an element to the quatree. Any object that implements the getLatLng() or the getBounds() methods is supported

var quadtree = L.quadtree(options);
...
quadtree.add(marker);

Get colliders

Gets an array with the elements that fall inside the given bounds

var quadtree = L.quadtree(options);
...
var colliders = quadtree.getColliders(bounds);

Get the possible colliders

Gets an array with the elements that might fall inside the given bounds. This method is faster than the previous one although it's inexact, you can use it if you only need an upper bound of the visible elements. This method returns the elements found on the leaf nodes that intersect the given bounds

var quadtree = L.quadtree(options);
...
var colliders = quadtree.getPossibleColliders(bounds);

Get quadtree stats

Gets an array with the number of elements inside each node. If a node has childs an array is returned with the elements of its child nodes in the following order [NW, NE, SW, SE]

var quadtree = L.quadtree(options);
...
var stats = quadtree.getQuadtreeStats();

ibesora/Leaflet.Quadtree