2
$\begingroup$

I have a program that, among many other things, checks to see if a Rectangle is at all overlapping with another rectangle - meaning, if any of the points of one rectangle is inside another given rectangle, they are overlapping. A rectangle is defined by its top-left point and its bottom-right point - I think this is more commonly known as a "bounding box". Here is the code I have for checking this:

def overlaps(self, other):
        """
        Return true if a box overlaps with this box.
        A Box class has 8:
        self.left                           left side
        self.top                            "top" side
        self.right                          right side
        self.bottom                         bottom side
        self.lt                             left-top point
        self.rb                             right-bottom point
        self.rt =                           right-top point
        self.lb                             left-bottom point

        A "point" is an x,y coordinate. 
        """
        if(self.lt.x > other.rb.x or other.lt.x > self.rb.x):
            return False
        elif(self.rb.y < other.lt.y or other.rb.y < self.lt.y):
            return False
        else:
            return True

If you are wondering, that this basically does is check two things:

  1. Is one rectangle above the top edge of the other rectangle?

  2. Is one rectangle on the left side of the left edge of the other rectangle?

If any of those are true, the function returns false.

So, this works fine (if you have any suggestions, let me know. However, now I want to calculate how much "percentage" overlap there is. Essentially, there are some boxes I want to "filter out" if they don't overlap with, say, a 40% percent overlap. I'm not too sure how to do this efficiently thought.

My idea was to find the "Point" of the other box that is inside the self box, then just do some simple math to figure out the area inside that box - but this only works if there is only on point - if there are two or three it gets a bit more complicated. Not too sure how to attack this. Any help would be appreciated!

Thanks

$\endgroup$
2
  • $\begingroup$ Your "40% overlap" would mean taht the surface overlaping is 40% of the surface of which rectangle ? $\endgroup$ – Evargalo Sep 28 '17 at 16:13
  • $\begingroup$ I want to know if, say, 40% of the other rectangle is contained inside the self rectangle $\endgroup$ – John Lexus Sep 28 '17 at 16:14
6
$\begingroup$

For the equations, I will let the left of the first rectangle be $l_0$, the right be $r_0$, the top $t_0$ and the bottom $b_0$. The second rectangle is $l_1, r_1, $ etc. Their areas will be $A_0$ and $A_1$.

If the boxes don't overlap, obviously the percentage overlap is $0$.

If your boxes are found to be colliding, simply use this formula to calculate the area that is overlapping:

$$A_{overlap} = (\max(l_0, l_1)-\min(r_0, r_1))\cdot(\max(t_0, t_1)-\min(b_0, b_1)).$$

Now there are two ways to calculate a percentage error that could make sense for your explanation. If we're just checking the percentage within the first rectangle (or "self" in your program), the percent overlap is simple: $$P_{overlap} = \frac{A_{overlap}}{A_{self}}.$$

If you want the percentage to be equal whether it's calculated from either rectangle, the equation you're looking for is: $$\frac{A_{overlap}}{A_0+A_1-A_{overlap}}.$$

$\endgroup$
2
  • $\begingroup$ I didn't see this - this is exactly what I was looking for. Thanks! $\endgroup$ – John Lexus Oct 6 '17 at 15:08
  • $\begingroup$ For some one who is confused about the coordinates. They are as follows. `` rect 0 - (l<sub>0</sub>,t<sub>0</sub>), (r<sub>0</sub>,t<sub>0</sub>),(r<sub>0</sub>,b<sub>0</sub>),(l<sub>0</sub>,b<sub>0</sub>) rect1 - (l<sub>1</sub>,t<sub>1</sub>), (r<sub>1</sub>,t<sub>1</sub>),(r<sub>1</sub>,b<sub>1</sub>),(l<sub>1</sub>,b<sub>1</sub>) `` $\endgroup$ – Gayan Kavirathne Jun 5 '20 at 8:55
1
$\begingroup$

You can solve this by distinguishing cases:

  • If one corner of the other rectangle is in the self rectangle, you use the ratio of two rectangles: the overlap divided by the other.

  • If two corners are in, you just use a ratio of distance along the coordinate those two corners have in common. For instance, if $self.lt.x<other.lt.x<self.rt.x<other.rt.x$ and $self.lb.y<other.lb.y<other.lt.y<self.lt.y$, then $ratio=\frac{self.rt.x-other.lt.x}{other.rt.x-other.lt.x}$

  • If four corners are in, well, the answer is 100%.

$\endgroup$
2
  • 2
    $\begingroup$ Did I really say what if three corners are in? $\endgroup$ – John Lexus Sep 28 '17 at 16:26
  • 1
    $\begingroup$ Thanks, this makes perfect sense $\endgroup$ – John Lexus Sep 28 '17 at 16:26
0
$\begingroup$

@John Lexus Find cutting points in a $4\cdot 4 =16$ cases. Plot corners and cutting points together. You can proceed from there.

$\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.