Imagine I have a 2D area where I have many simple polygons ("simple" meaning not self-intersecting, they are not necessarily concave). A polygon is given to me as a series of points. I have between 25 and 150 polygons in my area. I also have several thousand points that I need to figure out if they are inside any of the polygons or not. I need to do this about every second, with a new set of points. The set of polygons stays the same.
I know there are point-inside-polygon algorithms but they seem to be too computationally demanding for the numbers I have, particularly executing on a mobile phone in real time. So an alternative I am thinking is to pre-compute a black and white bitmap of the area (with white areas outside polygons and black inside). One pixel can simply be a single bit. Or you can see the whole thing as a 1D array of true and false values that the whole 2D area maps unto. So using area coordinates x,y we can access an element in that array and get an answer true/false. This will be considerably faster. The problem then becomes constructing this bitmap. Ideally I want this construction to happen at the phone if it's not too costly. As an alternative the phone can download this bitmap.
So how do I efficiently create this bitmap? I can run the point-in-polygon algorithm for successive "pixels" with the resolution I want, but this seems inefficient for 100K-200K "pixels", and probably rules out the phone processing option. I suspect there are more efficient algorithms than that. How do the programs convert SVG images to bitmap for example? I googled a bit, but what I get is the much more difficult problem of bmp->svg, also called vectorisation.
Inspired by the D.W. suggestion I expanded it to an answer. I have not implemented it to tell you what kind of savings I might get but it seems a bit expensive. Happy to receive completely different approaches.
Practically what I am currently doing is rasterising an svg file using public tools/libraries. I am doing this outside the mobile phone, and transfer the image to the phone.