Struct PointLocationGrid 

pub struct PointLocationGrid {
    pub resolution: usize,
    /* private fields */
}

Uniform grid over the Klein disk for O(1) point location.

The grid partitions the [-1, 1]² bounding box into resolution×resolution tiles. Each tile stores the ID of the power cell that owns its center. Query: map Klein coords → tile → owner ID → verify with half-plane check.

Fields

resolution: usize

Grid cells per axis

Implementations

impl PointLocationGrid

pub fn new(resolution: usize) -> Self

Create an empty grid with the given resolution and dimension. For dim > 2, the grid projects onto the first 2 coordinates.

pub fn with_dimension(resolution: usize, dimension: usize) -> Self

Create a grid for a specific embedding dimension.

A resolution of 0 is treated as 1 (a single degenerate cell): the grid spans [-1, 1] in each axis, so cell_size = 2 / resolution would divide by zero. A 1×1 grid holds no useful spatial structure but keeps the constructor total rather than panicking.

pub fn build(&mut self, sites: &[(String, KleinPoint)])

Build the grid from a set of KleinPoints by brute-force nearest power distance.

For each tile center inside the Klein disk, find the site with minimum power distance and assign that tile to that site’s node_id.

pub fn query(&self, query_klein: &FixedVector) -> Option<&str>

Query the grid for the node owning the tile containing the given Klein point.

Returns None if the point is outside the disk or the tile is unassigned.

pub fn update_insert( &mut self, parent_id: &str, new_id: &str, new_site: &KleinPoint, parent_site: &KleinPoint, )

Update the grid after inserting a new leaf node.

Only tiles currently assigned to the parent need checking. For each such tile, if the tile center is closer to the new leaf in power distance, reassign it.

pub fn update_delete(&mut self, deleted_id: &str, parent_id: &str)

Update the grid after deleting a leaf node.

All tiles assigned to the deleted node are reassigned to the parent.

pub fn assigned_tile_count(&self) -> usize

Get the number of assigned tiles (tiles inside the disk with an owner).

pub fn resolution(&self) -> usize

Get the grid resolution.

Trait Implementations

impl Debug for PointLocationGrid

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.