Unintuitive optimization for performing paths union

Unintuitive optimization for performing paths union(minus-ze.ro)

27 points by vg_head 1 year ago | 8 comments

rurban 1 year ago |

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.

vg_head 1 year ago | |

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.

fn-mote 1 year ago |

Spoiler: divide and conquer is the way to go. Adding paths one at a time to a massive union is slow.

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.

dwattttt 1 year ago | |

> 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

dsign 1 year ago | |

> 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.

vg_head 1 year ago | |

> 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!

sebastianmestre 1 year ago |

Please tell me that, after noticing that the best interval length is 2, you simplified your implementation to something like this

    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.

vg_head 1 year ago | |

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!

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])