Struct crater::kdtree::QueryOptions

pub struct QueryOptions<'a, R: KdRegion> {
    pub inner_bound: QueryBound<'a, R>,
    pub outer_bound: QueryBound<'a, R>,
    pub keep_ties: bool,
}

Fine grained control over a query within the tree (KdTree::k_closest).

Fields

inner_bound: QueryBound<'a, R>

Points within this bound will be EXCLUDED from the query result. Points ON the inner boundary will also be EXCLUDED (ie the excluded region is a closed set). Useful to exclude points that are “too close” to the query point, for example when iteratively increasing a sampling radius in a shortest path algorithm or some other situation where the number of k_closest points needed is not know a prior. For QueryBound::SqDist(d), this means points whose sqdist from the query point is <= d will be excluded. Since the query point itself is included by default if it is in the tree, passing QueryBound::SqDist(Distance::zero()) here can be used to exclude it. For QueryBound::Region(&r), this means points within r (where r.min_sqdist is Distance::zero()) will excluded. NB this cannot be conservative like an unbounded search. That is, if R::min_sqdist can be an underestimate, then QueryBound::Region should not be used. For QueryBound::None, no points will be excluded for being “too close” to the query point.

outer_bound: QueryBound<'a, R>

Points outside this bound will be EXCLUDED from the query result. Points ON the outer boundary will be INCLUDED (ie the excluded region is an open set). This makes the overall included region a half open set, excluding the inner bound but including the outer bound. This is to make it easy to have successive queries cover additional area without duplicate results. For QueryBound::SqDist(d), points whose sqdist from the query point is > d will be excluded. For QueryBount::Region(&r), points outside r (where r.min_sqdist is not Distance::zero()) will be excluded. Unlike the inner bound, this will work correctly with a conservative R::min_sqdist (ie if min_sqdist is an underestimate it can only cause the result to include extra points, not miss points that should be included). For QueryBound::None, no points will be excluded for being “too far” from the query point.

keep_ties: bool

If false, if multiple points are tied for being the kth closest, which one will be returned is arbitrary, but exactly k points will be returned. If true, if multiple points are tied for being the kth closest, all of them will be returned, and more than k points will be returned in this case. Setting this to true is necessary to correctly call KdTree::k_closest with an iteratively increasing sampling radius.

Implementations

impl<'a, R: KdRegion> QueryOptions<'a, R>

pub const ALL_KEEP_TIES: Self = _

Default QueryOptions to have the included region be the entire tree, and return all points which are tied for being the kth-closest

pub const ALL_NO_TIES: Self = _

Default QueryOptions to have the included region be the entire tree, and arbitrarily break ties for the kth-closest point so no more than k points are ever returned.

pub fn contains(&self, point: &R::Point, pt: &R::Point) -> bool

Returns true if the included region contains the point pt, where point is the center of the query, or false if pt is in the excluded region.

pub fn might_overlap( &self, point: &R::Point, max_sqdist: Option<&<R::Point as KdPoint>::Distance>, bounds: &R ) -> bool

Returns true if the included region might overlap with bounds and might contain additional points within max_sqdist of the center of the query, point. When some of the required functions of <R as KdRegion> are implemented conservatively, this function will return true in cases where the query region and bounds can’t actually contain any additional points in the result set. However, when this function returns false, the query region will always be disjoint from bounds, UNLESS self.inner_bound is not QueryBound::None and a conservative implementation is used for KdRegion.