Class ClusterCentroidGrid

Namespace

LansMap.Core.Markers

Grid spatial index over densely numbered ground points, backed entirely by flat pooled arrays: an open-addressed cell table, one shared bucket arena, and per-id side arrays. Serves the cluster build's two internal grids, where ids are consecutive from zero and no point has altitude.

public sealed class ClusterCentroidGrid

Inheritance

object

ClusterCentroidGrid

Remarks

Same query contract as MarkerSpatialIndex minus the altitude fallback: Query(in MercatorBounds, List<int>) visits only the cells a rect touches, filters each candidate against the rect exactly, and appends survivors in cell-scan order (y outer, x inner) and, within a cell, in bucket order. Add appends to a bucket, Remove swaps the bucket's last entry into the freed slot, and UpdatePosition(int, double, double) is a remove followed by an add - the identical ordering rules MarkerSpatialIndex follows, so the two produce the same result sequence for the same operation sequence, ties included.

Nothing here allocates per cell or per point once the arrays have grown to a workload's size: ResetForReuse(double) rewinds the arena and the table instead of releasing them, so a caller that runs many passes through one instance pays the growth once. Ids must be small non-negative integers - the side arrays are indexed by id, so a sparse id space costs memory proportional to the largest id, not to the number of points.

Not thread safe. Cell size is set by ResetForReuse(double) and is a world-mercator distance.

Constructors

ClusterCentroidGrid(double, int)

public ClusterCentroidGrid(double cellSize, int initialCapacity = 64)

Parameters

cellSize double

Grid cell width and height in normalized mercator units. Must be positive and finite.

initialCapacity int

Point count to preallocate for. A sizing hint only; the grid grows correctly from a smaller one.

Fields

DefaultCapacity

Point count to preallocate when constructing a new grid.

public const int DefaultCapacity = 64

Field Value

int

Properties

CellSize

The current grid cell size in normalized mercator units.

public double CellSize { get; }

Property Value

double

Count

Points currently in the grid.

public int Count { get; }

Property Value

int

LastQueryCellsVisited

Cells the most recent Query(in MercatorBounds, List<int>) stepped over, occupied or not. Exists so a caller or a test can verify the query bounded its work to the rect instead of walking the grid.

public int LastQueryCellsVisited { get; }

Property Value

int

OccupiedCellCount

Cells holding at least one point right now. Cells emptied by a removal are not counted.

public int OccupiedCellCount { get; }

Property Value

int

Methods

Add(int, double, double)

Starts tracking a point at x,y in normalized mercator units.

public void Add(int id, double x, double y)

Parameters

id int

Caller-chosen identity, used directly as an array index, so it must be non-negative and should be dense.

x double

Normalized mercator x.

y double

Normalized mercator y.

Exceptions

ArgumentOutOfRangeException

id is negative.

InvalidOperationException

id is already tracked.

FindNearest(double, double, double, double[], double[])

The tracked id closest to px,py among candidates strictly inside a radius-wide square around it, measured through refX/ refY rather than this grid's own stored positions - or -1 if none qualify.

public int FindNearest(double px, double py, double radius, double[] refX, double[] refY)

Parameters

px double

Query point normalized mercator X.

py double

Query point normalized mercator Y.

radius double

Half-width of the candidate rect and the strict distance cutoff.

refX double[]

Per-id X coordinates used for the distance test, indexable by every id this grid can return as a candidate. Caller-owned; may differ from this grid's own stored X for an id (see remarks).

refY double[]

Per-id Y coordinates, same contract as refX.

Returns

int

Remarks

Fuses the two-pass Query-then-scan sequence into one: the rect filter still runs against this grid's own stored positions (its candidate set can differ from a filter on refX/ refY when the two coordinate sources disagree by less than a cell), while the distance comparison that decides the winner reads the reference arrays. A caller with reference coordinates bitwise equal to its stored positions gets the exact result Query(in MercatorBounds, List<int>) plus a linear scan would. Updates LastQueryCellsVisited the same way Query(in MercatorBounds, List<int>) does.

Query(in MercatorBounds, List<int>)

Fills results (cleared first) with every tracked point inside bounds, visiting only the cells the rect touches.

public void Query(in MercatorBounds bounds, List<int> results)

Parameters

bounds MercatorBounds

Query rect in the same unwrapped normalized mercator frame the points were added in. A non-finite bound returns nothing rather than flooring an unspecified cast into an unbounded cell range.

results List<int>

Caller-owned output list; cleared first.

Remove(int)

Stops tracking a point. Idempotent: an id that is not tracked is ignored.

public void Remove(int id)

Parameters

id int

ResetForReuse(double)

Drops every point and rebases CellSize, so one instance can serve an unrelated pass without releasing the arrays it already grew.

public void ResetForReuse(double cellSize)

Parameters

cellSize double

Remarks

Destructive: every id this grid was tracking stops being findable, with no notification. Intended for a grid a single caller owns end to end and repopulates before its next use.

UpdatePosition(int, double, double)

Moves a tracked point, re-bucketing it if that changes its cell. A stale id - not currently tracked - is ignored rather than an error.

public void UpdatePosition(int id, double x, double y)

Parameters

id int

The point to move.

x double

New normalized mercator x.

y double

New normalized mercator y.