view release on metacpan or  search on metacpan

lib/Algorithm/SpatialIndex/Strategy/MedianQuadTree.pm  view on Meta::CPAN

package Algorithm::SpatialIndex::Strategy::MedianQuadTree;
use 5.008005;
use strict;
use warnings;
use Carp qw(croak);

our $VERSION = '0.02';

use Algorithm::SpatialIndex::Strategy::QuadTree qw(:all);
use parent 'Algorithm::SpatialIndex::Strategy::QuadTree';

use Statistics::CaseResampling qw(median);

sub _node_split_coords {
  my ($self, $node, $bucket, $coords) = @_;
  my $items = $bucket->items;
  if (@$items == 0) {
    # degrade to a quad tree
    return $self->SUPER::_node_split_coords($node, $bucket, $coords);
  }

  my $xmedian = median([map $_->[XI()], @$items]);
  my $ymedian = median([map $_->[YI()], @$items]);

  return($xmedian, $ymedian);
}

1;
__END__

=head1 NAME

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

=head1 SYNOPSIS

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

=head1 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 C<ALGORITHM>
below.

For a description of the public interface, see L<Algorithm::SpatialIndex>. This
spatial index strategy uses the default C<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.

=head1 ALGORITHM

For a basic discussion of quad trees, take a look at the documentation of the
L<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:

=over 2

=item *

Due to the dynamic nature of the coordinate choice when splitting a node in four,
the MQT cannot be of a fixed depth and preallocated. It needs to grow dynamically as it is
filled.

=item *