Rust多边形三角剖分库earcut的使用指南

介绍

earcut是一个高效的2D多边形三角剖分库，特别适合处理带有孔洞的复杂多边形。它基于"耳切法"(ear clipping)算法实现，能够将任意简单多边形(包括带孔洞的多边形)分解为三角形集合。

这个库的主要特点包括：

• 纯Rust实现
• 无外部依赖
• 处理带孔洞的多边形
• 高效性能
• 输出三角形索引

使用方法

添加依赖

首先在Cargo.toml中添加依赖：

[dependencies]
earcut = "0.4"

基本用法

use earcut::earcut;

fn main() {
    // 定义多边形顶点坐标(扁平化的Vec<f64>)
    // 格式: [x0, y0, x1, y1, x2, y2, ...]
    let vertices = vec![
        0.0, 0.0,
        1.0, 0.0,
        1.0, 1.0,
        0.0, 1.0,
    ];
    
    // 定义孔洞的起始索引(如果没有孔洞则为空vec)
    let holes = Vec::<usize>::new();
    
    // 每个顶点的维度(这里是2D)
    let dims = 2;
    
    // 执行三角剖分
    let triangles = earcut(&vertices, &holes, dims).unwrap();
    
    println!("三角形索引: {:?}", triangles);
    // 输出可能是: [0, 1, 2, 0, 2, 3] 表示两个三角形
}

处理带孔洞的多边形

use earcut::earcut;

fn main() {
    // 外轮廓顶点(顺时针)
    let vertices = vec![
        // 外矩形
        0.0, 0.0,
        3.0, 0.0,
        3.0, 3.0,
        0.0, 3.0,
        // 内矩形(孔洞，逆时针)
        1.0, 1.0,
        1.0, 2.0,
        2.0, 2.0,
        2.0, 1.0,
    ];
    
    // 孔洞的起始索引(这里是第4个顶点开始)
    let holes = vec![4];
    let dims = 2;
    
    let triangles = earcut(&vertices, &holes, dims).unwrap();
    
    println!("带孔洞的三角形索引: {:?}", triangles);
}

处理更复杂的多边形

use earcut::earcut;

fn main() {
    // 一个更复杂的多边形，包含多个孔洞
    let vertices = vec![
        // 外轮廓(五边形)
        0.0, 0.0,
        5.0, 0.0,
        5.0, 3.0,
        3.0, 5.0,
        0.0, 5.0,
        
        // 第一个孔洞(三角形)
        1.0, 1.0,
        2.0, 1.0,
        1.5, 2.0,
        
        // 第二个孔洞(四边形)
        3.0, 1.0,
        4.0, 1.0,
        4.0, 2.0,
        3.0, 2.0,
    ];
    
    // 两个孔洞的起始索引
    let holes = vec![5, 8];
    let dims = 2;
    
    let triangles = earcut(&vertices, &holes, dims).unwrap();
    
    println!("复杂多边形的三角形索引: {:?}", triangles);
}

注意事项

1. 顶点顺序: 外轮廓顶点应顺时针排列，孔洞顶点应逆时针排列
2. 坐标系统: 使用标准的2D笛卡尔坐标系
3. 性能: 对于非常复杂的多边形，可能需要考虑性能优化
4. 错误处理: earcut函数返回Result，记得处理可能的错误情况

高级用法

earcut还提供了更高级的接口Earcut结构体，可以重用分配的内存以提高性能：

use earcut::Earcut;

fn main() {
    let vertices = vec![
        0.0, 0.0,
        1.0, 0.0,
        1.0, 1.0,
        0.0, 1.0,
    ];
    
    let mut earcut = Earcut::new();
    let triangles = earcut.earcut(&vertices, &[], 2).unwrap();
    
    println!("使用Earcut结构体的结果: {:?}", triangles);
}

完整示例

下面是一个完整的示例，展示如何使用earcut库处理一个带孔洞的复杂多边形并可视化结果：

use earcut::earcut;
use plotters::prelude::*;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // 定义多边形顶点数据
    let vertices = vec![
        // 外轮廓(六边形)
        0.0, 0.0,
        4.0, 0.0,
        6.0, 2.0,
        4.0, 4.0,
        0.0, 4.0,
        -2.0, 2.0,
        
        // 第一个孔洞(三角形)
        1.0, 1.0,
        2.0, 1.0,
        1.5, 2.0,
        
        // 第二个孔洞(四边形)
        3.0, 1.0,
        3.5, 1.0,
        3.5, 2.0,
        3.0, 2.0,
    ];
    
    // 孔洞起始索引
    let holes = vec![6, 9];
    let dims = 2;
    
    // 执行三角剖分
    let triangles = earcut(&vertices, &holes, dims)?;
    
    println!("生成的三角形索引: {:?}", triangles);
    
    // 可视化结果
    let root = BitMapBackend::new("triangulation.png", (800, 600)).into_drawing_area();
    root.fill(&WHITE)?;
    
    let mut chart = ChartBuilder::on(&root)
        .build_cartesian_2d(-3.0..7.0, -1.0..5.0)?;
    
    // 绘制原始多边形
    chart.draw_series(LineSeries::new(
        vertices.chunks(2).take(6).map(|p| (p[0], p[1])).chain(std::iter::once((vertices[0], vertices[1]))),
        &BLACK,
    ))?;
    
    // 绘制孔洞
    chart.draw_series(LineSeries::new(
        vertices.chunks(2).skip(6).take(3).map(|p| (p[0], p[1])).chain(std::iter::once((vertices[12], vertices[13]))),
        &RED,
    ))?;
    
    chart.draw_series(LineSeries::new(
        vertices.chunks(2).skip(9).take(4).map(|p| (p[0], p[1])).chain(std::iter::once((vertices[18], vertices[19]))),
        &RED,
    ))?;
    
    // 绘制三角形网格
    for triangle in triangles.chunks(3) {
        let points: Vec<_> = triangle.iter()
            .map(|&i| (vertices[i*2], vertices[i*2+1]))
            .collect();
        
        chart.draw_series(std::iter::once(Polygon::new(
            points,
            BLUE.mix(0.2).filled(),
        )))?;
    }
    
    Ok(())
}

这个完整示例演示了：

1. 定义一个复杂的六边形外轮廓和两个孔洞
2. 使用earcut进行三角剖分
3. 使用plotters库可视化原始多边形和生成的三角形网格
4. 展示了如何处理多个孔洞的情况

要运行此示例，需要在Cargo.toml中添加以下依赖：

[dependencies]
earcut = "0.4"
plotters = "0.3"

这个库非常适合游戏开发、地理信息系统(GIS)和任何需要多边形三角剖分的图形应用。