CODEWITHSUNDEEP
pythonnumpygeometryrectanglesbounding-box
Autonomous
Autonomous

Reputation: 9075

Find outer non-overlapped region coordinates

TL; DR: Trying to find out the coordinates of the green region in O(1) time. The input is two sets of (top_left, bottom_right) points. So [x_min_1, y_min_1, x_max_1, y_max_1] and [x_min_2, y_min_2, x_max_2, y_max_2]. Output should be [x_min, y_min, x_max, y_max] for the green dotted rectangle.

Looks like an easy problem but I have been trying to find an efficient solution to this. I have a yellow rectangle and another orange rectangle always inside OR on the yellow rectangle. I would like to find the coordinates of the non-overlapping region of the yellow rectangle. Figures can explain this better.

Illustration

Constraints:

In the left figure, even though the orange rectangle is partially occluding the yellow rectangle, if we try to tightly wrap a box around the visible pixels of the yellow rectangle, we would get the box denoted by green dotted line. I want the coordinates of the green box.

In the right figure, the visible pixels of the yellow rectangle are traced by the green dotted line, which unlike the left figure, do not cover the entire yellow rectangle.

I wanted the coordinates of the green box as the output. Is there an O(1) solution to this?

Easy and computationally expensive solution would be to do np.where on yellow pixels and find the coordinates of the green box by taking min and max of the np.where output.

Upvotes: 0

Views: 100

Answers (1)

Jeff
Jeff

Reputation: 1264

If I understand this correctly, the only the time the green box does not coincide with the entire yellow rectangle is when the orange rectangle occupies an entire edge, i.e. when two of its adjacent corners are the same as the yellow rectangle. So you really only need to compare the corners of each rectangle. There are three general cases:

  1. Zero or one of the corners are the same: green is the entire yellow rectangle
  2. All of the corners are the same: ??? (not sure what you want to do when they completely overlap)
  3. Two adjacent corners are the same: the interesting case

In case (3) the green rectangle is composed of the four non-equal corners: two of yellow's and two of orange's.

Upvotes: 0

Related Questions