view release on metacpan or  search on metacpan

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

=head3 Region query cost

The cost of a region query scales with the number of grid cells covering
the query region, not with the number of matching points.  For
C<query_radius>, C<each_in_radius>, and each C<query_radius_many> sub-query that
is roughly S<(2 * radius / cell_size) ** dims> cells (similarly for C<query_aabb>,
which scans the cells spanning the box).  The scan runs while holding a
read lock.  An over-large radius relative to C<cell_size> therefore scans
many empty cells, wasting time and stalling concurrent writers that are
waiting for the lock.  Size C<cell_size> on the order of your typical
query radius so each query touches only a handful of cells.

As a safety net, any region query that would scan more than approximately
67 million cells (2**26) -- a C<query_radius>, C<query_aabb>,
C<each_in_radius>, or a C<query_radius_many> sub-query whose region spans that
many cells, a C<query_knn> that must walk that many cells across its expanding
shells, or a C<each_pair_within> / C<each_colliding_pair> whose per-entry
neighbourhood spans that many cells -- croaks with
a message containing the word "cells" rather than scanning unbounded.  If
your use case genuinely requires regions that large, increase C<cell_size>
so the same physical region maps to fewer cells.

=head2 Spherical worlds

For points on or above a sphere (planets, globes), construct with a body radius
and use the geo helpers; a separate cube-sphere scheme gives stable hierarchical
cell ids for chunking and level-of-detail.  Curvature needs no special handling:
with C<sphere> set, geo coordinates are converted to and from Cartesian in C, so
proximity is exact straight-line distance -- correct for surface and air entities
alike -- not a great-circle approximation.

=head3 Geo proximity

    my $s = Data::SpatialHash::Shared->new(undef, $max, 0, $cell, sphere => $R);

    my $h = $s->insert_geo($lat, $lon, $alt, $value);   # radians; alt above the surface
    $s->move_geo($h, $lat, $lon, $alt);
    my ($lat, $lon, $alt) = $s->position_geo($h);
    my @vals = $s->query_geo_radius($lat, $lon, $alt, $dist);   # $dist in world units

C<sphere> is the body radius -- distinct from a per-entry interaction radius --
and must be finite and greater than zero; it is stored in the map and restored
on reopen.  C<sphere> and C<wrap> are mutually exclusive (a sphere is not a flat
torus); passing both croaks.  Latitude and longitude are in B<radians> (C<lat>
in S<-pi/2 .. pi/2>, C<lon> in S<-pi .. pi>); C<alt> is height above the sphere
of radius C<$R>, so an entity lies at distance C<$R + $alt> from the centre.
Each geo method converts to Cartesian and delegates to the ordinary 3D engine,
so C<$dist> in C<query_geo_radius> is a true straight-line distance and must be
finite and non-negative.  At a pole, longitude is undefined and C<position_geo> reports it
as 0.  Calling a geo method on a map created without C<sphere> croaks.
C<insert_geo> returns a handle or C<undef> if the pool is exhausted (test with
C<defined> -- handle 0 is valid but false); C<move_geo> returns true, or false
for a freed/invalid handle; C<position_geo> croaks on a freed or invalid handle.

=head3 Cube-sphere cells

A direction (or lat/lon) maps to a hierarchical cell id on a cube-sphere: six
cube faces, each an equal-angle grid subdivided to a chosen B<level> (level 0 =
the whole face, level C<L> = C<2**L> cells per face edge, up to level 24).  The
ids are stateless integers independent of any stored data -- useful as chunk keys
for streaming and level-of-detail.

    my $cell = $s->cube_cell($x, $y, $z, $level);     # direction (need not be unit length)
    my $cell = $s->cube_cell_geo($lat, $lon, $level);
    my @adj  = $s->cube_neighbors($cell);             # 4 edge-adjacent cells, seam-aware
    my $up   = $s->cube_parent($cell);                # coarser cell (undef at level 0)
    my @kids = $s->cube_children($cell);              # 4 finer cells (empty at level 24)
    my $lvl  = $s->cube_level($cell);
    my ($x, $y, $z) = $s->cube_center($cell);         # cell centre as a unit vector
    my ($lat, $lon) = $s->cube_center_geo($cell);

A cell id packs C<(level, face, i, j)> into an unsigned integer, so cells at
different levels are different ids.  C<cube_neighbors> returns the four
edge-adjacent cells, correct across face seams; diagonal/corner neighbours are
not included.  These methods read no map state (any handle provides them), and a
malformed cell id croaks; a zero or non-finite direction yields an arbitrary but
valid cell.  The grid is near-uniform (equal-angle), not equal-area.

=head2 Introspection

    $s->count;        # live entry count
    $s->max_entries;  # capacity
    $s->num_buckets;  # bucket table size
    $s->cell_size;    # cell size in world units
    my @w = $s->world;  # wrap extents: (Wx,Wy) or (Wx,Wy,Wz); empty if not toroidal
    my $R = $s->sphere; # body radius (sphere => $R), or 0 if not a sphere map
    $s->stats;        # diagnostic hashref (see STATS)

=head2 Lifecycle

    $s->path;              # backing file path, or undef for anon/memfd
    $s->memfd;             # memfd fd (-1 for file-backed/anon)
    $s->sync;              # msync mmap to backing store
    $s->unlink;            # remove backing file
    Class->unlink($path);  # class-method form

C<sync> and C<unlink> croak on OS failure.

=head2 Event Loop Integration

    my $fd = $s->eventfd;         # lazy-create eventfd, returns fd
    $s->eventfd_set($fd);         # attach an external eventfd
    my $fd = $s->fileno;          # current eventfd fd, or -1
    $s->notify;                   # write 1 to eventfd (signal update)
    my $n = $s->eventfd_consume;  # read+reset eventfd counter

C<eventfd_set> attaches an external eventfd, closing the previously-attached fd
(such as one created by C<eventfd>) unless it is the same descriptor.
C<notify> returns false if no eventfd is attached, true after writing the
signal.  C<eventfd_consume> returns the counter as an integer, or C<undef> if
no eventfd is attached or nothing is pending (a spurious wakeup).

=head1 TUNING

Choose C<cell_size> close to your typical query radius.  A value too
small means many cells are scanned per radius query; a value too large
packs many entries into each cell and increases false-positive tests.

Choose C<num_buckets> to be a power of two slightly above the expected
peak live count; any value you pass is rounded up to the next power of
two.  The default (0 = auto) picks a power of two near C<max_entries>,