Data-SpatialHash-Shared
view release on metacpan or search on metacpan
if (v < 2) return 1;
return 1u << (32 - __builtin_clz(v - 1));
}
/* Largest magnitude a cell index may take. Clamping to +/-2^62 keeps cells far
* inside int64 range, so the cell-box and knn-shell loops -- which expand from
* center +/- g over a span already capped at SPH_MAX_QUERY_CELLS -- can never
* overflow int64. 2^62 is far beyond any coordinate a double represents exactly
* (2^53), so nothing reachable is lost. */
#define SPH_CELL_LIMIT ((int64_t)1 << 62)
/* Floor one coordinate to its integer cell. Defined for every double: NaN/Inf
* map to cell 0, and the result is clamped to +/-SPH_CELL_LIMIT, both to avoid
* the UB of converting an out-of-range double to int64_t and to bound the
* query loops (see SPH_CELL_LIMIT). */
static inline int64_t sph_floor_cell(double v, double cs) {
double d = floor(v / cs);
if (!isfinite(d)) return 0;
if (d >= (double)SPH_CELL_LIMIT) return SPH_CELL_LIMIT;
if (d <= -(double)SPH_CELL_LIMIT) return -SPH_CELL_LIMIT;
return (int64_t)d;
}
/* direction (need not be unit) -> cell id at level [0, SPH_CUBE_MAX_LEVEL] */
static inline uint64_t sph_cube_cell(const double dir[3], int level) {
double x = dir[0], y = dir[1], z = dir[2];
double ax = fabs(x), ay = fabs(y), az = fabs(z);
int face; double mag, s, t;
if (ax >= ay && ax >= az) { mag = ax; face = (x >= 0) ? 0 : 1; s = y / mag; t = z / mag; }
else if (ay >= az) { mag = ay; face = (y >= 0) ? 2 : 3; s = x / mag; t = z / mag; }
else { mag = az; face = (z >= 0) ? 4 : 5; s = x / mag; t = y / mag; }
double u = atan(s) / SPH_PI_4; /* equal-angle warp to [-1,1] */
double v = atan(t) / SPH_PI_4;
if (!isfinite(u)) u = 0.0; /* dir==0 -> s,t NaN; keep defined */
if (!isfinite(v)) v = 0.0;
int64_t N = (int64_t)1 << level;
int64_t i = (int64_t)floor((u + 1.0) * 0.5 * (double)N);
int64_t j = (int64_t)floor((v + 1.0) * 0.5 * (double)N);
if (i < 0) i = 0; else if (i >= N) i = N - 1;
if (j < 0) j = 0; else if (j >= N) j = N - 1;
return ((uint64_t)level << 51) | ((uint64_t)face << 48)
| ((uint64_t)i << 24) | (uint64_t)j;
}
}
if (collide) { if (maxr <= 0.0) return SPH_Q_OK; } /* no radii -> points never collide */
else if (!(fixed_r > 0.0)) return SPH_Q_OK; /* non-positive radius -> nothing */
int dims = (h->world[2] > 0.0 || has3d) ? 3 : 2;
for (uint32_t a = 0; a < me; a++) {
if (!sph_is_live(h, a)) continue;
const double *pa = h->entries[a].pos;
double ra = h->entries[a].radius;
double reach_d = ceil((collide ? (ra + maxr) : fixed_r) / cs);
/* defensive: the API validates radii, but a corrupt stored radius could make this
NaN, which would slip past the cap check below (NaN >= X is false) into the cast */
if (!(reach_d >= 0)) reach_d = 0;
if (reach_d >= (double)SPH_MAX_QUERY_CELLS) return SPH_Q_TOOBIG; /* avoid int64 overflow */
int64_t reach = (int64_t)reach_d;
int64_t ac[3]; sph_cell_raw(h, pa, ac);
int64_t cnt[3] = { 1, 1, 1 };
uint64_t cells = 1;
for (int i = 0; i < dims; i++) {
uint64_t span = (uint64_t)(2 * reach + 1);
if (h->wrap_cells[i] > 0 && span > (uint64_t)h->wrap_cells[i]) span = (uint64_t)h->wrap_cells[i];
if (span >= (uint64_t)SPH_MAX_QUERY_CELLS) return SPH_Q_TOOBIG;
t/14-extreme.t view on Meta::CPAN
use strict; use warnings; use Test::More;
use Data::SpatialHash::Shared;
# Non-finite / extreme coordinates must not crash or invoke UB (cells clamp to
# +/-2^62). Plus empty-map queries and exact knn ties.
# extreme + non-finite coordinates (use string->NV to be safe on longdouble perls)
{
my $s = Data::SpatialHash::Shared->new(undef, 100, 0, 1.0);
my $inf = "Inf" + 0;
my $nan = "NaN" + 0;
ok defined($s->insert($inf, 0, 1)), 'insert(+Inf) does not crash';
ok defined($s->insert($nan, 0, 2)), 'insert(NaN) does not crash';
ok defined($s->insert(1e300, 1e300, 3)), 'insert(1e300) does not crash';
ok defined($s->insert(-1e300, 0, 4)), 'insert(-1e300) does not crash';
is $s->count, 4, 'all extreme inserts stored';
ok eval { $s->query_radius(0, 0, 5); 1 }, 'normal query alongside extreme entries ok';
# the 1e300 entry clamps to the same far cell as a 1e300 knn center, so it is
# found at g=0 -- no unbounded shell walk
is_deeply [$s->query_knn(1e300, 1e300, 1)], [3], 'knn at an extreme coordinate finds the clamped-cell entry';
}
# empty-map queries
my $f = Data::SpatialHash::Shared->new(undef, 10, 0, 1.0); # no sphere => geo disabled
eval { $f->insert_geo(0, 0, 0, 1) }; like $@, qr/sphere/, 'insert_geo croaks without sphere';
eval { $f->move_geo(0, 0, 0, 0) }; like $@, qr/sphere/, 'move_geo croaks without sphere';
eval { $f->position_geo(0) }; like $@, qr/sphere/, 'position_geo croaks without sphere';
eval { $f->query_geo_radius(0, 0, 0, 1) }; like $@, qr/sphere/, 'query_geo_radius croaks without sphere';
eval { $s->query_geo_radius(0, 0, 0, -1) }; like $@, qr/dist/, 'query_geo_radius croaks on negative dist';
eval { Data::SpatialHash::Shared->new(undef, 10, 0, 1.0, sphere => 0) }; like $@, qr/sphere/, 'sphere => 0 croaks';
eval { Data::SpatialHash::Shared->new(undef, 10, 0, 1.0, sphere => -5) }; like $@, qr/sphere/, 'sphere => -5 croaks';
eval { Data::SpatialHash::Shared->new(undef, 10, 0, 1.0, sphere => ("NaN" + 0)) }; like $@, qr/sphere/, 'sphere => NaN croaks';
eval { Data::SpatialHash::Shared->new(undef, 10, 0, 1.0, sphere => ("Inf" + 0)) }; like $@, qr/sphere/, 'sphere => Inf croaks';
eval { Data::SpatialHash::Shared->new(undef, 10, 0, 1.0, sphere => 100, wrap => [4, 4]) }; like $@, qr/mutually exclusive/, 'sphere + wrap croaks (incompatible topologies)';
# ---- sphere_radius persists across reopen ----
my $path = "/tmp/sph-geo-$$.bin";
unlink $path;
{
my $w = Data::SpatialHash::Shared->new($path, 100, 0, 1000, sphere => 1234.5);
$w->insert_geo(0.1, 0.2, 0, 7); # alt 0 -> on the radius-1234.5 sphere
}
xt/invalid_args.t view on Meta::CPAN
eval { $s->move($s->insert(1,1,1), 1, 2, 3, 4) }; ok $@, 'move too many args';
eval { $s->query_radius(1,2) }; ok $@, 'query_radius too few args';
eval { $s->query_radius(0,0,-1) }; ok $@, 'negative radius';
eval { $s->query_knn(0,0,0) }; ok $@, 'k=0';
eval { $s->query_aabb(1,2,3) }; ok $@, 'aabb wrong arity';
eval { $s->query_cell(1) }; ok $@, 'query_cell wrong arity';
eval { $s->each_in_radius(0,0,5,'notcode') }; ok $@, 'each_in_radius non-coderef';
eval { $s->each_in_radius(0,0,-1,sub{}) }; ok $@, 'each_in_radius negative radius';
eval { $s->value(1<<30) }; ok $@, 'huge handle croaks';
eval { Data::SpatialHash::Shared->new(undef, 100, 0, -1) }; ok $@, 'negative cell_size';
# non-finite (Inf/NaN) rejected wherever a finite radius/extent is required -- an
# Inf radius used to silently scan only cell (0,0,0) and return a wrong subset
eval { $s->query_radius(0,0, "Inf"+0) }; ok $@, 'query_radius Inf radius croaks';
eval { $s->query_radius(0,0, "NaN"+0) }; ok $@, 'query_radius NaN radius croaks';
eval { $s->each_in_radius(0,0, "Inf"+0, sub{}) }; ok $@, 'each_in_radius Inf radius croaks';
eval { $s->each_pair_within("Inf"+0, sub{}) }; ok $@, 'each_pair_within Inf max_r croaks';
eval { $s->insert(1,2,3,4, "Inf"+0) }; ok $@, 'insert Inf radius croaks';
eval { Data::SpatialHash::Shared->new(undef, 100, 0, "Inf"+0) }; ok $@, 'Inf cell_size croaks';
{ my $h = $s->insert(7,7,9); eval { $s->set_radius($h, "Inf"+0) }; ok $@, 'set_radius Inf radius croaks'; }
{ my $g = Data::SpatialHash::Shared->new(undef, 100, 0, 50000, sphere => 6371000);
eval { $g->query_geo_radius(0,0,0, "Inf"+0) }; ok $@, 'query_geo_radius Inf dist croaks'; }
ok defined($s->insert(1,2,3)), 'sane insert still works';
# query_knn enforces the cell cap via shell expansion (a distinct code path from
# the upfront span check used by query_radius/query_aabb)
( run in 0.591 second using v1.01-cache-2.11-cpan-9581c071862 )