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 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.

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 and limit_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 also max_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 three-dimensional 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

Algorithm::QuadTree

Tree::M

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.

cpanm Algorithm::SpatialIndex

perl -MCPAN -e shell
install Algorithm::SpatialIndex