polybooljs
polybooljs copied to clipboard
velipso
Speed improvement
I've been testing polybooljs on large polygons, and found that it was not scaling too well. The problem is that finding the point of insertion in a linked list means going through the list one link at a time, and doing a comparison each time—at a O(n) cost for each segment. I figured we could change that by using a sorted flat list (or array) instead, and finding the insertion point by bisection, resulting in a O(log n) insertion cost.
I've implemented that solution here: https://github.com/Fil/polybooljs/commits/sorted-array
Test here https://observablehq.com/d/a7fc92f18bc1365a
wow, cool!
this looks great, do you have a summary of the results? I see a CSV table in the link provided, but not sure how to read it
I looked at the code, it makes sense why it would be faster, since it isn't going straight through the list, but is instead searching for the best spot
The table was an initial measurement of things, to get a sense of where time was spent. I should remove it. In my test with lots of polygons the computation is about 50x faster than the original—but we should have a real benchmark. Note that the improvement is O(n/ln n), so growing as the polygons become more complex.
I've opened a PR with the code change, and updated the demo notebook which was broken (because the temporary build file had disappeared).
Just wanted to mention I've pulled and used this and it works very well. Speed for working with polygons with thousands of vertices has gone from 25 seconds to less than 2 seconds. THANKS for this.
I only found it after I dug into the code and thought "hrm, linked lists are very slow, I'll change it to a sorted array" and then went to check if there was a newer code version and, hey, what's this PR... I was very happy you'd saved me the work!
You can also check out https://github.com/mfogel/polygon-clipping — I found it to be quite robust, and fast; see https://observablehq.com/@fil/hello-polygon-clipping for example usage.
@Fil Does polygon-clipping implement this sorted array solution you are suggesting?
Thank you so much for this! I incorporated this into the TypeScript port I made recently, here: https://github.com/velipso/polybool .