Performance regression in @turf/union from v7.1.0 to v7.2.0

[neave]

There is a significant performance regression in the @turf/union module when upgrading from version 7.1.0 to 7.2.0. Union operations are more than 10 times slower in 7.2.0.

Reproduction Steps

1. Create a test file (e.g., test-union.js) with the following content:

import { circle } from '@turf/circle';
import { featureCollection } from '@turf/helpers';
import { union } from '@turf/union';

const circles = [];
for (let i = 0; i < 1000; i++) {
  circles.push(circle([i * 0.1, 0], 200));
}

console.time('union');
union(featureCollection(circles));
console.timeEnd('union');

2. Install Dependencies with v7.1.0: npm install @turf/circle @turf/helpers @turf/[email protected] Run the test file: node test-union.js Observe the timing output (around 500 ms).

3. Upgrade to version 7.2.0: npm install @turf/[email protected] Run the test file again: node test-union.js Note the increased timing output (around 5.5 s).

Expected Behavior: The union operation should complete in a similar timeframe across these minor versions (around 500 ms for the provided test).

Observed Behavior: • v7.1.0: ~500 ms • v7.2.0: ~5.5 s

This performance degradation is critical, especially for workflows involving large numbers of geometries.

Environment: • Node.js version: 22 • OS: macOS, Ubuntu

Additional Context: This slowdown might be due to changes in the union implementation or dependencies in v7.2.0. Any investigation or fixes to address this regression would be greatly appreciated.

[kade-robertson]

Just looking to confirm that this is due to the change to polyclip-ts. Running the bechmarks from that repo (modified to also include the old polygon-clipping library), polyclip-ts is pretty much always behind by an order of magnitude, if not worse.

Hole_Hole
polyclip-ts x 1,327 ops/sec ±0.47% (96 runs sampled)
w8r x 69,672 ops/sec ±0.30% (98 runs sampled)
JSTS x 7,563 ops/sec ±0.75% (98 runs sampled)
polygon-clipping x 21,782 ops/sec ±0.22% (99 runs sampled)
- Fastest is w8r

Asia union
polyclip-ts x 2.37 ops/sec ±1.13% (10 runs sampled)
w8r x 19.85 ops/sec ±1.99% (37 runs sampled)
JSTS x 27.36 ops/sec ±1.24% (49 runs sampled)
polygon-clipping x 14.31 ops/sec ±2.57% (40 runs sampled)
- Fastest is JSTS

States clip
polyclip-ts x 30.90 ops/sec ±1.03% (55 runs sampled)
w8r x 422 ops/sec ±0.28% (94 runs sampled)
JSTS x 336 ops/sec ±0.63% (90 runs sampled)
polygon-clipping x 333 ops/sec ±0.45% (90 runs sampled)
- Fastest is w8r

Based on what I can see on that repo, it's implied their results are at least the most correct, at least compared to the library its based on, but the drop in performance to achieve this (if it is the case) seems really unfortunate.

Fortunately, the turf methods that use this are relatively thin wrappers around the underlying library, so duplicating the old 7.1 version (or just installing it separately) is pretty doable (ignoring the negative effect on bundle size that might have if that matters for your use case)

[pjreed]

Just wanted to comment that I just ran into this on an existing application where I upgraded from 7.1.0 to 7.2.0 and it absolutely destroyed performance. For now I just rolled back to 7.1.0, but it might be nice if there was an option to select between performance vs. accuracy where necessary.

[smallsaucepan]

Hi @neave, @kade-robertson and @pjreed. Looking at options for this.

First up, I don't believe we can consider going back to polygon-clipping as a default implementation. The results it produces are just plain wrong in many cases.

So per @pjreed's suggestion, as a stopgap we could add an option like "preferSpeed: false" which uses the old polygon-clipping library if overridden to true. Would that serve to restore the performance you need?

Longer term, we can look at another library to leverage. Or perhaps look at ways to work with polyclip-ts to achieve comparable performance, and so be able to retire the preferSpeed flag. Thoughts?

[kade-robertson]

I understand from a practical standpoint it makes sense to focus on polyclip-ts if it is the most correct implementation. I'm indifferent re: adding a preferSpeed option.

It has the downside of introducing an option that then has to be maintained until an eventual turf v8, means at least one dependency is guaranteed to be redundant because presumably, people are only going to be using the "fast" or "correct" version and generally not a mixture, and potentially becomes irrelevant if/when polyclip can match the performance of the alternatives.

On the other hand, it makes it a bit easier for people who already depend on the @turf/turf metapackage to use one version of all the turf dependencies and keep behaviour they like. To me personally I feel like the concession of having to pull in 7.1.0 versions is fine (or just keeping yourself on 7.1.0 in general -- this is also a bit challenging due to https://github.com/Turfjs/turf/issues/2860), but I'm not sure I know what option is best for most turf users.

[kragoth]

The drop in perfromance with polyclip-ts is pretty extreme. While I do like the fact it is more accurate (I've had my share of problems with the old implementation) it has completely destroyed performance in my application. I think polyclip-ts is fine for relatively simple data but once you get into large complex data the performance drop is extreme. It seems though that this is the general tradeoff in the spatial world. You can have fast or accurate but not both.

[smallsaucepan]

Thanks @kragoth. We're weighing up a couple of short term options. Frontrunner at the moment would be a "preferSpeed" option that defaults to false and uses polyclip-ts.

Overriding to true would see intersect, etc use a faster library instead, with the documented caveat that some cases might not produce correct results.

It's not a great solution. For example, we'd then have to expose that option on any other Turf functions that use clipping functions internally. Plus is means bundling two clipping libraries, which might only move the dissatisfaction to those conscious of bundle size.

Having read a bit about the different algos I don't think there is a single one that covers all possible cases. So in lieu of a clipping library that is robust and fast, the above might be the best option. Would be keen to hear your thoughts on that.

[kragoth]

@smallsaucepan yeah, it's a tough one. Over the years I've tried a bunch of different libraries for spatial operations and there's always tradeoffs. I think a prefer speed option at least gives us the ability to control when we want the extra expense for a more accurate operation and this will allow us to keep our library up to date. So, I support the idea at least until something better is available. I'm thinking eventually spatial operations will be performed in a web assembly instead of javascript to allow for significant performance improvements. But, so far I haven't seen one ready for production yet. (If you know of one please let me know ;) )

I've had to revert back to 7.1.0 for now.

[roman0x58]

I've also rolled back to version 7.1.0 because our project involves thousands of polygons used for intersection calculations, and the processing speed increased by about 100 times

[neave]

+1 for a way to opt-in to a “fast mode” vs. an “accuracy mode”, although I understand the added complexity and maintenance that this would introduce. I think the trade-off is necessary or we’ll be stuck using 7.1.0.

[smallsaucepan]

@roman0x58 do you have some example data you'd be willing to share? Or can you describe what you're working with - a gazillion small polys, fewer super complex multipolys, etc?

[kragoth]

@smallsaucepan in my app we are generally working with fewer than 100 polygons but some of them are very complex (6000+ vertices). In one of the examples the union of the polygons went from around 5 seconds to 96 seconds when going from 7.1.0 to 7.2.0. I could try extract the data if that would be useful.

[smallsaucepan]

It would be amazing if you could thanks @kragoth

[roman0x58]

@roman0x58 do you have some example data you'd be willing to share? Or can you describe what you're working with - a gazillion small polys, fewer super complex multipolys, etc?

There are ~2000 regular polygons (agricultural fields) on a map, with a hundred points each, overlapping with one another. I'm using turf/difference and turf/intersect to find intersections and differences between them.

Here's a quick example example

 const features = featureCollection([
   feature(poly1.geometry as Polygon),
   feature(poly2.geometry as Polygon)
 ])
 const intersection = intersect(features)
 const differencePoly1ToPoly2 = diff(features)
 const differencePoly2ToPoly1 = diff(featureCollection([
	feature(poly2.geometry as Polygon),
	feature(poly1.geometry as Polygon)
 ]))

[mourner]

@smallsaucepan got bit by this today too. In my case I'm doing union on a few hundred circles, here's an artificial sample (7.1 is about 8 times faster than 7.2):

const [minLon, minLat, maxLon, maxLat] = [12.61, 39.58, 47.55, 57.47];

const units = [];
for (let i = 0; i < 500; i++) {
  const lon = minLon + Math.random() * (maxLon - minLon);
  const lat = minLat + Math.random() * (maxLat - minLat);
  units.push(turf.circle([lon, lat], Math.random() * 50, {units: 'kilometers', steps: 128}));
}
console.time('union');
const data = turf.union(turf.featureCollection(units));
console.timeEnd('union');