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.
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.
This seem like more of a surprise to the author than it was for me.
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 $$$.
Sometimes it would help to read a book or consult someone more knowledgeable though.
From the very good, yet sadly HTTP http://thecodelesscode.com/case/195
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.
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!
def perform_union_dnc(paths):
if len(paths) == 0:
return None
if len(paths) == 1:
return paths[0]
middle = len(paths) // 2
left = perform_union_dnc(paths[:middle])
right = perform_union_dnc(paths[middle:])
return perform_union_naive([left, right])
It's not exactly the same algorithm (top-down merging instead of bottom-up) but the performance should be very close.Also, it can be optimized to avoid temporary lists if that turns out to be a win.