in reply to Speeding up point-in-polygon

How often will you need to perform such task? How big are polygons? How many polygons can you store in memory at once?

Reading the polygons from file at every turn of the cycle is surely a bad idea. You need to store as many polys as you can in the memory and match the points against them. then throw away all matched points, as the polygons don't intersect, and match all left points against the next portion of polys. This advice is true in any case.

Maybe you can improve your matching function — look at the source code of Math::Poly::Calc, the polygon_contains_point() sub. Rewriting it as XS will be even faster. The algorithms can be found here. This is a hard way to go—do it only if the memory caching does not give enough performance gain.

These simple optimizations might not be enough if you need to perform this task often, and they will work better in combination with bobf's algorithmic improvements.


     s;;Just-me-not-h-Ni-m-P-Ni-lm-I-ar-O-Ni;;tr?IerONim-?HAcker ?d;print