CODEWITHSUNDEEP
algorithm
orom
orom

Reputation: 871

Testing whether area around a polygon is obstacle free

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.

Upvotes: 1

Views: 60

Answers (1)

Timothy Shields
Timothy Shields

Reputation: 79631

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.)

Upvotes: 0

Related Questions