mapbox / delaunator

An incredibly fast JavaScript library for Delaunay triangulation of 2D points
https://mapbox.github.io/delaunator/
ISC License
2.33k stars 142 forks source link

Precalculate distances for sort #33

Closed RReverser closed 6 years ago

RReverser commented 6 years ago

Backports distance caching optimisation from Rust: https://github.com/mourner/delaunator-rs/pull/3

Some data points from benchmark from my machine (before/after) for 1M points:

uniform:    1624.276ms 1437.700ms
gaussian:   1522.548ms 1287.702ms
grid:       1369.310ms 1212.476ms
degenerate:  758.197ms  403.011ms