Optimally search for which positions a rectangle is within a polygon, faster way than using shapeID of union?

Hi all,

I want to check wether blue rectangle is completely within the red shape. Currently I do this I do this by defining a grid for the center point of the blue rectangle (the black x) and then for all these positions I check using the shapeID of the union function (see below) whether the rectangle is within the red polygon. To speed this up I use a rough grid away from the edges and a much finer grid close to the edges. However, if I want to determine this with a high accuracy (and thus a very fine grid), this will take a long time to determine. Is there an efficient/quick way to do this? Or do you have ideas how to speed this up? Inpolygon is even slower, since you need to divide the edges of the rectangle also in smaller sections to do the check accurately.

        [~,shapeID,~] = union(poly_range,poly_rect);    
        all(shapeID == 1);

Kind regards,

Bas

[Matt J]

Why did you remove the figure illustration of your region? It makes your question much harder to understand, retroactively. Here is the original version, restored from Google Cache:

I want to check wether blue rectangle is completely within the red shape. Currently I do this I do this by defining a grid for the center point of the blue rectangle (the black x) and then for all these positions I check using the shapeID of the union function (see below) whether the rectangle is within the red polygon. To speed this up I use a rough grid away from the edges and a much finer grid close to the edges. However, if I want to determine this with a high accuracy (and thus a very fine grid), this will take a long time to determine. Is there an efficient/quick way to do this? Or do you have ideas how to speed this up? Inpolygon is even slower, since you need to divide the edges of the rectangle also in smaller sections to do the check accurately.

[~,shapeID,~] = union(poly_range,poly_rect); 
all(shapeID == 1);

Answer 1

[Matt J]

If the red shape is fixed and you want to do this test for a swarm of blue rectangles, a good strategy may be to decompose the red area into the union of a small number of convex shapes. For the red shape that you've shown, this can be done by decomposing it into 2 half circles and the 3 red rectangles. Then you can use inpolygon to test whether the vertices of the blue rectangle all lie within the same convex subregion.

This is only a sufficient condition for containment and is not a conclusive test, but if you have a swarm of blue rectangles throughout the red shape, it could eliminate a large number of the rectangles that need to be tested with your current, slower method.

Also, assuming still that the red shape is fixed, a faster method of testing containment than inpolygon would be to pre-convert the convex red subregions to inequality form A*x<=b and just test to see if the vertices satisy the inequality.

Answer 2

[Aditya Patil]

As the outershape is not convex, there is no quick way to surely say that the rectangle is inside the polygon.

One alternative is to sample the edges of the rectangle randomly or uniformly and then use inpolygon. Note that inpolygon has GPU and parallel computing support, so you might gain some performance there.

Also, if you project the polygons to an axis parallel to the axes of the rectangle, then sampling the edges will be straightforward. If you are checking multiple rectangles for the same polygon, then this is probably the best approach, as the cost of projection will be amortized over multiple calls to inpolygon.