The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.


Algorithm::SpatialIndex::Strategy - Base class for indexing strategies


  use Algorithm::SpatialIndex;
  my $idx = Algorithm::SpatialIndex->new(
    strategy => 'QuadTree', # or others


This is the base class for all algorithm implementations (Strategies) in Algorithm::SpatialIndex. Your implementation should probably not inherit from this class directly, but from either Algorithm::SpatialIndex::Strategy::2D or Algorithm::SpatialIndex::Strategy::3D depending on the dimensionality of your index.



Inserts a new element into the index. Arguments: Element (not node!) integer id, Element x/y (and possibly z) coordinates.

Needs to be implemented in a subclass.


Given x/y (or x/y/z) coordinates, returns the Algorithm::SpatialIndex::Node that contains the given point.

Returns undef if the point is outside of the index range.

Needs to be implemented in a subclass.


Given two sets of x/y (or x/y/z) coordinates, returns all Algorithm::SpatialIndex::Nodes that are completely or partly within the rectangle defined by the two points.

Needs to be implemented in a subclass.


Constructor. Called by the Algorithm::SpatialIndex constructor. You probably do not need to call or implement this. Calls your init method if available.


If your subcass implements this, it will be called on the fresh object in the constructor.


If your subcass implements this, it will be called on the in the constructor after initializing its storage attribute.


A method returning the number of dimensions that the index handles.

This is set to a default in the 2D/3D subclasses.


Returns the number of subnodes per node. Required by the storage initialization.

This is set to a default in the 2D/3D subclasses.


Returns (as a list) all node coordinate's types. If you need to store one x/y pair of floating point coordinates per node, you may return:

  qw(double double)

or if less precision is acceptable for space savings:

  qw(float float)

If you need to store three coordinates but only in one dimension, you simply do:

  qw(float float float)

The storage backend is free to upgrade a float to a double value and even an integer to a double.

Valid coordinate types are:

  float, double, integer, unsigned

The integer types will be treated as C longs (likely 32bit).

This is set to a default in the 2D/3D subclasses. You may want to override that in your subclass.


Same as coord_types, but indicating what's required for each item stored in the tree.

This is set to a default in the 2D/3D subclasses.


This method is implemented in Algorithm::SpatialIndex::Strategy::2D and Algorithm::SpatialIndex::Strategy::3D for their respective dimensionality. If you inherit from those classes, you will not have to reimplement this in your strategy implementation.

Given the four or six coordinates of a rectangle (2D) or cuboid (3D) and one or more leaf node objects, this method fetches all items associated with the node(s) and returns all of those items that lie in the specified rectangle or cuboid.

The rectangle/cuboid coordinates are expected to be sorted (thus the use of $xl, $yl and $xu, $yu instead of 1/2) in the example:

  # 2D
  my @items = $strategy->filter_items_in_rect($xl, $yl, $xu, $yu, $node1, $node2, ...);
  # 3D
  my @items = $strategy->filter_items_in_rect(
    $xl, $yl, $zl,
    $xu, $yu, $zu,
    $node1, $node2, ...


Steffen Mueller, <>


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.

2 POD Errors

The following errors were encountered while parsing the POD:

Around line 191:

'=item' outside of any '=over'

Around line 217:

You forgot a '=back' before '=head1'