使用卢浮宫进行鲁棒三角剖分 🌙

▶️ 在线演示页面

卢浮宫是一个鲁棒的三角剖分算法，可以处理自相交多边形的三角剖分。

什么是三角剖分？ "Polygon triangulation" 将多边形的顶点坐标数组转换为三角形坐标集，其面积之和等于多边形的面积。

由于大多数计算图形处理系统（如 opengl/webgl）通过将多边形分解成三角形来处理多边形，因此一个好的快速三角剖分算法至关重要。

Earcut(mapbox/earcut.js) 是最广泛使用的三角剖分算法之一。然而，简单的 earcut 无法正确分解自相交多边形。

卢浮宫广泛参考了 mapbox/earcut.js 来实现简单 earcut 算法的逻辑和实用工具。卢浮宫做出了进一步的贡献，可以处理 自相交多边形，这在大多数开源算法中（包括 mapbox/earcut.js）都是不可行的。

请查看 卢浮宫的实时演示。尝试绘制一些复杂的自相交多边形。

当然，卢浮宫是快速且鲁棒的。您可以在 Rust 原生或 Rust 支持的 wasm 环境中使用它。

示例

use louvre::triangulate;

let mut data: Vec<f64> = vec![
  [0., 0.], [0., 3.], [3., 0.], [3., 4.], [-1., 0.]
].concat();

let (new_data, indices) = triangulate(&mut data, 2);

assert_eq!(new_data, 
  vec![
    3.0, 0.0,  3.0, 4.0,  1.0, 2.0, 
    0.0, 0.0,  0.0, 1.0,  -1.0, 0.0,
    0.0, 1.0,  1.0, 2.0,  0.0, 3.0
  ]
);
assert_eq!(indices, vec![
  1, 2, 0, 
  4, 5, 3, 
  7, 8, 6
]);

fig1. 解析 .json 文件： 三角剖分后的多边形显示在右侧框中。

fig2. 三角剖分随机的（自相交）多边形

性能

三角剖分处理每个项目所需的平均性能时间（以毫秒为单位）。

不安全链表

该包中有很多不安全代码和原始指针，用于实现链表。对于 Rust 中的链表，使用原始指针可能是其他选项中最好（且最快）的选择。这些不安全代码已通过 rust 的 miri 测试，并设计为安全。

更多？

尚未实现处理 3D 坐标和内部有孔的复杂多边形。

该项目的原始目标是使用 Rust 覆盖基本的计算几何问题。然而，目前尚未安排进一步的扩展。

日志

• v.0.2.0
  • 模块结构的微小调整。
  • 添加了 html 功能。
• v.0.2.1
  • 进行了轻微的内部修改