28
$\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
    You seem to hope to get an answer using only the field operations ($+$, $-$, $\times$, and $/$). But can you get a formula for the distance between two points on the real line using only those tools? Failing to do so should persuade you that your hope is forlorn.2012-01-16
  • 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

55

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; 
  • 4
    Also, if you really don't want to use max, note that max(a,b)=(|a-b|+a+b)/2.2012-01-16
  • 0
    thanks for the answers. It looks like it's easy using non-continuous functions. I was asking this question because my stomach told me that this should be in a form, e.g. Area = A*B-C*D+(A-C)*(B-D). Essentially something without the if condition (max is like if(a>b)?a:b though)2012-01-16
  • 2
    @chaiy Since the function that takes vertices and returns area is not differentiable, it is not possible to construct this function out of differentiable functions. You *must* use an "if-like" function in order to do it.2012-08-13
  • 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