HMath.Geometry.Spatial¶

Description

Immutable point-cloud spatial indexes. IDs are original zero-based row indices, duplicate points are retained, range boxes are closed, and nearest results sort by (distance,ID). Up to 65536 points in dimensions 1..16 are accepted (quadtrees require 2D, octrees 3D). Hash cells are real hash buckets; KD, ball, quadrant, packed R-tree, and BVH nodes retain actual hierarchical bounds. Query pruning is exact, with a caller leaf budget for nearest search.

On this page¶

API	Purpose
SpatialKind	Explicit index construction algorithm; hash width must be positive finite.
SpatialHash	Declaration and type contract below.
KDTree	Declaration and type contract below.
BallTree	Declaration and type contract below.
Quadtree	Declaration and type contract below.
Octree	Declaration and type contract below.
RTree	Declaration and type contract below.
BVH	Declaration and type contract below.
PointCloud	Validated homogeneous finite cloud; a nonempty cloud defines its dimension.
pointCloud	Construct a nonempty cloud of at most 65536 points, with consistent dimensions.
cloudPoints	Original cloud observations.
SpatialIndex	Opaque checked spatial-search tree/hash index.
buildSpatialIndex	Build the named structure.
rangeQuery	Closed range search, sorted original IDs.
radiusQuery	Exact closed radius query; uses the index range query then Euclidean filtering.
NeighborQuery	A budgeted nearest-neighbor answer; False means unexplored leaves may improve the answer.
NeighborQuery	Declaration and type contract below.
queryNeighbors	Nearest candidate IDs paired with Euclidean distances, in increasing distance order.
queryLeaves	Number of visited spatial-index leaves charged to the query budget.
queryExhaustive	True only when unexplored nodes cannot improve the returned neighbors; False marks a budget-limited approximation.
nearestQuery	Given neighbor count k, positive leaf budget, index, then query point, search for nearest neighbors.

Documentation

SpatialKind

data SpatialKind Source #

Explicit index construction algorithm; hash width must be positive finite.

Constructors

SpatialHash Double
KDTree
BallTree
Quadtree
Octree
RTree
BVH

Instances

Instances details

Show SpatialKind Source #
Instance details Defined in HMath.Geometry.Spatial Methods showsPrec :: Int -> SpatialKind -> ShowS # show :: SpatialKind -> String # showList :: [SpatialKind] -> ShowS #
Eq SpatialKind Source #
Instance details Defined in HMath.Geometry.Spatial Methods (==) :: SpatialKind -> SpatialKind -> Bool # (/=) :: SpatialKind -> SpatialKind -> Bool #

PointCloud

data PointCloud Source #

Validated homogeneous finite cloud; a nonempty cloud defines its dimension.

Instances

Instances details

Show PointCloud Source #
Instance details Defined in HMath.Geometry.Spatial Methods showsPrec :: Int -> PointCloud -> ShowS # show :: PointCloud -> String # showList :: [PointCloud] -> ShowS #
Eq PointCloud Source #
Instance details Defined in HMath.Geometry.Spatial Methods (==) :: PointCloud -> PointCloud -> Bool # (/=) :: PointCloud -> PointCloud -> Bool #

pointCloud

pointCloud :: [PointND] -> Either MathError PointCloud Source #

Construct a nonempty cloud of at most 65536 points, with consistent dimensions.

cloudPoints

cloudPoints :: PointCloud -> [PointND] Source #

Original cloud observations.

SpatialIndex

data SpatialIndex Source #

Opaque checked spatial-search tree/hash index. Construction and query functions document dimension/work limits and exactness flags.

Instances

Instances details

Show SpatialIndex Source #
Instance details Defined in HMath.Geometry.Spatial Methods showsPrec :: Int -> SpatialIndex -> ShowS # show :: SpatialIndex -> String # showList :: [SpatialIndex] -> ShowS #
Eq SpatialIndex Source #
Instance details Defined in HMath.Geometry.Spatial Methods (==) :: SpatialIndex -> SpatialIndex -> Bool # (/=) :: SpatialIndex -> SpatialIndex -> Bool #

buildSpatialIndex

buildSpatialIndex :: SpatialKind -> PointCloud -> Either MathError SpatialIndex Source #

Build the named structure. RTree uses sort-tile-recursive leaf packing (fanout 8); BVH splits longest-axis medians; quadrant trees split cells at their midplanes with a depth limit of 64 for coincident/near-coincident data.

rangeQuery

rangeQuery :: SpatialIndex -> AABB -> Either MathError [Int] Source #

Closed range search, sorted original IDs. Hash queries inspect occupied bucket bounds, avoiding an unbounded Cartesian enumeration of empty cells.

radiusQuery

radiusQuery :: SpatialIndex -> PointND -> Double -> Either MathError [Int] Source #

Exact closed radius query; uses the index range query then Euclidean filtering.

NeighborQuery

data NeighborQuery Source #

A budgeted nearest-neighbor answer; False means unexplored leaves may improve the answer. Returned distances are exact Double Euclidean distances.

Constructors

NeighborQuery
Fields queryNeighbors :: [(Int, Double)] Nearest candidate IDs paired with Euclidean distances, in increasing distance order. queryLeaves :: Int Number of visited spatial-index leaves charged to the query budget. queryExhaustive :: Bool True only when unexplored nodes cannot improve the returned neighbors; False marks a budget-limited approximation.

Instances

Instances details

Show NeighborQuery Source #
Instance details Defined in HMath.Geometry.Spatial Methods showsPrec :: Int -> NeighborQuery -> ShowS # show :: NeighborQuery -> String # showList :: [NeighborQuery] -> ShowS #
Eq NeighborQuery Source #
Instance details Defined in HMath.Geometry.Spatial Methods (==) :: NeighborQuery -> NeighborQuery -> Bool # (/=) :: NeighborQuery -> NeighborQuery -> Bool #

nearestQuery

nearestQuery :: Int -> Int -> SpatialIndex -> PointND -> Either MathError NeighborQuery Source #

Given neighbor count k, positive leaf budget, index, then query point, search for nearest neighbors. Require matching finite coordinate dimension and 1<=k<=65536. The result reports neighbors, visited leaves and whether search was exhaustive; an exhausted budget is not an exact-neighbor guarantee.