NAME
Algorithm::SpatialIndex  Flexible 2D/3D spacial indexing
SYNOPSIS
use Algorithm::SpatialIndex;
my $idx = Algorithm::SpatialIndex>new(
strategy => 'QuadTree', # or others
storage => 'Memory', # or others
limit_x_low => 100,
limit_x_up => 100,
limit_y_low => 100,
limit_y_up => 100,
bucket_size => 100,
max_depth => 20,
);
# fill (many times with different values):
$idx>insert($id, $x, $y);
# query
my @items = $idx>get_items_in_rect($xlow, $ylow, $xup, $yup);
# @items now contains 0 or more array refs [$id, $x, $y]
DESCRIPTION
A generic implementation of spatial (2D and 3D) indexes with support for pluggable algorithms (henceforth: strategies) and storage backends.
Right now, this package ships with a quad tree implementation (Algorithm::SpatialIndex::Strategy::QuadTree), an experimental oct tree (3D indexing, Algorithm::SpatialIndex::Strategy::OctTree), an inmemory storage backend (Algorithm::SpatialIndex::Storage::Memory), and an experimental databasebacked storage (Algorithm::SpatialIndex::Storage::DBI),
NOTE: This is an experimental release. There must be bugs.
The functionality is split between pluggable storage backends (see Algorithm::SpatialIndex::Storage) and strategies (see Algorithm::SpatialIndex::Strategy, the latter of which implement the actual indexing algorithm, usually some form of tree.
For the basic quad tree (Algorithm::SpatialIndex::Strategy::QuadTree) and oct tree strategies, the tree is built from Algorithm::SpatialIndex::Nodes. For each leaf node of the tree, the storage contains a bucket (Algorithm::SpatialIndex::Bucket). The buckets are basically dumb, linear complexity storage for items. Each item is simply an array reference containing an id followed by two or more coordinates. The dimensionality depends on the strategy. For example, quad trees are twodimensional, oct trees threedimensional.
new
Creates a new spatial index. Requires the following parameters:
 strategy

The strategy to use. This is the part of the strategy class name after a leading
Algorithm::SpatialIndex::Strategy::
.  storage

The storage backend to use. This is the part of the storage class name after a leading
Algorithm::SpatialIndex::Storage::
.
The following parameters are optional:
 limit_x_low limit_x_up limit_y_low limit_y_up limit_z_low limit_z_up

The upper/lower limits of the x/y dimensions of the index. Defaults to
[100, 100]
for both dimensions.If the chosen strategy is suitable for 3D indexing,
limit_z_low
andlimit_z_up
do the obvious.  bucket_size

The number of items to store in a single leaf node (bucket). If this number is exceeded by an insertion, the node is split up according to the chosen strategy.
bucket_size
defaults to 100. See alsomax_depth
below.  max_depth

The maximum depth of the underlying tree. There can be a collision of limiting the bucket size with limiting the maximum depth of the tree. If that is the case, the maximum depth takes precedence over limiting the bucket size.
max_depth
defaults to 20.
insert
Insert a new item into the index. Takes the unique item id, an x, and a y coordinate as arguments.
For threedimensional spatial indexes such as an oct tree, you must pass three coordinates.
bucket_class
The class name of the bucket implementation to use for the given tree. Defaults to using Algorithm::SpatialIndex::Bucket
. May be either a fully qualified class name or just the fourth level of the namespace, implicitly prefixed by Algorithm::SpatialIndex::Bucket::
.
All storage engines and strategies must use the bucket_class
accessor of the storage engines when constructing new buckets to remain pluggable:
$storage>bucket_class>new(...)
get_items_in_rect
Given the coordinates of two points that define a rectangle (or a cuboid in 3D), this method finds all items within that rectangle (or cuboid).
Returns a list of array references each of which contains the id and coordinates of a single item.
Usage for 2D:
$idx>get_items_in_rect($x1, $y1, $x2, $y2);
Usage for 3D:
$idx>get_items_in_rect($x1, $y1, $z1, $x2, $y2, $z2);
If the chosen bucket implementation exposes a method of the name items_in_rect
, it will be called instead of manually filtering the items returned from $bucket>items()
. This is intended as an optimization. If you're just going to implement an O(n) scan on your bucket, don't bother.
SEE ALSO
Algorithm::SpatialIndex::Strategy::MedianQuadTree
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.
1 POD Error
The following errors were encountered while parsing the POD:
 Around line 216:
You forgot a '=back' before '=head2'