mourner
Eliminate performance bottlenecks
The library doesn't yet implement Seidel's main idea of randomizing input and building trapezoidation in batches, because currently querying points in the trapezoid query structure isn't a bottleneck.
E.g. monotone mountains extraction from the trapezoidal map happens in nlog(n), because for each edge, collected mountain vertices need to be sorted by the axis of monotonicity. Sort operation is nlog(n). There must be a faster way to do this.
https://github.com/mapbox/seidel/blob/master/src/trapezoid.js#L65-L71
Here's the current performance breakdown:
Query structure search only takes 3.5%, whereas it's the main target of optimization of Seidel's randomized idea in the paper (improving tree balance, building trapezoidation in edge batches for faster queries, etc). It's probably a clue that something really inefficient is going on elsewhere (trapezoid splitting, collecting mountain points and triangulating mountains are real bottlenecks).
Worth noting that even with the current bottlenecks, it's already significantly faster than poly2tri.js. Sure it produces much worse triangulation quality, but for some applications triangulation performance is much more critical (e.g. when it happens real-time in the browser).
Performance is much better now. Splitting trapezoids is still a bottleneck though.
typical OSM building (15 vertices):
seidel x 74,740 ops/sec ±0.69% (98 runs sampled)
libtess x 22,402 ops/sec ±0.56% (100 runs sampled)
poly2tri x 29,617 ops/sec ±1.16% (94 runs sampled)
seidel is 152% faster than poly2tri (second fastest)
dude shape (94 vertices):
seidel x 9,294 ops/sec ±0.82% (99 runs sampled)
libtess x 4,368 ops/sec ±0.58% (100 runs sampled)
poly2tri x 3,979 ops/sec ±1.09% (96 runs sampled)
seidel is 113% faster than libtess (second fastest)
monkey (1204 vertices):
seidel x 593 ops/sec ±0.79% (97 runs sampled)
libtess x 353 ops/sec ±2.16% (93 runs sampled)
poly2tri x 273 ops/sec ±0.83% (89 runs sampled)
seidel is 68% faster than libtess (second fastest)