Algorithm::SpatialIndex - Flexible 2D/3D spacial indexing
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]
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 in-memory storage backend (Algorithm::SpatialIndex::Storage::Memory), and an experimental database-backed 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 two-dimensional, oct trees three-dimensional.
Creates a new spatial index. Requires the following parameters:
The strategy to use. This is the part of the strategy class name after a leading Algorithm::SpatialIndex::Strategy::
.
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:
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
and limit_z_up
do the obvious.
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 also max_depth
below.
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 a new item into the index. Takes the unique item id, an x-, and a y coordinate as arguments.
For three-dimensional spatial indexes such as an oct tree, you must pass three coordinates.
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(...)
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.
Algorithm::SpatialIndex::Strategy::MedianQuadTree
Steffen Mueller, <smueller@cpan.org>
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.