Hole cutting performance

[fernap3]

Hi all. I've been using earcut (through ThreeJS) for a while with great results. I have been thinking for a while on whether or not is is possible to eek out any additional performance on hole-cutting. In my use case, I cut hundreds or thousands of holes in a single polygon, and it would be high value if there is any way to make this faster. Things I've considered:

• Parallelism doesn't seem to be an option here. I am dealing with cutting holes in one polygon, and hole-cutting does not seem to be parallelizable since each hole cut mutates the geometry. So it seems like we cannot "divide and conquer" hole cutting
• eliminateHoles itself seems to be almost entirely arithmetic and linked list operations. After several hours spent here, there are no obvious wins for micro optimizations. Specifically, findHoleBridge is showing as the bottleneck in my testing, but I'm not really sure if anything can be done there.

Really I'm just posting this to see if anyone has some insight into how hole cutting might be made faster. I am certainly motivated to contribute any work myself.

Thanks!

[mourner]

Yeah, that's something I've been worried about myself — it consistently shows up as the biggest bottleneck on practical applications such as triangulation polygons in OSM data for map rendering (water bodies in particular have tons of holes). On GL JS side, the only hack we came up with is to sort all holes by area and discard all but the biggest 500.

So far the only idea I have come up with is to explore whether the eliminateHoleBridge search can be accelerated with the zOrder indexing that kicks for points in on higher counts, but haven't thought through any specifics yet.