parent results from the CPAN

Algorithm-SpatialIndex

view release on metacpan or search on metacpan

license:            unknown
distribution_type:  module
configure_requires:
    ExtUtils::MakeMaker:  0
build_requires:
    ExtUtils::MakeMaker:  0
requires:
    Class::XSAccessor:  1.05
    lib:                0
    Module::Pluggable:  0
    parent:             0
no_index:
    directory:
        - t
        - inc
generated_by:       ExtUtils::MakeMaker version 6.56
meta-spec:
    url:      http://module-build.sourceforge.net/META-spec-v1.4.html
    version:  1.4

Makefile.PL view on Meta::CPAN

use 5.008001;
use ExtUtils::MakeMaker;
# See lib/ExtUtils/MakeMaker.pm for details of how to influence
# the contents of the Makefile that is written.
WriteMakefile(
    NAME              => 'Algorithm::SpatialIndex',
    VERSION_FROM      => 'lib/Algorithm/SpatialIndex.pm', # finds $VERSION
    PREREQ_PM         => {
      'Module::Pluggable' => '0',
      'Class::XSAccessor' => '1.05',
      'parent'            => '0',
      'lib'               => '0',
    }, # e.g., Module::Name => 1.1
    ($] >= 5.005 ?     ## Add these new keywords supported since 5.005
      (ABSTRACT_FROM  => 'lib/Algorithm/SpatialIndex.pm', # retrieve abstract from module
       AUTHOR         => 'Steffen Mueller <smueller@cpan.org>') : ()),
);

lib/Algorithm/SpatialIndex/Storage/DBI.pm view on Meta::CPAN

package Algorithm::SpatialIndex::Storage::DBI;
use 5.008001;
use strict;
use warnings;
use Carp qw(croak);

our $VERSION = '0.02';

use parent 'Algorithm::SpatialIndex::Storage';
use constant DEBUG => 0;

=head1 NAME

Algorithm::SpatialIndex::Storage::DBI - DBI storage backend

=head1 SYNOPSIS

  use Algorithm::SpatialIndex;
  my $dbh = ...;

lib/Algorithm/SpatialIndex/Storage/Memory.pm view on Meta::CPAN

package Algorithm::SpatialIndex::Storage::Memory;
use 5.008001;
use strict;
use warnings;
use Carp qw(croak);

use parent 'Algorithm::SpatialIndex::Storage';

use Class::XSAccessor {
  getters => {
    _options => 'options',
  },
};

sub init {
  my $self = shift;
  $self->{nodes} = [];

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

package Algorithm::SpatialIndex::Strategy::2D;
use 5.008001;
use strict;
use warnings;

use parent 'Algorithm::SpatialIndex::Strategy';

sub no_of_dimensions { 2 }
sub no_of_subnodes { 4 }
sub coord_types { qw(double double double double) }
sub item_coord_types { qw(double double) }

sub filter_items_in_rect {
  my ($self, $xl, $yl, $xu, $yu, @nodes) = @_;
  my $storage = $self->storage;
  if ($storage->bucket_class->can('items_in_rect')) {

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

package Algorithm::SpatialIndex::Strategy::3D;
use 5.008001;
use strict;
use warnings;

use parent 'Algorithm::SpatialIndex::Strategy';

sub no_of_dimensions { 3 }
sub no_of_subnodes { 8 }
sub coord_types { qw(double double double double double double) }
sub item_coord_types { qw(double double double) }

sub filter_items_in_rect {
  my ($self, $xl, $yl, $zl, $xu, $yu, $zu, @nodes) = @_;
  my $storage = $self->storage;
  if ($storage->bucket_class->can('items_in_rect')) {

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

package Algorithm::SpatialIndex::Strategy::OctTree;
use 5.008001;
use strict;
use warnings;
use Carp qw(croak);

use parent 'Algorithm::SpatialIndex::Strategy::3D';

# Note that the subnode indexes are as follows:
# (like octants, http://en.wikipedia.org/wiki/Octant)
# After wikipedia:
#
#  0) first octant (+, +, +)
#  1) top-back-right (âˆ’, +, +)
#  2) top-back-left (âˆ’, âˆ’, +)
#  3) top-front-left (+, âˆ’, +)
#  4) bottom-front-left (+, âˆ’, âˆ’)

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

    ($c->[YLOW]+$c->[YUP])/2,
    ($c->[ZLOW]+$c->[ZUP])/2,
  );
}


# Splits the given node into four new nodes of equal
# size and assigns the items
sub _split_node {
  my $self        = shift;
  my $parent_node = shift;
  my $bucket      = shift; # just for speed, can be taken from parent_node

  my $storage = $self->storage;
  my $parent_node_id = $parent_node->id;
  $bucket = $storage->fetch_bucket($parent_node_id) if not defined $bucket;

  my $coords = $parent_node->coords;
  my ($splitx, $splity, $splitz) = $self->_node_split_coords($parent_node, $bucket, $coords);
  @$coords[XSPLIT, YSPLIT, ZSPLIT] = ($splitx, $splity, $splitz); # stored below
  my @child_nodes;

  # PPP_NODE
  push @child_nodes, Algorithm::SpatialIndex::Node->new(
    coords      => [$splitx, $splity, $splitz,
                    $coords->[XUP], $coords->[YUP], $coords->[ZUP],
                    undef, undef, undef],
    subnode_ids => [],
  );

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

  );
  # PPM_NODE
  push @child_nodes, Algorithm::SpatialIndex::Node->new(
    coords      => [$splitx, $splity, $coords->[ZLOW],
                    $coords->[XUP], $coords->[YUP], $splitz,
                    undef, undef, undef],
    subnode_ids => [],
  );

  # save nodes
  my $snode_ids = $parent_node->subnode_ids;
  foreach my $cnode (@child_nodes) {
    push @{$snode_ids}, $storage->store_node($cnode);
  }
  $storage->store_node($parent_node);

  # split bucket
  my $items = $bucket->items;
  my @child_items = ( map [], @child_nodes );
  foreach my $item (@$items) {
    if ($item->[XI] <= $splitx) {
      if ($item->[YI] <= $splity) {
        if ($item->[ZI] <= $splitz) { push @{$child_items[MMM_NODE]}, $item }
        else                        { push @{$child_items[MMP_NODE]}, $item }
      }

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

  
  # generate buckets
  foreach my $subnode_idx (0..$#child_nodes) {
    $self->_make_bucket_for_node(
      $child_nodes[$subnode_idx],
      $storage,
      $child_items[$subnode_idx]
    );
  }

  # remove the parent node's bucket
  $storage->delete_bucket($bucket);
}

sub _make_bucket_for_node {
  my $self = shift;
  my $node_id = shift;
  my $storage = shift || $self->storage;
  my $items = shift || [];
  $node_id = $node_id->id if ref $node_id;

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

package Algorithm::SpatialIndex::Strategy::QuadTree;
use 5.008001;
use strict;
use warnings;
use Carp qw(croak);

use parent 'Algorithm::SpatialIndex::Strategy::2D';

# Note that the subnode indexes are as follows:
# (like quadrants in planar geometry)
#
# /---\
# |1|0|
# |-+-|
# |2+3|
# \---/
#

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

  # args: $self, $node, $bucket, $coords
  my $c = $_[3];
  return( ($c->[0]+$c->[2])/2, ($c->[1]+$c->[3])/2 );
}


# Splits the given node into four new nodes of equal
# size and assigns the items
sub _split_node {
  my $self        = shift;
  my $parent_node = shift;
  my $bucket      = shift; # just for speed, can be taken from parent_node

  my $storage = $self->storage;
  my $parent_node_id = $parent_node->id;
  $bucket = $storage->fetch_bucket($parent_node_id) if not defined $bucket;

  my $coords = $parent_node->coords;
  my ($splitx, $splity) = $self->_node_split_coords($parent_node, $bucket, $coords);
  @$coords[XSPLIT, YSPLIT] = ($splitx, $splity); # stored below
  my @child_nodes;

  # UPPER_RIGHT_NODE => 0
  push @child_nodes, Algorithm::SpatialIndex::Node->new(
    coords      => [$splitx, $splity, $coords->[XUP], $coords->[YUP], undef, undef],
    subnode_ids => [],
  );
  # UPPER_LEFT_NODE => 1
  push @child_nodes, Algorithm::SpatialIndex::Node->new(

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

    coords      => [$coords->[XLOW], $coords->[YLOW], $splitx, $splity, undef, undef],
    subnode_ids => [],
  );
  # LOWER_RIGHT_NODE => 3
  push @child_nodes, Algorithm::SpatialIndex::Node->new(
    coords      => [$splitx, $coords->[YLOW], $coords->[XUP], $splity, undef, undef],
    subnode_ids => [],
  );

  # save nodes
  my $snode_ids = $parent_node->subnode_ids;
  foreach my $cnode (@child_nodes) {
    push @{$snode_ids}, $storage->store_node($cnode);
  }
  $storage->store_node($parent_node);

  # split bucket
  my $items = $bucket->items;
  my @child_items = ([], [], [], []);
  foreach my $item (@$items) {
    if ($item->[XI] <= $splitx) {
      if ($item->[YI] <= $splity) { push @{$child_items[LOWER_LEFT_NODE]}, $item }
      else                        { push @{$child_items[UPPER_LEFT_NODE]}, $item }
    }
    else {

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

  
  # generate buckets
  foreach my $subnode_idx (0..3) {
    $self->_make_bucket_for_node(
      $child_nodes[$subnode_idx],
      $storage,
      $child_items[$subnode_idx]
    );
  }

  # remove the parent node's bucket
  $storage->delete_bucket($bucket);
}

sub _make_bucket_for_node {
  my $self = shift;
  my $node_id = shift;
  my $storage = shift || $self->storage;
  my $items = shift || [];
  $node_id = $node_id->id if ref $node_id;

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

package Algorithm::SpatialIndex::Strategy::Test;
use strict;
use warnings;
use parent 'Algorithm::SpatialIndex::Strategy::2D';

our $InitStorageCalled;
our $InitCalled;

sub insert {} # noop

sub init_storage {
  $InitStorageCalled = 1;
}

( run in 0.265 second using v1.01-cache-2.11-cpan-4d50c553e7e )