#computational-geometry #polygon #triangulation #graphics #2d-3d #port #coplanar

no-std earcut

A Rust port of the Earcut polygon triangulation library

5 releases

0.4.2 Oct 21, 2024
0.4.1 Apr 18, 2024
0.3.6 Apr 12, 2024

#45 in Science

Download history 2005/week @ 2024-07-22 4976/week @ 2024-07-29 2098/week @ 2024-08-05 3012/week @ 2024-08-12 3353/week @ 2024-08-19 4840/week @ 2024-08-26 3844/week @ 2024-09-02 1830/week @ 2024-09-09 665/week @ 2024-09-16 1688/week @ 2024-09-23 2157/week @ 2024-09-30 2975/week @ 2024-10-07 2439/week @ 2024-10-14 2416/week @ 2024-10-21 2151/week @ 2024-10-28 2816/week @ 2024-11-04

9,875 downloads per month
Used in dda-voxelize

ISC license

1MB
1K SLoC

earcut-rs

Test codecov Crates.io Version

A Rust port of the mapbox/earcut polygon triangulation library, implemented from scratch with some reference to donbright/earcutr.

  • Based on the latest earcut 3.0.0 release.
  • Designed to avoid unnecessary memory allocations. The internal buffer and output index vector can be reused across multiple triangulations.
  • (Experimental) An additional module, utils3d, can rotate 3D coplanar polygons into the 2D plane before triangulation.
  • License: ISC

Benchmarks

on Macbook Pro (M1 Pro)

Polygon earcut.hpp earcut-rs (0.4.1) earcutr (0.4.3)
bad_hole 3.574 µs/i 4.623 µs/i 4.415 µs/i
building 397 ns/i 195 ns/i 604 ns/i
degenerate 142 ns/i 45 ns/i 206 ns/i
dude 5.061 µs/i 6.496 µs/i 8.096 µs/i
empty_square 195 ns/i 74 ns/i 331 ns/i
water 459.6 µs/i 574.5 µs/i 801.3 µs/i
water2 334.1 µs/i 393.9 µs/i 450.3 µs/i
water3 13.12 µs/i 19.21 µs/i 23.46 µs/i
water3b 1.340 µs/i 1.345 µs/i 2.165 µs/i
water4 81.48 µs/i 110.6 µs/i 154.1 µs/i
water_huge 6.906 ms/i 11.0 ms/i 10.90 ms/i
water_huge2 15.38 ms/i 23.60 ms/i 22.35 ms/i

(Earcutr 0.4.3 is not besed on the latest earcut.)

Authors

  • Taku Fukada (@ciscorn) - original author
  • MIERUNE Inc.

Dependencies