结果数组中每组三个顶点索引形成一个三角形。

// triangulating a polygon with a hole
earcutr::earcut(&[0.,0., 100.,0., 100.,100., 0.,100.,  20.,20., 80.,20., 80.,80., 20.,80.], &[4],2).unwrap();
// [3,0,4, 5,4,0, 3,4,7, 5,0,1, 2,3,7, 6,5,1, 2,7,6, 6,1,2]

如果您传递一个单个顶点作为孔，Earcut将其视为Steiner点。请参阅./tests/fixtures下的'steiner'测试用例，以及./viz下的测试可视化。

在获得三角剖分后，您可以使用earcutr.deviation验证其正确性。

let deviation = earcutr.deviation(&data.vertices, &data.holes, data.dimensions, &triangles);

偏差返回三角形总面积与输入多边形面积的相对差异。代码0表示三角剖分完全正确。

平面数据与多维数据

如果您的输入是多维数组，您可以使用earcut.flatten将其转换为Earcut期望的格式。例如

let v = vec![
  vec![vec![0.,0.],vec![1.,0.],vec![1.,1.],vec![0.,1.]], // outer ring
  vec![vec![1.,1.],vec![3.,1.],vec![3.,3.]]        // hole ring
];
let (vertices,holes,dimensions) = earcutr::flatten( &v );
let triangles = earcutr::earcut(&vertices, &holes, dimensions).unwrap();

GeoJSON Polygon格式使用基于文本的JSON格式的多维数据。有关如何解析JSON数据的示例代码，请参阅tests/integration_test.rs下的内容。测试/固定文件都是多维.json文件。

工作原理：算法

该库实现了一种改进的耳切片算法，通过z-order曲线哈希优化，并扩展以处理孔洞、扭曲多边形、退化性和自相交，但并不保证三角剖分的正确性，而是尝试为实际数据始终产生可接受的结果。

它基于Martin Held的FIST：快速工业强度多边形三角剖分和David Eberly的耳剪裁三角剖分中的思想。

可视化示例

例如，一个矩形可以用GeoJSON格式如下表示

[ [ [0,0],[7,0],[7,4],[0,4] ] ]

这有一个单一的轮廓，或环，包含四个点。点列出的方式，在页面上看起来是“逆时针”或“顺时针”。这是“缠绕”，表示它是一个“外部”环，或形状的“主体”。

 _______
 |     |
 |     |
 |     |
 |_____|

现在让我们在正方形中添加一个洞。

[ 
  [ [0,0],[7,0],[7,4],[0,4] ],   
  [ [1,1],[3,1],[3,3] ] 
]

这有两个轮廓（环），第一个有四个点，第二个有三个点。第二个是“顺时针”缠绕，表示它是一个“洞”。

_______
|     |
|  /| |
| /_| |
|_____|

“展开”后，我们最终得到一个单一的数组

data [ 0,0,7,0,7,4,0,4,1,1,3,1,3,3  ]
holeindexes: [ 4 ]
dimensions: 2

程序将把这个数据序列解释为两个单独的“环”，外部环和“洞”。环是用循环双链表存储的。

程序通过在洞和多边形之间添加一个“切割”来“移除”洞，从而只有一个“环”循环。

     _______
     |     |
     |  /| |
cut> |_/_| |
     |_____|

程序还会自动“纠正”输入点期间的缠绕，使它们都是逆时针。

然后，应用“耳切割”算法。但这不仅仅是任何耳切割算法。

通常，耳切割算法通过查看多边形上三个连续点来找到潜在的耳或“候选”耳。然后，它必须确保没有其他点“在耳内”。

为了做到这一点，它必须遍历多边形中的每个点，所以如果你的多边形有15,000个点，那么它必须遍历所有这些点，查看每个点是否在潜在的耳内。每个耳检查需要十几个计算，通常使用像耳的每一边与检查点之间的楔积测试这样的测试。如果点在每一边的右手边（楔积小于零），则它在耳内，因此耳不能切割。然后算法继续到下一个潜在的耳。

Z-order曲线

Z-order哈希允许将“在耳内”检查的数量大大减少。如何做到这一点？不是在每个多边形的其他点上运行“在耳内”代码，它只能检查耳“附近”的点。这是通过以下方式实现的

步骤 1：在 earcut 之前，多边形的每个点都通过多边形边界框的空间给定了 z 轴（Morton）曲线上的坐标。这是一种在许多几何算法中已经探索过的空间填充曲线策略。请参阅 https://zh.wikipedia.org/wiki/Z-轴曲线

步骤 2：巧妙之处在于，如果您想在由 Z 轴曲线填充的空间内的一个有限矩形内进行搜索，您可以通过查看它们在 z 轴曲线上的位置（即它们的 z 索引）相对容易地找出哪些点在该矩形内。换句话说，代码将索引存储为 ".z" 在表示多边形顶点的链表节点的每个节点中。

更具体地说，Z 轴曲线有一个特殊之处，当您在内部选择一个有限的矩形时，您可以沿着 z 曲线从“最低”角迭代到“最高”角，并保证会击中该矩形内的每个 2D 点。

例如，在 4x4 的 Morton 方阵中，有 16 个 Morton 代码。

 x-----0--1--2--3-->
y|0    0  1  4  5
 |1    2  3  6  7
 |2    8  9 12 13
 |3   10 11 14 15
\|/

从 z 代码 0 到 z 代码 6，0 1 2 3 4 5 6，将我们带过了从 0,0 到 2,1 的每个二维点，其中 0 位于 0,0，而 6 位于 2,1。它还通过了 3,0，但没有什么是完美的。

假设您选择 2,2 和 3,3。最低点的 z 代码是 12，最高点是 15。因此，您的 z 迭代将是 12, 13, 14, 15，这覆盖了从 2,2 到 3,3 的矩形。

因此，它避免了检查多边形中的每个点来确定它们是否在耳部内。它围绕耳部画一个矩形，找到该矩形的最低和最高角，然后迭代 z 曲线以检查每个接近多边形耳部的 2D 点。

如您所想象，如果您的多边形中有 14,000 个点在这个盒子外面，而只有 1,000 个点在盒子里，那么要做的数学和计算要比迭代 15,000 个点少得多。

额外调整

如果简单的 earcut 失败，它还进行了一些简单的修复，

• 过滤点 - 移除一些共线点和相等点

• 自相交 - 移除只在一个小环中打结而没有对多边形的整体形状做出贡献（同时也使它不是简单的）的点

• 分割桥梁 - 实际上将多边形分割成两个独立的部分，并尝试对每个部分进行 earcut。

数据示例包含在 tests/fixtures 下的 json 文件中。测试结果的可视化生成在 viz/testoutput 下，可以在网页浏览器中通过打开 viz/viz.html 来查看

坐标数字类型

此代码中的坐标类型是 64 位浮点数。请注意，32 位浮点数将无法通过测试，因为测试数据文件中有一些数字无法在 32 位中完全精确表示，例如 537629.886026485 这个十进制数，在从十进制转换为 32 位二进制时被四舍五入到 537629.875。

权衡

此三角剖分器主要作为将 JavaScript 端口移植到 Rust 的练习来构建。然而，实现的一些细节已经为了速度优化而进行了修改。该代码应该使用与原始 JavaScript 代码一起提供的庞大测试数据集，产生与 JavaScript 版本完全相同的输出。速度与 Mapbox 的 C++ 版本 earcut，earcut.hpp 相当，除了在非常小的多边形输入中速度要慢得多。有关更多详细信息，请参阅基准测试部分。

如果您想在有大量自相交和 earcut 不够精确的非常差的数据上获得正确的三角剖分，请查看 libtess.js。

您还可以考虑使用Angus J的Clipper对多边形数据进行预处理，该工具使用Vatti算法清理“多边形汤”类型的数据。

这些算法基于链表，在Rust中这很难吗？

是的。A. Beinges的《Too Many Lists》展示了如何在Rust中实现链表。Rust还有一个内置的'linked list'类型，理论上可以通过调用iter().cycle()使其成为循环链表。

然而，此代码完全在Rust Vector之上实现了一个循环双链表，没有使用任何不安全块。它不使用Rc、Box、Arc等。正常链表节点代码中的指针已被整数替换，这些整数索引到LinkedLists结构体中存储的单个节点Vector。如果您使用超出范围的索引，它仍然会崩溃，但RUST_BACKTRACE=1会告诉您具体发生崩溃的位置。

这可能会被认为是一个导致速度减慢的来源——在每次数组访问时进行边界检查。然而，在实践中，这种差异几乎可以忽略不计。事实上，代码是构建的，相对容易切换到"unchecked_get"来测试没有边界检查的向量访问。

测试、基准测试

要运行测试

$ git clone github.com/donbright/earcutr
$ cd earcutr
$ cargo test             # normal Rust tests. Also outputs visualization data
$ cd viz                 # which is stored under viz/testoutput. you can
$ firefox viz.html       # view in your favorite web browser (circa 2018)

要运行基准测试

$ cargo bench
...
test bench_water                ... bench:   1,860,385 ns/iter (+/- 21,188)
test bench_water2               ... bench:   1,477,185 ns/iter (+/- 10,294)
test bench_water3               ... bench:      63,800 ns/iter (+/- 3,809)
test bench_water3b              ... bench:       5,751 ns/iter (+/- 18)
test bench_water4               ... bench:     473,971 ns/iter (+/- 5,950)
test bench_water_huge           ... bench:  26,770,194 ns/iter (+/- 532,784)
test bench_water_huge2          ... bench:  53,256,089 ns/iter (+/- 1,208,028)

基准测试说明：截至本文撰写时，基准测试不在稳定版Rust中，因此该项目使用一个替代方案，https://docs.rs/bencher/0.1.5/bencher/

Rust代码与earcut.hpp C++代码的速度

以下是一个基于测试的粗略表格，包括对Earcut的C++代码的测试、Earcut的C++对LibTess的C++代码的测试，最后是Earcut的Rust版本。

____polygon______earcut.hpp_-O2__libtessc++_-O2___Rust_earcutr_release
| water      |  1,831,501 ns/i  |  9,615,384 ns/i |   1,860,385 ns/i |
| water2     |  1,626,016 ns/i  |  1,694,915 ns/i |   1,477,185 ns/i |
| water3     |     53,140 ns/i  |    153,869 ns/i |      63,800 ns/i |
| water3b    |      4,183 ns/i  |     20,143 ns/i |       5,751 ns/i |
| water4     |    475,511 ns/i  |    871,839 ns/i |     473,971 ns/i |
| water_huge | 26,315,789 ns/i  | 26,315,789 ns/i |  26,770,194 ns/i |
| water_huge2| 55,555,555 ns/i  | 20,000,000 ns/i |  53,256,089 ns/i |
----------------------------------------------------------------------
ns/i = nanoseconds per iteration

对于小形状，此Rust代码似乎比Earcut的C++版本慢20-40%。然而，对于大形状，它要么在误差范围内，或许稍微快一点。

比较Earcut C++ / Earcutr Rust的方法

Mapbox有一个earcut.hpp的C++版本，内置了一个benchmarker，以“每秒操作次数”衡量。它还与C++版本的libtess进行了比较。然而，默认情况下，它没有优化构建，这阻碍了比较。我们可以解决这个问题。通过编辑.hpp CMakeLists.txt文件来设置C编译器标志，我们可以打开优化。

add_compile_options("-g" "-O2" ....

现在，Rust基准测试以每迭代纳秒衡量。C++ Earcut以每秒迭代数衡量。要转换：1秒18次操作，是1,000,000,000纳秒内的18次迭代。1,000,000,000 / 18 -> 55,555,555纳秒/迭代。这样，可以进行转换。

性能分析

• http://www.codeofview.com/fix-rs/2017/01/24/how-to-optimize-rust-programs-on-linux/

• Valgrind的callgrind：（请参见Cargo.toml，设置debug=yes）

sudo apt install valgrind
cargo bench water2 # find the binary name "Running: target/release/..."
valgrind --tool=callgrind target/release/deps/speedtest-bc0e4fb32ac081fc water2
callgrind_annotate callgrind.out.6771
kcachegrind callgrind.out.6771

• CpuProfiler

来自AtheMathmo https://github.com/AtheMathmo/cpuprofiler

• Perf

https://perf.wiki.kernel.org/index.php/Tutorial

cargo bench water2 # find the binary name "Running: target/release/..."
sudo perf stat target/release/deps/speedtest-bc0e4fb32ac081fc  water2
sudo perf record  target/release/deps/speedtest-bc0e4fb32ac081fc  water2
sudo perf report

性能分析结果

如果您希望对优化过程有一个详细的描述，请参阅OPTO.md。这里是一些其他亮点

• is_earcut_hashed()是热点

性能分析器揭示，在更大的形状上，绝大多数时间都花在is_earcut_hashed()内部，这是确定一个“耳朵”是否真的是“耳朵”，以便可以切割而不会损坏多边形。

• Zorder也是热点

第二次主要速度提升来自于Callgrind/kcachegrind，特别是它揭示了zorder()函数是CPU大量工作的来源。特别是从输入参数的64位浮点数到32位整数的转换，这可能对提高速度很重要。

• inline by-hand很重要

在C++中，您通常可以假设编译器会自动处理内联。然而，在Rust中，point_in_triangle和area函数在ear_checker内部不会自动内联，除非明确使用inline宏指示。

• Vector [索引]和Rust中的边界检查不会影响速度

如前所述，此代码作为位于向量之上的双链表实现，而所谓的“指针”实际上是向量中的索引。这里使用了一些宏，它们代表了常规链表语言，例如next!(index)和prev!(index)，它们接受索引整数作为输入，并返回节点或节点的引用。每个索引都使用Rust内置的向量索引，该索引使用“边界检查”，如果意外访问向量范围之外的内存，则会立即引发panic。panic和backtrace将报告访问发生的确切行号和太大而无法使用的索引值。

从理论上讲，这会减慢程序的速度。在实践中，它并没有这样做。这已经被广泛测试，因为next!()和prev!()这样的宏被编写得非常容易在边界检查的向量索引和unsafe向量索引（使用get_unchecked()）之间切换，并重新运行'cargo bench water'以比较它们。

水形基准测试显示，差异在误差范围内，除了像water3b这样的小型形状，其好处非常小，对于大多数使用场景来说不值得。

• 迭代与循环

此代码将几个JavaScript for循环转换为Rust迭代。从理论上讲，这要慢一些。在实践中，它并没有，在某些情况下，它实际上更快，尤其是在find_hole_bridge中。从理论上讲，迭代器更容易阅读和编写，代码量更少，错误也更少。

其他语言中的三角化器

• mapbox/earcut MapBox原始JavaScript
• mapbox/earcut.hpp MapBox C++11

谢谢