三角剖分

将一组非自相交的多边形分割成一组非重叠的三角形。输入和输出可以自定义，以使用您所需的格式，以避免不必要的转换。

注意：虽然这个crate使用的算法的大O度量非常出色，但在实践中，常数因子意味着它的运行速度可能比earcutr等crate慢，除非多边形非常大。

# use triangulate::formats;
# use triangulate::{PolygonList, ListFormat};

// A hollow square shape
//  ________
// |  ____  |
// | |    | |
// | |____| |
// |________|
let polygons = vec![
    vec![[0f32, 0f32], [0., 1.], [1., 1.], [1., 0.]], 
    vec![[0.05, 0.05], [0.05, 0.95], [0.95, 0.95], [0.95, 0.05]]
];
let mut triangulated_indices = Vec::<[usize; 2]>::new();
polygons.triangulate(formats::IndexedListFormat::new(&mut triangulated_indices).into_fan_builder()).expect("Triangulation failed");
println!("First triangle: {:?}, {:?}, {:?}", 
    polygons.get_vertex(triangulated_indices[0]), 
    polygons.get_vertex(triangulated_indices[1]), 
    polygons.get_vertex(triangulated_indices[2]));

任何实现了 Polygon 或 PolygonList 特质的类型都可以进行三角剖分。最常见的情况是 Vec<T> 或 Vec<Vec<T>>（其中 T: Vertex，例如 [f32; 2]），但您也可以在自己的类型上实现该特质。

输出格式也可以自定义。《code>PolygonList::triangulate 接收一个 FanFormat，该格式决定了输出结果。通常情况下，您可能想要 formats::IndexedListFormat，它将每个生成的三角形的三个索引存储在一个 List（如 Vec）中。然而，这是一个 ListFormat（它接受单个三角形而不是三角形扇），因此必须通过调用 ListFormat::into_fan_format（见上面的示例）将其转换为 FanFormat。另一个有用的格式是 formats::DeindexedListFormat，它将每个三角形的顶点降序索引以创建一个包含实际顶点的 List。

先决条件

• 没有边可以交叉任何其他边，无论是在同一个多边形上还是在不同的多边形上。
• 每个顶点必须是两条边的组成部分。多边形不能与其他多边形共享顶点。
• 每个顶点必须是唯一的 - 没有顶点的 x 和 y 坐标可以与另一个顶点的坐标相等。

这些先决条件不会明确检查，但一个无效的多边形集可能会产生 TriangulationError::InternalError。

结果

由于算法涉及随机排序，精确的三角剖分在调用之间不一定相同。

算法

此库基于 Raimund Seidel 的多边形三角剖分随机算法。每个具有 n 个顶点的多边形或孔的预期运行时间为 O(n log* n），接近线性运行时间。