Hacker News Reader

Divide and conquer is suboptimal, esp. with so many polygons. You just had luck.

You'd need to sweep over all polygons at once, checking each intersection, and there the angles. This requires some ad hoc preparation. Log(n) instead of exponential. A modified Graham scan or Bentley - Ottoman scan.

View on HN

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.

Reply on news.ycombinator.com