Trait TriangulationExt

trait TriangulationExt {
    // Required methods
    fn all_edges(&self) -> DHashSet<(usize, usize)>;
    fn is_hull_node(&self, index: usize) -> bool;
    fn node_connections(&self) -> DHashMap<usize, DockNode>;
    fn eulerized_route_segments(
        &self,
        all_dock_points: &[Point],
        iterations: usize,
        max_route_leg_length: f64,
        seed: u32,
    ) -> Option<(Vec<Vec<usize>>, Vec<usize>, usize, f32, usize)>;
}

Extension functions for Triangulation (from the triangulate crate).

Required Methods

fn all_edges(&self) -> DHashSet<(usize, usize)>

fn is_hull_node(&self, index: usize) -> bool

fn node_connections(&self) -> DHashMap<usize, DockNode>

fn eulerized_route_segments( &self, all_dock_points: &[Point], iterations: usize, max_route_leg_length: f64, seed: u32, ) -> Option<(Vec<Vec<usize>>, Vec<usize>, usize, f32, usize)>

Implementations on Foreign Types

impl TriangulationExt for Triangulation

Implementation of extension functions for the Triangulation struct.

fn all_edges(&self) -> DHashSet<(usize, usize)>

Get the set of all edges in the triangulation.

fn node_connections(&self) -> DHashMap<usize, DockNode>

For all triangles in the tessellation, create a map of nodes to their connected nodes.

fn is_hull_node(&self, index: usize) -> bool

True if the node is on the outer hull of the triangulation.

fn eulerized_route_segments( &self, all_dock_points: &[Point], iterations: usize, max_route_leg_length: f64, seed: u32, ) -> Option<(Vec<Vec<usize>>, Vec<usize>, usize, f32, usize)>

Calculates the best way to modify the triangulation so that all nodes have an even number of connections (all nodes have an even ‘degree’). The steps are:

1. Remove very long edges (not important for eurelization, but this is a goal of the airship routes design.
2. Remove the shortest edges from all nodes that have more than 8 connections to other nodes. This is because the airship docking sites have at most 4 docking positions, and for deconfliction purposes, no two “routes” can use the same docking position.
3. Add edges to the triangulation so that all nodes have an even number of connections to other nodes. There are many combinations of added edges that can make all nodes have an even number of connections. The goal is to find a graph with the maximum number of ‘routes’ (sub-graphs of connected nodes that form a closed loop), where the routes are all the same length. Since this is a graph, the algorithm is sensitive to the starting point. Several iterations are tried with different starting points (node indices), and the best result is returned.

Returns a tuple with the following elements:

• best_route_segments (up to 4 routes, each route is a vector of node indices)
• best_circuit (the full eulerian circuit)
• max_seg_len (the length of the longest route segment)
• min_spread (the standard deviation of the route segment lengths)
• best_iteration (for debugging, the iteration that produced the best result)

Implementors