Efficient rasterisation of vector image with polygons Imagine I have a 2D area where I have many simple polygons (&quot;simple&quot; 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 &quot;pixels&quot; with the resolution I want, but this seems inefficient for 100K-200K &quot;pixels&quot;, 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-&gt;svg, also called vectorisation.
Update
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.
An alternative approach is to use a quad-tree.

One approach is to store each polygon in the deepest node that corresponds to a region that wholly contains the polygon.  Given a test point, you traverse the quad-tree, and when you visit a node, you do a point-in-polygon test for each polygon associated with that node.  This then lets you do a smaller number of point-in-polygon tests.

An alternative approach is to continue subdividing each region recursively.  Stop subdividing when a region intersects with at most 2 polygons (or replace 2 with any other constant) or when you have hit some maximum depth, mark that as a leaf node, and associate those polygons with the leaf node.  Given a test point, you traverse the quad-tree until you hit a leaf node, then you do a point-in-polygon test for each polygon associated with that leaf node.  This trades space for time: it uses more space (more quad-tree cells) but uses fewer point-in-polygon tests.

It should be straightforward to build either type of quad-tree.

You can think of a quad-tree as a recursive version of your bitmap idea, where the bitmap is stored in a sparse way (large regions of all-white or all-black can often be collapsed to a single node), and where you have an image pyramid of bitmaps.