jitfields.distance

This module implements functions that compute distances to raster masks, 2D polygons, 3D triangular meshes, and spline-encoded curves.

Functions:

Name	Description
euclidean_distance_transform	Compute the Euclidean distance transform of a binary image. Alias: edt.
l1_distance_transform	Compute the L1 distance transform of a binary image. Alias: l1dt.
signed_distance_transform	Compute the signed Euclidean distance transform of a binary image. Alias: sdt.
spline_distance_table	Compute the minimum distance from a set of points to a 1D spline (dicitonary search).
spline_distance_brent	Compute the minimum distance from a set of points to a 1D spline (derivative-free optimization). In-place: spline_distance_brent_.
spline_distance_gaussnewton	Compute the minimum distance from a set of points to a 1D spline (second order optimization). In-place: spline_distance_gaussnewton. Aliases: spline_dt, spline_dt_.
mesh_distance	Compute the minimum distance from a set of points to a triangular mesh. Alias: mesh_dt.
mesh_distance_signed	Compute the signed minimum distance from a set of points to a triangular mesh. Alias: mesh_sdt.
mesh_sdt_extra	mesh_distance_signed + also return the vertex nearest (in geodesic distance) to each point.

euclidean_distance_transform

euclidean_distance_transform(x, ndim=None, vx=1, dtype=None)

Compute the Euclidean distance transform of a binary image

Parameters:

Name	Type	Description	Default
x	`(..., *spatial) tensor`	Input tensor, with shape (..., *spatial).	required
ndim	`int`	Number of spatial dimensions. Default: all.	`x.ndim`
vx	`[sequence of] float`	Voxel size.	1
dtype	`torch.dtype`	Ouptut data type. Default is same as x if it has a floating point data type, else torch.get_default_dtype().	None

Returns:

Name	Type	Description
d	`(..., *spatial) tensor`	Distance map, with shape (..., *spatial).

References

1. Felzenszwalb, P.F. and Huttenlocher, D.P., 2012. Distance transforms of sampled functions. Theory of computing, 8(1), pp.415-428.

   @article{felzenszwalb2012distance,
       title={Distance transforms of sampled functions},
       author={Felzenszwalb, Pedro F and Huttenlocher, Daniel P},
       journal={Theory of computing},
       volume={8},
       number={1},
       pages={415--428},
       year={2012},
       publisher={Theory of Computing Exchange},
       url={https://www.theoryofcomputing.org/articles/v008a019/v008a019.pdf}
   }
   

l1_distance_transform

l1_distance_transform(x, ndim=None, vx=1, dtype=None)

Compute the L1 distance transform of a binary image

Parameters:

Name	Type	Description	Default
x	`(..., *spatial) tensor`	Input tensor, with shape (..., *spatial).	required
ndim	`int`	Number of spatial dimensions. Default: all.	`x.ndim`
vx	`[sequence of] float`	Voxel size.	1
dtype	`torch.dtype`	Ouptut data type. Default is same as x if it has a floating point data type, else torch.get_default_dtype().	None

Returns:

Name	Type	Description
d	`(..., *spatial) tensor`	Distance map, with shape (..., *spatial).

References

1. Felzenszwalb, P.F. and Huttenlocher, D.P., 2012. Distance transforms of sampled functions. Theory of computing, 8(1), pp.415-428.

   @article{felzenszwalb2012distance,
       title={Distance transforms of sampled functions},
       author={Felzenszwalb, Pedro F and Huttenlocher, Daniel P},
       journal={Theory of computing},
       volume={8},
       number={1},
       pages={415--428},
       year={2012},
       publisher={Theory of Computing Exchange},
       url={https://www.theoryofcomputing.org/articles/v008a019/v008a019.pdf}
   }
   

signed_distance_transform

signed_distance_transform(x, ndim=None, vx=1, dtype=None)

Compute the signed Euclidean distance transform of a binary image

Parameters:

Name	Type	Description	Default
x	`(..., *spatial) tensor`	Input tensor, with shape (..., *spatial).	required
ndim	`int`	Number of spatial dimensions. Default: all.	`x.ndim`
vx	`[sequence of] float`	Voxel size.	1
dtype	`torch.dtype`	Ouptut data type. Default is same as x if it has a floating point data type, else torch.get_default_dtype().	None

Returns:

Name	Type	Description
d	`(..., *spatial) tensor`	Distance map, with shape (..., *spatial).

References

1. Felzenszwalb, P.F. and Huttenlocher, D.P., 2012. Distance transforms of sampled functions. Theory of computing, 8(1), pp.415-428.

   @article{felzenszwalb2012distance,
       title={Distance transforms of sampled functions},
       author={Felzenszwalb, Pedro F and Huttenlocher, Daniel P},
       journal={Theory of computing},
       volume={8},
       number={1},
       pages={415--428},
       year={2012},
       publisher={Theory of Computing Exchange},
       url={https://www.theoryofcomputing.org/articles/v008a019/v008a019.pdf}
   }
   

spline_distance_table

spline_distance_table(loc, coeff, steps=None, order=3, bound='dct2', square=False)

Compute the minimum distance from a set of points to a 1D spline

Parameters:

Name	Type	Description	Default
loc	`(..., D) tensor`	Point set.	required
coeff	`(..., N, D) tensor`	Spline coefficients encoding the location of the 1D spline.	required
steps	`int or (..., K) tensor`	Number of time steps to try, or list of time steps to try.	None
order	1..7	Spline order.	1..7
bound	BoundType	Boundary conditions of the spline.	'dct2'
square	bool	Return the squared Euclidean distance.	False

Returns:

Name	Type	Description
dist	`(...) tensor`	Distance from each point in the set to its closest point on the spline
time	`(...) tensor`	Time of the closest point on the spline

spline_distance_brent_

spline_distance_brent_(dist, time, loc, coeff, max_iter=128, tol=1e-06, step_size=0.01, order=3, bound='dct2', square=False)

Compute the minimum distance from a set of points to a 1D spline (inplace)

Parameters:

Name	Type	Description	Default
dist	`(...) tensor`	Initial distance from each point in the set to its closest point on the spline	required
time	`(...) tensor`	Initial time of the closest point on the spline	required
loc	`(..., D) tensor`	Point set.	required
coeff	`(..., N, D) tensor`	Spline coefficients encoding the location of the 1D spline.	required
max_iter	int	Number of optimization steps.	128
tol	float	Tolerance for early stopping	1e-06
step_size	float	Initial search size.	0.01
order	1..7	Spline order.	1..7
bound	BounLike	Boundary conditions of the spline.	'dct2'
square	bool	Return the squared Euclidean distance.	False

Returns:

Name	Type	Description
dist	`(...) tensor`	Distance from each point in the set to its closest point on the spline
time	`(...) tensor`	Time of the closest point on the spline

spline_distance_brent

spline_distance_brent(loc, coeff, max_iter=128, tol=1e-06, step_size=0.01, order=3, bound='dct2', square=False, steps=None)

Compute the minimum distance from a set of points to a 1D spline

Parameters:

Name	Type	Description	Default
loc	`(..., D) tensor`	Point set.	required
coeff	`(..., N, D) tensor`	Spline coefficients encoding the location of the 1D spline.	required
max_iter	int	Number of optimization steps.	128
tol	float	Tolerance for early stopping	1e-06
step_size	float	Initial search size.	0.01
order	1..7	Spline order.	1..7
bound	BoundType	Boundary conditions of the spline.	'dct2'
square	bool	Return the squared Euclidean distance.	False
steps	int	Number of steps used in the table-based initialisation.	None

Returns:

Name	Type	Description
dist	`(...) tensor`	Distance from each point in the set to its closest point on the spline
time	`(...) tensor`	Time of the closest point on the spline

spline_distance_gaussnewton_

spline_distance_gaussnewton_(dist, time, loc, coeff, max_iter=16, tol=1e-06, order=3, bound='dct2', square=False)

Compute the minimum distance from a set of points to a 1D spline (inplace)

Parameters:

Name	Type	Description	Default
dist	`(...) tensor`	Initial distance from each point in the set to its closest point on the spline	required
time	`(...) tensor`	Initial time of the closest point on the spline	required
loc	`(..., D) tensor`	Point set.	required
coeff	`(..., N, D) tensor`	Spline coefficients encoding the location of the 1D spline.	required
max_iter	int	Number of optimization steps.	16
tol	float	Tolerance for early stopping	1e-06
order	1..7	Spline order.	1..7
bound	BoundType	Boundary conditions of the spline.	'dct2'
square	bool	Return the squared Euclidean distance.	False

Returns:

Name	Type	Description
dist	`(...) tensor`	Distance from each point in the set to its closest point on the spline
time	`(...) tensor`	Time of the closest point on the spline

spline_distance_gaussnewton

spline_distance_gaussnewton(loc, coeff, max_iter=16, tol=1e-06, order=3, bound='dct2', square=False, steps=None)

Compute the minimum distance from a set of points to a 1D spline

Parameters:

Name	Type	Description	Default
loc	`(..., D) tensor`	Point set.	required
coeff	`(..., N, D) tensor`	Spline coefficients encoding the location of the 1D spline.	required
max_iter	int	Number of optimization steps.	16
tol	float	Tolerance for early stopping	1e-06
order	1..7	Spline order.	1..7
bound	BoundType	Boundary conditions of the spline.	'dct2'
square	bool	Return the squared Euclidean distance.	False
steps	int	Number of steps used in the table-based initialisation.	None

Returns:

Name	Type	Description
dist	`(...) tensor`	Distance from each point in the set to its closest point on the spline
time	`(...) tensor`	Time of the closest point on the spline

mesh_distance_signed

mesh_distance_signed(loc, vertices, faces, out=None)

Compute the signed minimum distance from a set of points to a triangular mesh

Parameters:

Name	Type	Description	Default
loc	`(..., D) tensor`	Point set.	required
vertices	`(N, D) tensor`	Mesh vertices	required
faces	`(M, D) tensor[integer]`	Mesh faces	required

Returns:

Name	Type	Description
dist	`(...) tensor`	Signed distance from each point in the set to its closest point on the mesh (negative inside, positive outside)

mesh_sdt_extra

mesh_sdt_extra(loc, vertices, faces, out=None)

Compute the signed minimum distance from a set of points to a triangular mesh.

Also return the vertex nearest (in geodesic distance) to each point.

Parameters:

Name	Type	Description	Default
loc	`(..., D) tensor`	Point set.	required
vertices	`(N, D) tensor`	Mesh vertices	required
faces	`(M, D) tensor[integer]`	Mesh faces	required

Returns:

Name	Type	Description
dist	`(...) tensor`	Signed distance from each point in the set to its closest point on the mesh (negative inside, positive outside)
nearest_vertex	`(...) tensor[integer]`	Index of the nearest vertex to each point.

mesh_distance

mesh_distance(loc, vertices, faces, naive=False, out=None)

Compute the minimum distance from a set of points to a triangular mesh

Parameters:

Name	Type	Description	Default
loc	`(..., D) tensor`	Point set.	required
vertices	`(N, D) tensor`	Mesh vertices	required
faces	`(M, D) tensor[integer]`	Mesh faces	required
naive	bool	Usae naive algorithm	False

Returns:

Name	Type	Description
dist	`(...) tensor`	Signed distance from each point in the set to its closest point on the mesh (negative inside, positive outside)