view release on metacpan or  search on metacpan

lib/Data/SpatialHash/Shared.pm  view on Meta::CPAN

=head2 2D vs 3D

All methods that accept coordinates accept either (x, y) or (x, y, z).
When z is omitted it is treated as 0, so a 2D query matches the z=0 cell layer
(points within one C<cell_size> of the z=0 plane), not an infinite z-column, and
z does not enter the distance for a 2D call.  A handle created with a 2D
insert can be queried with either 2D or 3D calls.

=head2 Toroidal space

By default the grid is unbounded and Euclidean.  Construct with
C<< wrap => [$Wx, $Wy] >> (2D) or C<< [$Wx, $Wy, $Wz] >> (3D) to make space a
seamless B<torus>: neighbour-cell expansion wraps around the grid edges and
C<query_radius>, C<query_knn>, C<each_in_radius>, C<query_radius_many>, and the
pair emitters all use the minimum-image (shortest wrapping) distance

    dx = abs(ax - bx);  dx = $Wx - dx if dx > $Wx / 2;   # per axis

so an entry near C<0> and one near C<$Wx> are neighbours.  Keep positions within
C<[0, $W)> per axis for the metric to be meaningful.  Each wrapped extent must be
a positive multiple of C<cell_size> so the cells tile the world exactly,
otherwise the constructor croaks.  C<query_cell> resolves its coordinate to a
wrapped cell, but C<query_aabb> uses the literal (non-wrapping) box even in a
wrapping world.  The wrap configuration is part of the mapped format and is
restored on reopen; the C<world> accessor returns the extents.

=head1 METHODS

=head2 Constructors

    my $s = Data::SpatialHash::Shared->new($path, $max, $buckets, $cell);
    my $s = Data::SpatialHash::Shared->new(undef, $max, $buckets, $cell);
    my $s = Data::SpatialHash::Shared->new_memfd($name, $max, $buckets, $cell);
    my $s = Data::SpatialHash::Shared->new_from_fd($fd);
    my $s = Data::SpatialHash::Shared->new($path, $max, $buckets, $cell, wrap => [$Wx, $Wy]);

C<$path> is the backing file path; C<undef> creates an anonymous mapping.
C<$max> is the maximum number of entries.  C<$buckets> is the bucket count
(0 = auto).  C<$cell> is the cell size (float).

Pass C<< wrap => [$Wx, $Wy] >> (or C<< [$Wx, $Wy, $Wz] >>) to make the world a
seamless torus of those extents (see L</Toroidal space>); omit it for an
unbounded Euclidean space.

When reopening an existing backing file or memfd, the stored header wins: the
caller's C<$max>, C<$buckets>, C<$cell>, C<wrap>, and C<sphere> arguments are
ignored and the file's original values are used. They are still validated for
well-formedness first (for example a non-positive C<$cell> croaks), so pass
plausible values even on a reopen; only the stored geometry is authoritative.

C<new_memfd> creates a Linux memfd (anonymous but transferable via C<memfd>
file descriptor).  C<new_from_fd> reopens an existing memfd in another
process.

=head2 Mutators

    my $h = $s->insert(x, y, value);        # 2D insert -- returns handle or undef
    my $h = $s->insert(x, y, z, value);     # 3D insert
    my $h = $s->insert(x, y, z, value, r);  # 3D insert with an interaction radius
    $s->set_radius($h, $r);                 # set/replace an entry's radius
    $s->move($h, x, y);                     # relocate entry (2D)
    $s->move($h, x, y, z);                  # relocate entry (3D)
    $s->remove($h);                         # free entry slot
    $s->set_value($h, $v);                  # update stored value
    $s->clear;                              # remove all entries
    my @ids = $s->insert_many([ [x,y,value], [x,y,value,r], ... ]);  # bulk insert
    my $n   = $s->move_many([ [handle,x,y], [handle,x,y,z], ... ]);  # bulk move

C<insert> returns a handle (opaque integer) on success, or C<undef> if
C<max_entries> is exhausted.  C<move> and C<remove> return true on success,
or false if the handle is invalid or already removed.  C<set_value> instead
croaks on an invalid or freed handle; it and C<clear> return nothing.

Each entry may carry an B<interaction radius> (default 0; must be finite and
non-negative), used by C<each_colliding_pair>.  Set it with the 5-argument C<insert> or with
C<set_radius> (which croaks on an invalid or freed handle); for a 2D entry with
a radius, insert then call C<set_radius>.  C<insert_many> and C<move_many> apply
a whole batch under a single lock acquisition -- each row is an arrayref.
C<insert_many> inserts B<2D> entries (rows C<[x,y,value]> or
C<[x,y,value,radius]>; use C<insert> in a loop for 3D) and returns the list of
handles, with C<undef> for any row that overflowed the pool, was malformed
(not an arrayref of length 3 or 4), or carried a negative or non-finite radius.  C<move_many> takes C<[handle,x,y]> or
C<[handle,x,y,z]> rows and returns the count successfully moved; freed/invalid
handles and malformed rows are skipped.

Handles are entry slot indices starting at B<0>, and B<0 is false in
Perl>.  The very first insert into a fresh hash returns handle C<0>.
Always test the result with C<defined $h>, never for truthiness:

    my $h = $s->insert($x, $y, $v);
    die "full" unless defined $h;   # correct: handle 0 is valid
    # WRONG: "unless $h" would treat the first handle (0) as failure

=head2 Accessors

    $s->has($h);              # true if handle is live
    $s->value($h);            # stored value
    $s->get_radius($h);       # stored interaction radius (0 if unset)
    my ($x, $y, $z) = $s->position($h);   # current position

C<has> is the safe predicate for a possibly-freed handle; C<value>,
C<position>, and C<get_radius> croak on an invalid or freed handle.

=head2 Queries

Most query methods return a list of stored values (not handles) for
matching entries; C<query_radius_many> instead returns an arrayref of id-list
arrayrefs (see L</Batched radius queries>).  For C<query_knn>, results are in
nearest-first order.

    my @ids = $s->query_radius(x, y, r);         # 2D radius search
    my @ids = $s->query_radius(x, y, z, r);      # 3D radius search
    my @ids = $s->query_aabb(x0, y0, x1, y1);    # 2D axis-aligned box
    my @ids = $s->query_aabb(x0, y0, z0, x1, y1, z1);  # 3D box
    my @ids = $s->query_cell(x, y);              # single cell (2D)
    my @ids = $s->query_cell(x, y, z);           # single cell (3D)
    my @ids = $s->query_knn(x, y, k);            # k nearest (2D)
    my @ids = $s->query_knn(x, y, z, k);         # k nearest (3D)
    $s->each_in_radius(x, y, r, sub { my ($v) = @_; ... });    # 2D cb
    $s->each_in_radius(x, y, z, r, sub { my ($v) = @_; ... }); # 3D cb
    my $lists = $s->query_radius_many([ [x,y,r], [x,y,z,r] ]); # N radius queries, one lock