Trait spade::HintGenerator

pub trait HintGenerator<S: SpadeNum>: Default {
    // Required methods
    fn get_hint(&self, position: Point2<S>) -> FixedVertexHandle;
    fn notify_vertex_lookup(&self, vertex: FixedVertexHandle);
    fn notify_vertex_inserted(
        &mut self,
        vertex: FixedVertexHandle,
        vertex_position: Point2<S>
    );
    fn notify_vertex_removed(
        &mut self,
        swapped_in_point: Option<Point2<S>>,
        vertex: FixedVertexHandle,
        vertex_position: Point2<S>
    );
    fn initialize_from_triangulation<TR, V>(triangulation: &TR) -> Self
       where TR: Triangulation<Vertex = V>,
             V: HasPosition<Scalar = S>;
}

A structure used to speed up common operations on delaunay triangulations like insertion and geometry queries by providing hints on where to start searching for elements.

Without a hint, these operations run in O(sqrt(n)) for n uniformly distributed vertices. Most time is spent by “walking” to the queried site (e.g. the face that is being inserted to), starting at a random vertex. A hint generator can speed this up by either using heuristics or a spatial data structure to determine where to start walking closer to the target site.

Hints can also be given manually by using the ...with_hint methods (e.g. Triangulation::insert_with_hint)

Usually, you should not need to implement this trait. Spade currently implements two common hint generators that should fulfill most needs:

• A heuristic that uses the last inserted vertex as hint (LastUsedVertexHintGenerator)
• A hint generator based on a hierarchy of triangulations that improves walk time to O(log(n)) (HierarchyHintGenerator)

Required Methods

fn get_hint(&self, position: Point2<S>) -> FixedVertexHandle

Returns a vertex handle that should be close to a given position.

The returned vertex handle may be invalid.

fn notify_vertex_lookup(&self, vertex: FixedVertexHandle)

Notifies the hint generator that an element was looked up

fn notify_vertex_inserted( &mut self, vertex: FixedVertexHandle, vertex_position: Point2<S> )

Notifies the hint generator that a new vertex is inserted

fn notify_vertex_removed( &mut self, swapped_in_point: Option<Point2<S>>, vertex: FixedVertexHandle, vertex_position: Point2<S> )

Notifies the hint generator that a vertex was removed

fn initialize_from_triangulation<TR, V>(triangulation: &TR) -> Self

where TR: Triangulation<Vertex = V>, V: HasPosition<Scalar = S>,

Creates a new hint generator initialized to give hints for a specific triangulation

Object Safety

This trait is not object safe.

Implementors

impl<S: SpadeNum> HintGenerator<S> for LastUsedVertexHintGenerator