Testing whether area around a polygon is obstacle free

1
votes

I have a set of arbitrary rotated filled rectangles plotted on a Cartesian grid (2D integer array, each cell is either 0 - empty space or 1 - rectangle pixel) and would like to test whether a particular rectangle has any obstacles around it given that the center of rectangle is known along with the coordinates of its four edges.

For example, let's say we want to test if rectangle is obstacle free 5 units from either of its edges. Rectangles marked with green dot are ok, while the unmarked are clearly collide. enter image description here

It seems trivial for non rotated rectangles however, I am having a hard time coming up with algorithm which can handle rotated rectangles. Simply looping starting from the center till we hit empty space and then checking for obstacles in the empty space doesn't seem to work if rectangles are touching each other.

1
algorithm
What about computing the distance from each vertex to each edge for each rectangle in question? This assumes you have easy access to each vertex for the rectangles, which I don't know if it's true. – SirGuy
If you are willing to use the L1 norm (Manhattan Distance) then you can run a flood-fill algorithm that will give a buffer of distances from the rectangle you are checking. Then you just check whether a bit is set is in a cell with a distance less than 6. Whether this will be faster or slower than my previous comment depends on your set up. – SirGuy
I think mixing pixels and vectors here is causing a bit of confusion. Using just the coordinates of the edge line segments you can easily calculate whether two rectangles intersect, no need to consult the pixel data. – biziclop
@biziclop The question isn't quite about intersecting rectangles, but your point still stands. – SirGuy
@GuyGreer flood-fill trick seems like it might just work. Thanks! – orom

1 Answers

0
votes

Since you seem to be operating with an image-oriented mindset, you can use image processing.

  1. Apply a radius-2.5 dilation filter to your image.
  2. Treat the image as a graph where there is an edge between two pixels if they both have a red value above some threshold.
  3. Any rectangles that have a path between them are at most 5 apart. (Although, note that this will give you the transitive closure of the "too close" relationship.)