Efficient rasterisation of vector image with polygons

Question

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.

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.

Answer 1

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.

Answer 2

The quad tree suggestion by D.W. is interesting. I want to expand on it here. The principle of it is to break the area into big (and then progressively smaller) squares and check whether these squares are fully in or fully out of any polygon. Let's call these cases "black" and "white" respectively. If a big square is either black or white you do not have to check all their pixels, so you save some p-in-p tests. If a square is "grey" (meaning some of it is in and some is out of polygons) we just go to the smaller sized squares in the progression. For the smallest possible size we just make an assumption: e.g. if it's partially in we consider it fully in.

The problem then becomes how do we check whether a square is fully in or fully out of any polygons. This is not a trivial task. For example we cannot simply check whether the four corners of the square are in/out and be done. For example look at this image below that shows a square that all of its corners are within a blue polygon, but not all of the square is in the polygon.

So checking for just the corners of the square is not enough, we have to check if the sides of the squares intersect with any of the sides of the polygons (if they cross the square is "grey"). I then discovered that this is not enough either. What if a polygon is entirely inside a square? There will be no intersecting of sides but still the square is grey. The image below shows all the cases we need to check to decide if a square is "grey" "black" or "white".

This is the test to check for the "colour" of the square:

• Check the four corners of the current square: are they all either inside the same polygon or all outside of any polygon? No: the square is grey. Yes: look at next cases.
• Case: all corners are inside the same polygon, do the sides intersect the sides of the polygon? Yes: square is grey, No: square is black
• Case: all corners are outside all polygons. Do the sides intersect the sides of the polygon? Yes: square is grey, No: go to the next case
• Case: All corners outside polygons and no intersection of sides. Are any polygon points inside the square? Yes: square is grey. No: square is white.

I have not implemented this method to check its efficiency but as you can see it involved several (and potentially hundreds) expensive operations for each square. So we will see a significant benefit only if the boundaries are forming big blobs of space without much detail.

Any feedback on this approach is also welcome.