30
$\begingroup$

I have a problem where I have TWO NON-rotated rectangles (given as two point tuples {x1 x2 y1 y2}) and I like to calculate their intersect area. I have seen more general answers to this question, e.g. more rectangles or even rotated ones, and I was wondering whether there is a much simpler solution as I only have two non-rotated rectangles.

What I imagine should be achievable is an algorithm that only uses addition, subtraction and multiplication, possibly abs() as well. What certainly should not be used are min/max, equal, greater/smaller and so on, which would make the question obsolete.

Thank you!

EDIT 2: okay, it's become too easy using min/max or abs(). Can somebody show or disprove the case only using add/sub/mul?

EDIT: let's relax it a little bit, only conditional expressions (e.g. if, case) are prohibited!

PS: I have been thinking about it for a half hour, without success, maybe I am now too old for this :)

  • 0
    I thought because the area of a square would be calculated as (a-b)*(c-d), a negative area would mean that the area is rotating in the other direction (if you use vector). But I think the question is ill-posed anyways. Sorry for wasting time....2012-01-17

1 Answers 1

58

Uses only max and min (drag the squares to see the calculation. Forget about most of the code, the calculation is those two lines with the min and max):

http://jsfiddle.net/Lqh3mjr5/

You can also reduce min to max here (or the opposite), i.e. $min\{a,b\} = -max\{-a,-b\}$.


First compute the bounding rectangles rect1 and rect2 with the following properties:

rect = {   left: x1,   right: x1 + x2,   top: y1,   bottom: y1 + y2, } 

The overlap area can be computed as follows:

x_overlap = Math.max(0, Math.min(rect1.right, rect2.right) - Math.max(rect1.left, rect2.left)); y_overlap = Math.max(0, Math.min(rect1.bottom, rect2.bottom) - Math.max(rect1.top, rect2.top)); overlapArea = x_overlap * y_overlap; 
  • 0
    Can you clarify the difference between x12 and x12? They can be interpreted in opposite ways, no? Should I read x12 as "x1 from rectangle 2" or "x2 from rectangle 1"?2017-08-10