Unintuitive optimization for performing paths union (opens in new tab)

Of course it's not optimal, it was simply a pragmatic trade-off. This wasn't the only case with lots of paths, and the divide-and-conquer approach improved the runtime performance substantially on all of them.

What you are proposing is valid, however the “checking each intersection” part is far from a simple one. It's difficult enough with polygons only, but the input can have Bézier curves too. I highly doubt everything would amount to Log(n) - after all Skia already does something similar to what you're saying, unless I'm misunderstanding.

> When a rabbit is placed inside the Black Box and vanishes on cue, it is the audience’s privilege to simply ooh and aah in wonderment. But we who step on stage should know how the trick is done. The loss of innocence is the price of applause.

From the very good, yet sadly HTTP http://thecodelesscode.com/case/195

> I’d say the takeaway is that treating everything like a black box doesn’t produce good results (sometimes). And not knowing enough to open the box completely leaves you with a lot of unknowns, surprises, and loose ends. But hey, figuring this stuff out is why we get paid the $$$.

To add a little bit of nuance to your comment, I've to say that computational geometry algorithms are incredibly human-effort-intensive. Treating their implementations as a black-box could be an incredible time-saver. In my experience however, that particular black box tends to fail when least one needs it, and then one is left with inscrutable pieces. Often the "least bad" approach is to learn how polygon/polyline composition works and implement it oneself. It will be buggy and crappy (at first) but it won't break in cryptic ways. Budget a couple of months for the learning and initial implementation though, and be most wary of floating point and God coming in the night to mess with your code and put new bugs.

> This seem like more of a surprise to the author than it was for me.

The bigger surprise for me was that the path builder is slower than doing divide and conquer, given that it's optimized for doing union on everything.

> Sometimes it would help to read a book or consult someone more knowledgeable though.

I'd be happy to receive suggestions!

I didn't get to simplify the code further unfortunately. I could have, but I was running very tight on time with other things. In fact the running-in-production-version is even worse than what I've posted, I just went with what worked fast on the first try and moved on to something else immediately. But it can absolutely be improved further!