NAME
Algorithm::SpatialIndex::Strategy  Base class for indexing strategies
SYNOPSIS
use Algorithm::SpatialIndex;
my $idx = Algorithm::SpatialIndex>new(
strategy => 'QuadTree', # or others
);
DESCRIPTION
This is the base class for all algorithm implementations (Strategies) in Algorithm::SpatialIndex
. Your implementation should probably not inherit from this class directly, but from either Algorithm::SpatialIndex::Strategy::2D or Algorithm::SpatialIndex::Strategy::3D depending on the dimensionality of your index.
METHODS
insert
Inserts a new element into the index. Arguments: Element (not node!) integer id, Element x/y (and possibly z) coordinates.
Needs to be implemented in a subclass.
find_node_for
Given x/y (or x/y/z) coordinates, returns the Algorithm::SpatialIndex::Node that contains the given point.
Returns undef if the point is outside of the index range.
Needs to be implemented in a subclass.
find_nodes_for
Given two sets of x/y (or x/y/z) coordinates, returns all Algorithm::SpatialIndex::Nodes that are completely or partly within the rectangle defined by the two points.
Needs to be implemented in a subclass.
new
Constructor. Called by the Algorithm::SpatialIndex constructor. You probably do not need to call or implement this. Calls your init
method if available.
init
If your subcass implements this, it will be called on the fresh object in the constructor.
init_storage
If your subcass implements this, it will be called on the in the constructor after initializing its storage attribute.
no_of_dimensions
A method returning the number of dimensions that the index handles.
This is set to a default in the 2D/3D subclasses.
no_of_subnodes
Returns the number of subnodes per node. Required by the storage initialization.
This is set to a default in the 2D/3D subclasses.
coord_types
Returns (as a list) all node coordinate's types. If you need to store one x/y pair of floating point coordinates per node, you may return:
qw(double double)
or if less precision is acceptable for space savings:
qw(float float)
If you need to store three coordinates but only in one dimension, you simply do:
qw(float float float)
The storage backend is free to upgrade a float to a double value and even an integer to a double.
Valid coordinate types are:
float, double, integer, unsigned
The integer types will be treated as C longs (likely 32bit).
This is set to a default in the 2D/3D subclasses. You may want to override that in your subclass.
item_coord_types
Same as coord_types, but indicating what's required for each item stored in the tree.
This is set to a default in the 2D/3D subclasses.
 filter_items_in_rect

This method is implemented in Algorithm::SpatialIndex::Strategy::2D and Algorithm::SpatialIndex::Strategy::3D for their respective dimensionality. If you inherit from those classes, you will not have to reimplement this in your strategy implementation.
Given the four or six coordinates of a rectangle (2D) or cuboid (3D) and one or more leaf node objects, this method fetches all items associated with the node(s) and returns all of those items that lie in the specified rectangle or cuboid.
The rectangle/cuboid coordinates are expected to be sorted (thus the use of
$xl, $yl
and$xu, $yu
instead of 1/2) in the example:# 2D my @items = $strategy>filter_items_in_rect($xl, $yl, $xu, $yu, $node1, $node2, ...); # 3D my @items = $strategy>filter_items_in_rect( $xl, $yl, $zl, $xu, $yu, $zu, $node1, $node2, ... );
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.
2 POD Errors
The following errors were encountered while parsing the POD:
 Around line 191:
'=item' outside of any '=over'
 Around line 217:
You forgot a '=back' before '=head1'