Subset by polygon too slow in some cases

[letmaik]

Use case: #1

In the test polygon dataset (https://raw.githubusercontent.com/chrisfinch/over9k/master/public/experiments/march-2013/GBR_adm2.json) there are some MultiPolygons which have a huge number of vertices, and even after code optimization using typed arrays and tight for-loops (point-in-poly / pnpoly test) it still takes around 1min to calculate for all grid cells whether they are inside the multi polygon or not. And this is after subsetting the area by a bounding box first.

I'm not sure if this can be made much faster. An alternative would be to offer the user (after detecting that it would take too long) the choice of simplifying the polygon first, but this may not be desirable in all cases since then the borders are not as accurate anymore.

Since this problem is perfect for parallel execution it would make sense to use multithreading, but this is still rather complicated in browsers (using web workers).

[letmaik]

Idea: Try HTML5's Canvas context method isPointInPath. This should be faster.

Something like:

var geopoly = [[0,0],[10,0],[10,10],[0,10],[0,0]]
var poly = new Path2D()

poly.moveTo(geopoly[0][0], geopoly[0][1])
for (var i=1; i < geopoly.length-1; i++) {
  poly.lineTo(geopoly[i][0], geopoly[i][1])
}
poly.closePath()
var vctx = document.createElement('canvas').getContext('2d');
console.log(vctx.isPointInPath(poly, 5, 5))

[jonblower]

This is basically what we do at the Java end (the API is almost identical). There is a cost to creating the polygons of course, which could be significant.

[letmaik]

Well, that didn't work, in fact it is way slower. I guess it's because ctx.isPointInPath is not optimized for the case when there are just straight lines, since it accepts generic paths which can be made of arcs for example.

I guess a progress bar is the way forward here. Together with displaying a warning when the product of grid points and polygon vertices is above some threshold, suggesting to grab a coffee or simplify the polygon first.

[letmaik]

I could improve the polygon subsetting speed a lot by using a different library for the point-in-polygon tests. On my machine, the scottish highlands now only need a few seconds, compared to 1-2min. Closing this now, fast enough.