mapbox / delaunator

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

Eliminate recursion with a fixed-size stack #35

Closed mourner closed 5 years ago

mourner commented 5 years ago

Managed to get a perf win with recursion elimination here too — but in a simpler/faster way, by only increasing the stack once on each illegal edge. cc @delfrrr

delfrrr commented 5 years ago

Need to spend time on it to understand why it will produce the same result 😯

mourner commented 5 years ago

@delfrrr basically, it "recurses" (increases stack) only in one direction, while the other one just runs as the next iteration of the loop (while keeping a value).