NAME Algorithm::SpatialIndex - Flexible 2D 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, ); # 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) 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) and an in-memory storage backend (Algorithm::SpatialIndex::Storage::Memory). 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 The upper/lower limits of the x/y dimensions of the index. Defaults to "[-100, 100]" for both dimensions. 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. insert Insert a new item into the index. Takes the unique item id, an x-, and a y coordinate as arguments. get_items_in_rect Given the coordinates of two points that define a rectangle, this method finds all items within that rectangle. Returns a list of array references each of which contains the id and coordinates of a single item. SEE ALSO Algorithm::SpatialIndex::Strategy::MedianQuadTree Algorithm::QuadTree Tree::M AUTHOR Steffen Mueller, COPYRIGHT AND LICENSE Copyright (C) 2010 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. POD ERRORS Hey! The above document had some coding errors, which are explained below: Around line 183: You forgot a '=back' before '=head2'