Speed improvement about polybooljs HOT 8 CLOSED

I've opened a PR with the code change, and updated the demo notebook which was broken (because the temporary build file had disappeared).

from polybooljs.

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!

from polybooljs.

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.

from polybooljs.

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

from polybooljs.

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.

from polybooljs.

@Fil Do you plan to open a MR to integrate your changes? 😊

from polybooljs.

@Fil Does polygon-clipping implement this sorted array solution you are suggesting?

from polybooljs.