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.

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.

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);

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