Speeding up point-in-polygonby punkish (Priest)
|on Jul 23, 2006 at 17:07 UTC||Need Help??|
punkish has asked for the
wisdom of the Perl Monks concerning the following question:
There are many threads on point-in-polygon analyses, and much published elsewhere. I know how to do it, but my problem is of speed. I am using the algorithm in the Wolf Book, and it works well. So, given an array of points (x,y pairs), and an array of polys (an array of array of points), I do the following --
I have more than 5 million points, and more than 200k polys, leading to a possible 1 trillion intersections to be computed... obviously less than that because of last POLY, nevertheless, a pretty tedious task.
I seek advice on how to speed this up. Several thoughts come to mind, some difficult, some perhaps not so --
when small people start casting long shadows, it is time to go to bed