I have the impression that usually (I'm thinking of 3D modeling and raytracing, in the first place), these polygons tend to be grouped in cluster areas of relatively small sizes. You should therefore group the polygons in polygon groups, create an outside box or a superpolygon (the polygon that contains all polygons in the group) and check if a point is inside that superpolygon. If not, you can skip the whole group.
As a very rough example, suppose you can split your screen into 4 quadrants, each containing about 1/4 of the polygons. You test for each point if it falls in such a quadrant, and only for that quadrant, test the polygons in the way you did. You'll get an average speedup of close to 4x already.
For maximum effectiveness, you should get a lot of those groups first, that all span as little area as possible. So, the object is to get groups out of all of your polygons first, so this splits up into as small area as possible. The areas may overlap, but preferable as little as possible...
So, how can you achieve that?
For a start, I'd take out the really large polygons. You'll likely have to brute force those anyway.
But I suspect most polygons will be really tiny, almost not much larger than dots. Well, you could try using clustering algorithms for dots — on their centers of gravity, for example.
To put those into groups, there's the algorithm that belg4mit asked about a little while ago. You could try that out for size. Oh yeah, I turned that into Perl code. I almost forgot. ;-)
In reply to Re: Speeding up point-in-polygon
by bart
in thread Speeding up point-in-polygon
by punkish
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |