Algorithm::SpatialIndex::Strategy::MedianQuadTree - QuadTree splitting on bucket medians
use Algorithm::SpatialIndex; my $idx = Algorithm::SpatialIndex->new( strategy => 'MedianQuadTree', );
A modified quad tree implementation that I'll call Median Quad Tree (MQT) in this document. (Not sure if this data structure has a different name elsewhere.) See
For a description of the public interface, see Algorithm::SpatialIndex. This spatial index strategy uses the default
Algorithm::SpatialIndex::Strategy::QuadTree as a base class and gets away with containing very little code because of that. This also means that most of the interface and behaviour is inherited.
For a basic discussion of quad trees, take a look at the documentation of the Algorithm::QuadTree module or look it up on Wikipedia. The following describes how the MQT differs from a normal quad tree and some implementation details.
Any x/y coordinate pair can be used to divide a rectangular area into four sub-rectangles. When splitting up a node of an ordinary quad tree, the center of the quad tree is chosen to split the node into four sub-nodes. This can be done either when the tree is created (before it is populated) with a static depth of the tree, or dynamically whenever the number of items associated with a node becomes too large.
For the MQT, the point which splits a given node into four is chosen to be the median of all contained item coordinates in each dimension.
This has several consequences:
If the MQT is filled in random order and the data is not uniformly distributed, it will, on average, have more evenly filled buckets and thus less nodes than a quad tree, thus reducing the amount of tree walking required while filling and later polling the index.
Steffen Mueller, <email@example.com>
Copyright (C) 2010-2011 by Steffen Mueller
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.10.1 or, at your option, any later version of Perl 5 you may have available.