Python API Reference

Note

The sdsl package must be installed (pip install ./sdsl) before building these docs so that autodoc can import the compiled extension.

Core

sdsl.seed(seed: int) → None: Seed the global random number generator used by SDSL.

Configurations

class sdsl.R2

D-dimensional configuration (point in C-space ≅ R^D).

Elements are accessed with q[i] and the usual comparison operators perform component-wise tests (not a total order).

__add__: Add a scalar delta to every coordinate.

__getitem__: Return the i-th coordinate.

__repr__

__setitem__: Set the i-th coordinate.

__sub__: Subtract a scalar delta from every coordinate.

class sdsl.R3

D-dimensional configuration (point in C-space ≅ R^D).

Elements are accessed with q[i] and the usual comparison operators perform component-wise tests (not a total order).

__add__: Add a scalar delta to every coordinate.

__getitem__: Return the i-th coordinate.

__repr__

__setitem__: Set the i-th coordinate.

__sub__: Subtract a scalar delta from every coordinate.

class sdsl.R4

D-dimensional configuration (point in C-space ≅ R^D).

Elements are accessed with q[i] and the usual comparison operators perform component-wise tests (not a total order).

__add__: Add a scalar delta to every coordinate.

__getitem__: Return the i-th coordinate.

__repr__

__setitem__: Set the i-th coordinate.

__sub__: Subtract a scalar delta from every coordinate.

Voxels

class sdsl.Voxel_R2

Axis-aligned bounding box (voxel) in C-space ≅ R^D.

Defined by a bottom_left and top_right Configuration. Used both as the initial search region and as the result type of localize_omp_forkjoin_3d().

property bottom_left: Lower corner of the voxel.

expand_self

bottom_left -= delta, top_right += delta.

Type:: Expand the voxel in-place

midpoint: Return the centre configuration of the voxel.

split

Overloaded function.

split(self) -> list[sdsl._sdsl.Voxel_R2]

Split into 2^D equal sub-voxels. Returns a list of child voxels.

split(self, midpoint: sdsl._sdsl.R2) -> list[sdsl._sdsl.Voxel_R2]

Split into 2^D sub-voxels at a given midpoint. Returns a list of child voxels.

property top_right: Upper corner of the voxel.

class sdsl.Voxel_R3

Axis-aligned bounding box (voxel) in C-space ≅ R^D.

Defined by a bottom_left and top_right Configuration. Used both as the initial search region and as the result type of localize_omp_forkjoin_3d().

property bottom_left: Lower corner of the voxel.

expand_self

bottom_left -= delta, top_right += delta.

Type:: Expand the voxel in-place

midpoint: Return the centre configuration of the voxel.

split

Overloaded function.

split(self) -> list[sdsl._sdsl.Voxel_R3]

Split into 2^D equal sub-voxels. Returns a list of child voxels.

split(self, midpoint: sdsl._sdsl.R3) -> list[sdsl._sdsl.Voxel_R3]

Split into 2^D sub-voxels at a given midpoint. Returns a list of child voxels.

property top_right: Upper corner of the voxel.

class sdsl.Voxel_R4

Axis-aligned bounding box (voxel) in C-space ≅ R^D.

Defined by a bottom_left and top_right Configuration. Used both as the initial search region and as the result type of localize_omp_forkjoin_3d().

property bottom_left: Lower corner of the voxel.

expand_self

bottom_left -= delta, top_right += delta.

Type:: Expand the voxel in-place

midpoint: Return the centre configuration of the voxel.

split

Overloaded function.

split(self) -> list[sdsl._sdsl.Voxel_R4]

Split into 2^D equal sub-voxels. Returns a list of child voxels.

split(self, midpoint: sdsl._sdsl.R4) -> list[sdsl._sdsl.Voxel_R4]

Split into 2^D sub-voxels at a given midpoint. Returns a list of child voxels.

property top_right: Upper corner of the voxel.

Environments

class sdsl.Environment

Abstract base class for 3-DOF (x, y, θ) environments.

All concrete environment classes inherit from this.

contains: Return True if configuration q is inside the environment.

intersects: Return True if voxel intersects the occupied region.

class sdsl.Env_R2_Arrangement

Bases: Environment

2-D planar environment built from a polygon/arrangement of line segments.

Internally uses a CGAL arrangement and a segment tree for exact and efficient ray-casting. The configuration space is 3-D: (x, y, θ).

Example:

import numpy as np, sdsl
pts = np.loadtxt('map.poly')
segs = np.column_stack([pts, np.roll(pts, -1, axis=0)])
env = sdsl.Env_R2_Arrangement(segs)

bounding_box: Return a Voxel_R3 covering the full (x, y, θ) configuration space.

collision_detection: Return True if the straight-line path from q1 to q2 crosses any wall segment.

contains: Return True if (q[0], q[1]) is inside the polygon.

get_representation: Return the segment array as an (N, 4) NumPy array [x1, y1, x2, y2].

hausdorff_distance: Hausdorff distance between the ray from q and the nearest wall segment.

intersects: Return True if voxel intersects any wall segment.

measure_distance: Cast a ray from (q[0], q[1]) in direction q[2] and return the hit distance.

voxel_hausdorff_distance: Worst-case Hausdorff distance over all configurations in voxel.

class sdsl.Env_2D_PCD

Bases: Environment

2-D point-cloud environment for 3-DOF (x, y, θ) localization.

Builds an AABB tree and KD-tree over a set of 2-D points (e.g., a sampled obstacle boundary). Suitable when the map is given as a PCD rather than a clean polygon.

Example:

import numpy as np, sdsl
pts = np.loadtxt('cloud.txt')  # (N, 2)
env = sdsl.Env_2D_PCD(pts)

bounding_box: Return a Voxel_R3 covering the full configuration space.

collision_detection: Return True if the straight-line path from q1 to q2 crosses any point in the cloud.

contains: Return True if (q[0], q[1]) is inside the point cloud hull.

forward: Apply the forward map F_dg(V) as described in the SDSL paper.

get_representation: Return the point cloud as an (N, 2) NumPy array.

hausdorff_distance: Hausdorff distance from q to the nearest point.

intersects: Return True if voxel intersects the point cloud.

measure_distance: Ray-cast distance from (q[0], q[1]) in direction q[2].

voxel_hausdorff_distance: Worst-case Hausdorff distance over all configurations in voxel.

class sdsl.Env_3D_PCD

Bases: Environment4

3-D point-cloud environment for 4-DOF (x, y, z, θ) localization.

Builds an AABB tree and KD-tree over a set of 3-D points.

Example:

import numpy as np, sdsl
pts = np.loadtxt('cloud3d.txt')  # (N, 3)
env = sdsl.Env_3D_PCD(pts)

bounding_box: Return a Voxel_R4 covering the full configuration space.

contains: Return True if q is inside the point cloud hull.

forward: Apply the forward map F_dg(V) as described in the SDSL paper.

get_representation: Return the point cloud as an (N, 3) NumPy array.

hausdorff_distance: Hausdorff distance from q to the nearest point.

intersects: Return True if voxel intersects the point cloud.

measure_distance: Ray-cast distance from the 3-D pose q.

voxel_hausdorff_distance: Worst-case Hausdorff distance over all configurations in voxel.

Predicates

class sdsl.Predicate_Fwd2D_Arr

Voxel-intersection predicate for planar (x, y, theta) robots.

Implements the k-k’ dynamic gap guarantee: given k measurements of which at least k’ are valid, the predicate provably retains the ground-truth voxel while pruning all others. Small measurement noise is handled via error_bound.

Example:

pred = sdsl.Predicate_Fwd2D_Arr(
    env, odometry, measurements,
    kk_prime_ratio=0.7, error_bound=0.05,
)
voxels = sdsl.localize_omp_forkjoin_3d(bbox, pred, recursion_depth=8)

forward: Compute F_dg(V) — the forward-mapped voxel for measurement d and odometry g.

class sdsl.Predicate_AlwaysTrue_3d

Trivial predicate that accepts every voxel.

Useful for exhaustive space enumeration and benchmarking — passing this to localize_omp_forkjoin_3d() simply subdivides the entire bounding box without pruning.

class sdsl.Predicate_AlwaysTrue_4d

Trivial predicate that accepts every voxel.

Useful for exhaustive space enumeration and benchmarking — passing this to localize_omp_forkjoin_3d() simply subdivides the entire bounding box without pruning.

Localization

sdsl.localize_omp_forkjoin_3d(bounding_box: sdsl._sdsl.Voxel_R3, predicate: sdsl._sdsl.Predicate_AlwaysTrue_3d, recursion_depth: int, timeout: float = 0.0, verbose: bool = False) → list[sdsl._sdsl.Voxel_R3]

sdsl.localize_omp_forkjoin_3d(bounding_box: sdsl._sdsl.Voxel_R3, predicate: sdsl._sdsl.Predicate_Fwd2D_Arr, recursion_depth: int, timeout: float = 0.0, verbose: bool = False) → list[sdsl._sdsl.Voxel_R3]

Run the parallel fork-join localization algorithm.

Recursively subdivides bounding_box into 2^D sub-voxels, keeping only those accepted by predicate. Subdivision continues for recursion_depth iterations (or until timeout seconds elapse).

Parameters:

bounding_box (Voxel) – The initial search region (use env.bounding_box()).
predicate (callable) – A predicate that accepts a voxel and returns True if it may contain the robot’s true configuration.
recursion_depth (int) – Number of subdivision iterations. Resolution ≈ bbox / 2^depth.
timeout (float, optional) – Stop early after this many seconds (0 = no limit).
verbose (bool, optional) – Print iteration count and timing to stdout.

Returns:

Candidate voxels that survived all predicate checks.

Return type:

list[Voxel]

sdsl.localize_omp_forkjoin_4d(bounding_box: sdsl._sdsl.Voxel_R4, predicate: sdsl._sdsl.Predicate_AlwaysTrue_4d, recursion_depth: int, timeout: float = 0.0, verbose: bool = False) → list[sdsl._sdsl.Voxel_R4]

Run the parallel fork-join localization algorithm.

Recursively subdivides bounding_box into 2^D sub-voxels, keeping only those accepted by predicate. Subdivision continues for recursion_depth iterations (or until timeout seconds elapse).

Parameters:

bounding_box (Voxel) – The initial search region (use env.bounding_box()).
predicate (callable) – A predicate that accepts a voxel and returns True if it may contain the robot’s true configuration.
recursion_depth (int) – Number of subdivision iterations. Resolution ≈ bbox / 2^depth.
timeout (float, optional) – Stop early after this many seconds (0 = no limit).
verbose (bool, optional) – Print iteration count and timing to stdout.

Returns:

Candidate voxels that survived all predicate checks.

Return type:

list[Voxel]

Simulation utilities

sdsl.loaders.load_poly_as_pcd.load_poly_as_pcd(path, spacing)[source]