Update kinks to use sweepline-intersections library

[rowanwins]

• [x] Use a meaningful title for the pull request. Include the name of the package modified.
• [x] Have read How To Contribute.
• [x] Run npm test at the sub modules where changes have occurred.
• [ ] Run npm run lint to ensure code style at the turf module level.

This replaces the naive algorithm in kinks to use the sweepline-intersections library.

I've added a larger geometry (switzerlandKinked - which has 700 vertices) which really highlights how slow the existing naive implementation is. The existing implementation works ok if dealing with <20 vertices but will quickly grind to a halt as it checks every segment against every segment.

// NEW
---> switzerlandKinked x 1,907 ops/sec ±1.28% (91 runs sampled)
hourglass x 898,096 ops/sec ±6.84% (79 runs sampled)
multi-linestring x 392,678 ops/sec ±1.52% (90 runs sampled)
multi-polygon x 403,615 ops/sec ±2.56% (90 runs sampled)
open-hourglass x 1,197,766 ops/sec ±3.54% (75 runs sampled)
triple x 364,118 ops/sec ±1.31% (88 runs sampled)

// OLD
---> switzerlandKinked x 88.20 ops/sec ±0.78% (75 runs sampled)
hourglass x 3,919,439 ops/sec ±1.87% (90 runs sampled)
multi-linestring x 620,491 ops/sec ±2.10% (73 runs sampled)
multi-polygon x 536,627 ops/sec ±2.36% (67 runs sampled)
open-hourglass x 3,077,403 ops/sec ±3.21% (78 runs sampled)
triple x 804,901 ops/sec ±1.29% (87 runs sampled)

[rowanwins]

In regards to performance - those old benchmarks are done on trivial geometries where the number of edges are between 5 & 10. The new algorithm sets up a few data structures which allow it to scale on larger geometries (eg the switzerland example I added with 700 edges), but that adds some initial overhead. The more edges you have the worse the old brute force algorithm will perform.

Conceivably we could set some arbitrary limit where we use the brute force algorithm in number of edges is < x. What do you think @mfedderly ?

[mfedderly]

Yeah I think splitting based on number of edges is a good solution, some amount of testing would have to be required to figure out what the inflection point is. You could maybe use @turf/circle to generate arbitrarily complex circle polygons to test with

[rowanwins]

@mfedderly - took your advice re the benchmarks with testing for the inflection point using @turf/circle to generate edges and got the following results. So it looks like the infection point is probably around 10 edges.

// New version
steps - 5 x 470,655 ops/sec ±0.72% (93 runs sampled)
steps - 10 x 254,759 ops/sec ±2.27% (93 runs sampled)
steps - 15 x 163,340 ops/sec ±0.30% (94 runs sampled)
steps - 20 x 115,420 ops/sec ±2.33% (91 runs sampled)

// Old version
steps - 5 x 511,895 ops/sec ±2.93% (84 runs sampled)
steps - 10 x 249,804 ops/sec ±1.94% (88 runs sampled)
steps - 15 x 135,428 ops/sec ±1.98% (87 runs sampled)
steps - 20 x 85,685 ops/sec ±1.59% (89 runs sampled)

[mfedderly]

Similar objection here with the compiled code that wound up vendored https://github.com/Turfjs/turf/pull/2033#issuecomment-893682955

[mfedderly]

Same thoughts as https://github.com/turfjs/turf/pull/2033#issuecomment-1014898084 to go back to using the proper npm dependency.