Struct GridSearch 

pub struct GridSearch { /* private fields */ }

Implements a grid for fast searching entries by coordinates

Definitions

• xmin – (ndim) minimum coordinates to define the boundary
• xmax – (ndim) maximum coordinates to define the boundary
• ndiv – number of division for the longest direction
• tolerance – tolerance used to define the Halo and to compare points; e.g. 1e-4
• border_tol – tolerance used to expand the border a little bit and then accommodate eventual imprecision near the borders; e.g. 1e-2

Important: The number of divisions cannot be very large because it could make the container’s side_length be smaller the the tolerance. Conversely, the tolerance cannot be too large making the halo bigger than the container. In fact, the following constraint must be satisfied:

side_length = (xmax - xmin) / ndiv > 2·tolerance

Reference

• Durand, Farias, and Pedroso (2015) Computing intersections between non-compatible curves and finite elements, Computational Mechanics; DOI=10.1007/s00466-015-1181-y

Examples

use gemlab::util::GridSearch;
use gemlab::StrError;
use plotpy::Plot;
use russell_lab::math::SQRT_2;

fn main() -> Result<(), StrError> {
    let xmin = &[0.0, 0.0];
    let xmax = &[10.0, 10.0];
    let mut grid = GridSearch::new(xmin, xmax, Some(2), None, None)?;
    grid.insert(123, &[5.5, SQRT_2])?;
    assert_eq!(grid.search(&[5.5, SQRT_2])?, Some(123));
    assert_eq!(grid.search(&[5.501, SQRT_2])?, None);
    if false {
        let mut plot = Plot::new();
        grid.draw(&mut plot, true)?;
        plot.set_equal_axes(true).save("/tmp/gemlab/doc_grid_search.svg")?;
    }
    Ok(())
}

The figure above illustrates the grid generated by the example.

Implementations

impl GridSearch

pub fn new( xmin: &[f64], xmax: &[f64], ndiv: Option<usize>, tolerance: Option<f64>, border_tol: Option<f64>, ) -> Result<Self, StrError>

Allocates a new instance

Input

• xmin – (ndim) minimum coordinates to define the boundary
• xmax – (ndim) maximum coordinates to define the boundary
• ndiv – number of division (≥ 1)
  • If None, GS_DEFAULT_NDIV is used
  • This number is used for the longest direction
  • The other directions will be subdivided with a number such that the containers will be square/cubic
  • For the other directions, the minimum number of divisions will be 1, in case they are too short compared with the longest direction
• tolerance – tolerance used to define the Halo and to compare points; e.g. 1e-4
  • If None, GS_DEFAULT_TOLERANCE is used
• border_tol – tolerance used to expand the border a little bit and then accommodate eventual imprecision near the borders; e.g. 1e-2
  • If None, GS_DEFAULT_BORDER_TOL is used

Given the ndiv for the longest direction, the number of divisions for the other directions are calculated as follows:

ndiv_other = truncate((delta_other/delta_long) * ndiv)
ndiv_other = max(1, ndiv_other)

Thus the resulting grid will be square/cubic

Important: The number of divisions cannot be very large because it could make the container’s side_length be smaller the the tolerance. Conversely, the tolerance cannot be too large making the halo bigger than the container. In fact, the following constraint must be satisfied:

side_length = (xmax - xmin) / ndiv > 2·tolerance

pub fn is_outside(&self, x: &[f64]) -> bool

Returns whether a point is outside the grid or not (thus we cannot use insert or search)

Panics

This function requires that x.len() = ndim, otherwise a panic occurs.

pub fn insert(&mut self, id: usize, x: &[f64]) -> Result<(), StrError>

Inserts a new item to a container in the grid

Input

• id – identification number of the item
• x – (ndim) coordinates of the item

pub fn search(&self, x: &[f64]) -> Result<Option<usize>, StrError>

Searches an item by coordinates

Input

• x – (ndim) coordinates of the item

Output

• id – if found, returns the ID, otherwise, returns None (not found)

pub fn search_on_line<F>( &self, a: &[f64], b: &[f64], filter: F, ) -> Result<HashSet<usize>, StrError>

where F: FnMut(&[f64]) -> bool,

Searches points on a 2D or 3D line

Input

• a – (ndim) first point on the line
• b – (ndim) second point on the line (different than a)
• filter – fn(x) -> bool that returns true to keep the coordinate just found (yields only the elements for which the closure returns true)

Output

Returns the ids of points.

pub fn search_on_circle<F>( &self, center: &[f64], radius: f64, filter: F, ) -> Result<HashSet<usize>, StrError>

where F: FnMut(&[f64]) -> bool,

Searches points on the perimeter of a circle (2D only)

Input

• center – 2D circle center
• radius – circle radius
• filter – fn(x) -> bool that returns true to keep the coordinate just found (yields only the elements for which the closure returns true)

Output

Returns the ids of points.

Note

This works in 2D only.

pub fn search_on_cylinder<F>( &self, a: &[f64], b: &[f64], radius: f64, filter: F, ) -> Result<HashSet<usize>, StrError>

where F: FnMut(&[f64]) -> bool,

Searches points on the surface of a cylinder (3D only)

Input

• a – 3D point on the cylinder axis
• b – 3D point on the cylinder axis
• radius – cylinder radius
• filter – fn(x) -> bool that returns true to keep the coordinate just found (yields only the elements for which the closure returns true)

Output

Returns the ids of points.

Note

This works in 3D only.

pub fn search_on_plane_xy<F>( &self, z: f64, filter: F, ) -> Result<HashSet<usize>, StrError>

where F: FnMut(&[f64]) -> bool,

Searches points on the x-y plane (3D only)

Input

• z – the plane passes through z
• filter – fn(x) -> bool that returns true to keep the coordinate just found (yields only the elements for which the closure returns true)

Output

Returns the ids of points.

Note

This works in 3D only.

pub fn search_on_plane_yz<F>( &self, x: f64, filter: F, ) -> Result<HashSet<usize>, StrError>

where F: FnMut(&[f64]) -> bool,

Searches points on the y-z plane (3D only)

Input

• x – the plane passes through x
• filter – fn(x) -> bool that returns true to keep the coordinate just found (yields only the elements for which the closure returns true)

Output

Returns the ids of points.

Note

This works in 3D only.

pub fn search_on_plane_xz<F>( &self, y: f64, filter: F, ) -> Result<HashSet<usize>, StrError>

where F: FnMut(&[f64]) -> bool,

Searches points on the x-z plane (3D only)

Input

• y – the plane passes through y
• filter – fn(x) -> bool that returns true to keep the coordinate just found (yields only the elements for which the closure returns true)

Output

Returns the ids of points.

Note

This works in 3D only.

pub fn draw(&self, plot: &mut Plot, with_ids: bool) -> Result<(), StrError>

Draws grid and items

Trait Implementations

impl Display for GridSearch

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

Shows info about the items in the grid containers