Unintuitive Optimization For Performing Paths Union
I once had the task of processing whatever vector graphics the user would input into the software, and compute the contour of all shapes from that. That contour would then be sent to a printer. Most of the time users would upload vector art they made in something like Illustrator, and that art could get very complex. In this blog post I’ll take one real SVG I had to work with which consists of about 1981 paths.
Computing the contour comes down to performing union on all shapes. Here’s one basic example that illustrates what union is:
So as you can see, it quite literally means getting the contour of everything, without “cutting” inside any shape. Computing union on paths for the general case is extremely difficult to do robustly. The paths uploaded by users are arbitrary: they can self-intersect, they can have overlapping edges, they can have holes (even nested holes), and so on. Fortunately there are existing solutions for this already, like Skia’s PathOps module and Paper.js. I’ve used Skia for this particular task.
The path builder claims it’s even optimized for doing union on everything, so it seems like it’s exactly what I needed. At first I tried the naive version:
