NAME

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

SYNOPSIS

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

DESCRIPTION

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.

METHODS

insert

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.

find_node_for

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.

find_nodes_for

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.

new

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

init

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

init_storage

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

no_of_dimensions

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

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

no_of_subnodes

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

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

coord_types

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.

item_coord_types

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.

filter_items_in_rect

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

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