slow booleanOverlap performance vs very fast booleanWithin

[gplv2]

Hi,

I'm using the latest npm turf modules browserified. The code I created compares many geometries to eachother, trying to find geometries that are within others is really fast in the browser. crosschecking 3000 polygons vs itself is super fast , less than 1 second in chrome. (linux platform)

I added the same check , same code with booleanOverlap and it almost takes a minute to run over this same set (excluding testing the positive matches found with booleanWithin. The fans kick in, the CPU goes 170%.

Is there a known issue with the efficiency / performance of booleanOverlap ? Can I help analyse / assist in finding a more optimized way ? Is this by nature a hard math job to do ?

And lastly, are there any alternative approaches to detect polygons that partially overlap ?

Thanks for turf.js too, it's pretty awesome to work with. Let me know if I can help

[twelch]

Thanks for asking. I encourage you to look at the source, it's quite readable.

boolean-within checks that each point in polygon 1 is within polygon 2. That is quite fast. It also first makes sure the 2 polygons bbox's overlap. Even faster. (https://github.com/Turfjs/turf/blob/master/packages/turf-boolean-within/index.ts#L81)

boolean-overlap on the other hand is testing that at least 1 line segment in polygon 1 intersects with a line segment in polygon 2. This is done one segment at a time and I don't see bbox checks up front (not sure why) - (https://github.com/Turfjs/turf/blob/52a4419bfc5d2c5231c81ba075706e20c8de4987/packages/turf-boolean-overlap/index.ts#L81).

Possible improvements to boolean-overlap off the top of my head (contribution welcome)

• Add a bbox check to boolean-overlap for the polygon case, like boolean-within does.
• The function seems to compare all line segments in polygon A with all in B, every single one, and returns true if number of overlaps is > 0. It seems like it could bail out and return true once it finds one intersecting segment? (https://github.com/Turfjs/turf/blob/52a4419bfc5d2c5231c81ba075706e20c8de4987/packages/turf-boolean-overlap/index.ts#L81)
• The hot loop of boolean-overlap uses the line-intersect module, which can take single line features, or a collection as arguments. Instead of calling intersect for each pair of line segments, it may be possible have one or both inputs be a collection of line segments. So like lineIntersect(segment1, segments2) or lineIntersect(segments1, segments2) (https://github.com/Turfjs/turf/blob/master/packages/turf-boolean-overlap/index.ts#L83)

I also saw this library in searching open issues: https://github.com/dpmcmlxxvi/de9im

[gplv2]

Thanks a lot for this detailed information , I think I'll be giving it a try to improve this, it's so perfect for my goals. cheer!

[gplv2]

Hi,

The intersects code of de9im is really fast (order turf isWithin). Quite interesting. Looking at the turf code to see where I can improve is not straightforward for me, I see and es and a js directory in the node module, not sure how/where any modification should be made to try to improve this, I know js decently but never went into module/plugin coding. Any pointers to some documentation would be well appreciated.

Still thanks a lot for pointing out that project. I would still be interested in tackling the turf performance.