1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm thinking it might be cleaner to ask your new question (how do I test whether a polygon is wholly contained in a square? how do I test whether it wholly contains a square?) separately. $\endgroup$ – D.W. Mar 4 at 6:26
  • $\begingroup$ @D.W. The solution is mostly there, I'll refine it and post it as an answer $\endgroup$ – Thanassis Mar 4 at 6:37
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your suggestions and the quad-tree reference (+1). My understanding of what you suggest is this: limit the point-in-polygon operations for the real-time task. But I do not want to do any p-in-p operations for the realtime task, that's why I am suggesting the bitmap idea. I am not sure how a quad-tree would help me with creating the bitmap. Is it better to construct the quad tree and then test every point, or jump straight to test every point? It's not clear how to construct the quad tree in the first place. Presumably I would need p-in-p operations. $\endgroup$ – Thanassis Mar 3 at 12:46
  • $\begingroup$ @Thanassis, a bitmap doesn't let you avoid point-in-polygon tests, because of "grey" pixels that are partly but not completely covered by a polygon (those will still require a point-in-polygon test). You can think of a quadtree as multiple bitmaps: one of size $2\times 2$, one of size $4\times 4$, one of size $8 \times 8$, etc.; except that the bitmaps are stored in a compressed way that saves space. Because the set of polygons stays the same, it's presumably ok if constructing the quad-tree takes longer. Yup, you'll need p-in-p tests or something like it to construct the quad-tree. $\endgroup$ – D.W. Mar 3 at 16:16
  • $\begingroup$ Thank you for your reply! Of course I will need p-in-p tests to construct the bitmap. My rationale is that after I put all the hard work to construct the bitmap, it will be a simple table lookup after that. After I have the bitmap I do not care about grey points. I accept I will lose some accuracy due to quantisation, and that's fine. My question was "can I construct the bitmap somewhat faster?" Quad trees maybe an idea that saves me from testing every pixel in the bitmap, but it is not clear how it will work. I'll update the description of the question with my understanding of this. $\endgroup$ – Thanassis Mar 3 at 22:26
  • 1
    $\begingroup$ An alternative to quad-trees is to use binary space partitioning. en.wikipedia.org/wiki/Binary_space_partitioning $\endgroup$ – Pseudonym Mar 4 at 5:51
1
$\begingroup$

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. counter example

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". cases for grey, black, or white squares

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.