Earcutr

这是MapBox公司Earcut计算机代码的移植版本（见 https://github.com/mourner ），用于多边形三角化。更多信息请参见 https://github.com/mapbox/earcut 关于原始JavaScript代码的描述。此移植版本是针对Rust编程语言的，且为单线程。

此移植版本与MapBox没有任何关联，也不暗示任何认可。此外，请注意MapBox有自己的Rust移植版本，不声称此版本优于其版本。

请注意，有人将此制作成Crate（不是我）以方便使用，请检查crates.io

使用方法

extern crate earcutr;
var triangles = earcutr::earcut(&vec![10,0, 0,50, 60,60, 70,10],&vec![],2);
println!("{:?}",triangles);  // [1, 0, 3, 3, 2, 1]

签名

earcut(vertices:&vec<f64>,hole_indices:&vec<usize>,dimensions:usize).

• vertices 是一个顶点坐标的扁平数组，例如 [x0,y0, x1,y1, x2,y2, ...]。
• holes 是任何孔洞的 索引 数组，如果有（例如，对于一个12个顶点的输入，[5, 8] 表示一个顶点为5-7，另一个为8-11的孔洞）。
• dimensions 是输入数组中每个顶点的坐标数。维度必须是2。

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

// triangulating a polygon with a hole
earcutr::earcut(&vec![0.,0., 100.,0., 100.,100., 0.,100.,  20.,20., 80.,20., 80.,80., 20.,80.], &vec![4],2);
// [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);

GeoJSON多边形格式使用基于文本的JSON格式来存储多维数据。在tests/integration_test.rs目录下有如何解析JSON数据的示例代码。测试文件test/fixtures中的所有文件都是多维.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：在耳剪切之前，多边形上的每个点都通过多边形边界的空间在z-order（Morton）曲线上给出一个坐标。这是一种在许多几何算法中探索过的空间填充曲线策略。请参阅https://en.wikipedia.org/wiki/Z-order_curve

步骤2：巧妙之处在于，如果你想在一个有限的矩形内搜索Z-order曲线填满的空间，你可以相对容易地通过查看它们在z-order曲线上的位置来确定哪些点在盒子内，换句话说，它们的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维点，其中0存在，以及2,1，其中6存在。它还穿过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个点相比，要做的数学和计算要少得多。

额外处理

如果简单的耳朵切割失败，它也会做一些简单的修正，

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

• 自交点 - 移除那些只在多边形中形成一个很小的结，而不贡献于其整体形状的点（这也使它不简单）

• 分割桥 - 实际上把多边形分割成两个单独的多边形，并尝试对每个多边形进行耳朵切割。

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

坐标数值类型

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

权衡

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

如果您想在具有许多自交和耳朵切割不精确的非常糟糕的数据上获得正确的三角剖分，请查看libtess.js。

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

这些算法基于链表，这在Rust中是不是很困难？

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

然而，此代码完全在Rust Vector之上实现了一个循环双向链表，没有任何不安全的代码块。它不使用Rc、Box、Arc等。普通链表节点代码中的指针已被替换为整数，这些整数索引到一个单独的Vector，该Vector存储在LinkedLists结构中的节点。如果使用索引越界，它仍然会崩溃，但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对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++移植版本，内置了基准测试器，以“每秒操作数”来衡量。它还与libtess的C++版本进行比较。然而，默认情况下，它没有进行优化，这妨碍了比较。我们可以解决这个问题。通过编辑.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中，ear_checker内部的point_in_triangle和area函数除非使用inline宏明确指示，否则不会内联。

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

如前所述，此代码实现为一个位于向量之上的双链表，而“指针”实际上是向量的索引。使用了几种宏来表示正常的链表语言，例如next!(index) prev!(index)，它们以索引整数作为输入，并返回一个Node或Node的引用。每个索引使用Rust的内置向量索引，它使用“边界检查”，因此如果意外访问向量范围之外的内存，则会立即panic。panic和backtrace将报告访问发生的行以及太大而无法使用的索引值。

理论上这会减慢程序的速度。实际上，它并没有。这已经经过大量测试，因为next!()和prev!()之类的宏已经以这种方式编写，使得在边界检查的向量索引和使用get_unchecked()的不安全向量索引之间切换变得极其容易，并重新运行'cargo bench water'来比较它们。

水形基准测试表明，除了像water3b这样的微小形状外，差异都在误差范围内，因为这些形状的好处非常微小，对于大多数应用来说不值得。

• 迭代与循环

此代码已将几个JavaScript循环转换为Rust迭代。从理论上讲，这会慢一些。在实践中，它并不慢，在某些情况下，它甚至更快，尤其是在find_hole_bridge中。从理论上讲，迭代器更容易阅读和编写，占用的代码更少，并且错误更少。

其他语言的三角剖分器

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

感谢