Trait geo::algorithm::triangulate_spade::TriangulateSpade

pub trait TriangulateSpade<'a, T>: TriangulationRequirementTrait<'a, T>
where
    T: SpadeTriangulationFloat,
{
    // Provided methods
    fn unconstrained_triangulation(
        &'a self
    ) -> TriangulationResult<Triangles<T>> { ... }
    fn constrained_outer_triangulation(
        &'a self,
        config: SpadeTriangulationConfig<T>
    ) -> TriangulationResult<Triangles<T>> { ... }
    fn constrained_triangulation(
        &'a self,
        config: SpadeTriangulationConfig<T>
    ) -> TriangulationResult<Triangles<T>> { ... }
}

Triangulate polygons using a Delaunay Triangulation

This trait contains both constrained and unconstrained triangulation methods. To read more about the differences of these methods also consult this page

Provided Methods

fn unconstrained_triangulation(&'a self) -> TriangulationResult<Triangles<T>>

returns a triangulation that’s solely based on the points of the geometric object

The triangulation is guaranteed to be Delaunay

Note that the lines of the triangulation don’t necessarily follow the lines of the input geometry. If you wish to achieve that take a look at the constrained_triangulation and the constrained_outer_triangulation functions.

use geo::TriangulateSpade;
use geo::{Polygon, LineString, Coord};
let u_shape = Polygon::new(
    LineString::new(vec![
        Coord { x: 0.0, y: 0.0 },
        Coord { x: 1.0, y: 0.0 },
        Coord { x: 1.0, y: 1.0 },
        Coord { x: 2.0, y: 1.0 },
        Coord { x: 2.0, y: 0.0 },
        Coord { x: 3.0, y: 0.0 },
        Coord { x: 3.0, y: 3.0 },
        Coord { x: 0.0, y: 3.0 },
    ]),
    vec![],
);
let unconstrained_triangulation = u_shape.unconstrained_triangulation().unwrap();
let num_triangles = unconstrained_triangulation.len();
assert_eq!(num_triangles, 8);

fn constrained_outer_triangulation( &'a self, config: SpadeTriangulationConfig<T> ) -> TriangulationResult<Triangles<T>>

returns triangulation that’s based on the points of the geometric object and also incorporates the lines of the input geometry

The triangulation is not guaranteed to be Delaunay because of the constraint lines

This outer triangulation also contains triangles that are not included in the input geometry if it wasn’t convex. Here’s an example:

┌──────────────────┐
│\              __/│
│ \          __/ / │
│  \      __/   /  │
│   \  __/     /   │
│    \/       /    │
│     ┌──────┐     │
│    /│\:::::│\    │
│   / │:\::::│ \   │
│  /  │::\:::│  \  │
│ /   │:::\::│   \ │
│/    │::::\:│    \│
└─────┘______└─────┘

use geo::TriangulateSpade;
use geo::{Polygon, LineString, Coord};
let u_shape = Polygon::new(
    LineString::new(vec![
        Coord { x: 0.0, y: 0.0 },
        Coord { x: 1.0, y: 0.0 },
        Coord { x: 1.0, y: 1.0 },
        Coord { x: 2.0, y: 1.0 },
        Coord { x: 2.0, y: 0.0 },
        Coord { x: 3.0, y: 0.0 },
        Coord { x: 3.0, y: 3.0 },
        Coord { x: 0.0, y: 3.0 },
    ]),
    vec![],
);
// we use the default [`SpadeTriangulationConfig`] here
let constrained_outer_triangulation =
u_shape.constrained_outer_triangulation(Default::default()).unwrap();
let num_triangles = constrained_outer_triangulation.len();
assert_eq!(num_triangles, 8);

The outer triangulation of the top down U-shape contains extra triangles marked with “:”. If you want to exclude those, take a look at constrained_triangulation

fn constrained_triangulation( &'a self, config: SpadeTriangulationConfig<T> ) -> TriangulationResult<Triangles<T>>

returns triangulation that’s based on the points of the geometric object and also incorporates the lines of the input geometry

The triangulation is not guaranteed to be Delaunay because of the constraint lines

This triangulation only contains triangles that are included in the input geometry. Here’s an example:

┌──────────────────┐
│\              __/│
│ \          __/ / │
│  \      __/   /  │
│   \  __/     /   │
│    \/       /    │
│     ┌──────┐     │
│    /│      │\    │
│   / │      │ \   │
│  /  │      │  \  │
│ /   │      │   \ │
│/    │      │    \│
└─────┘      └─────┘

use geo::TriangulateSpade;
use geo::{Polygon, LineString, Coord};
let u_shape = Polygon::new(
    LineString::new(vec![
        Coord { x: 0.0, y: 0.0 },
        Coord { x: 1.0, y: 0.0 },
        Coord { x: 1.0, y: 1.0 },
        Coord { x: 2.0, y: 1.0 },
        Coord { x: 2.0, y: 0.0 },
        Coord { x: 3.0, y: 0.0 },
        Coord { x: 3.0, y: 3.0 },
        Coord { x: 0.0, y: 3.0 },
    ]),
    vec![],
);
// we use the default [`SpadeTriangulationConfig`] here
let constrained_triangulation = u_shape.constrained_triangulation(Default::default()).unwrap();
let num_triangles = constrained_triangulation.len();
assert_eq!(num_triangles, 6);

Compared to the constrained_outer_triangulation it only includes the triangles inside of the input geometry

Object Safety

This trait is not object safe.

Implementors

impl<'a, T, G> TriangulateSpade<'a, T> for G

where T: SpadeTriangulationFloat, G: TriangulationRequirementTrait<'a, T>,