Steffen Müller > Algorithm-SpatialIndex-Strategy-MedianQuadTree > Algorithm::SpatialIndex::Strategy::MedianQuadTree

Download:
Algorithm-SpatialIndex-Strategy-MedianQuadTree-0.02.tar.gz

Dependencies

Annotate this POD

View/Report Bugs
Module Version: 0.02   Source  

NAME ^

Algorithm::SpatialIndex::Strategy::MedianQuadTree - QuadTree splitting on bucket medians

SYNOPSIS ^

  use Algorithm::SpatialIndex;
  my $idx = Algorithm::SpatialIndex->new(
    strategy => 'MedianQuadTree',
  );

DESCRIPTION ^

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 ALGORITHM below.

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.

ALGORITHM ^

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:

SEE ALSO ^

Algorithm::SpatialIndex

Algorithm::SpatialIndex::Strategy::QuadTree

Algorithm::SpatialIndex::Strategy

Algorithm::QuadTree

AUTHOR ^

Steffen Mueller, <smueller@cpan.org>

COPYRIGHT AND LICENSE ^

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.

syntax highlighting: