27

I have two 2D rectangles, defined as an origin (x,y) a size (height, width) and an angle of rotation (0-360°). I can guarantee that both rectangles are the same size.

I need to calculate the approximate area of intersection of these two rectangles. Rectangle intersection

The calculation does not need to be exact, although it can be. I will be comparing the result with other areas of intersection to determine the largest area of intersection in a set of rectangles, so it only needs to be accurate relative to other computations of the same algorithm.

I thought about using the area of the bounding box of the intersected region, but I'm having trouble getting the vertices of the intersected region because of all of the different possible cases: So many possible intersection shapes

I'm writing this program in Objective-C in the Cocoa framework, for what it's worth, so if anyone knows any shortcuts using NSBezierPath or something you're welcome to suggest that too.

Nate Thorn
  • 2,193
  • 2
  • 23
  • 27
  • I am not getting what you need exactly. But I think the maximum intersection area is always equals to area of one of the rectangles as both the rectangles are of same area. – Narendra Jul 26 '12 at 13:16
  • @rain, he doesn't want the maximum possible intersection area, but the actual intersection are of two given rectangles. – Shahbaz Jul 26 '12 at 13:17
  • Yes you are right. But in the question he has mentioned " I can guarantee that both rectangles are the same size." and " I will be comparing the result with other areas of intersection to determine the largest area of intersection in a set of rectangles". So I doubt what is required exactly. – Narendra Jul 26 '12 at 13:20
  • @Rain, Shahbaz is correct; I have a set of rectangles--of that set, I need to determine the greatest area of intersection between any two of them. The only reason I mention it is to give context for why I need to be able to find the area of intersection of two rectangles. – Nate Thorn Jul 26 '12 at 13:26
  • This is essentially a duplicate of http://stackoverflow.com/questions/8011267/area-of-rectangle-rectangle-intersection. – Codie CodeMonkey Jul 27 '12 at 07:14

6 Answers6

12

To supplement the other answers, your problem is an instance of line clipping, a topic heavily studied in computer graphics, and for which there are many algorithms available. If you rotate your coordinate system so that one rectangle has a horizontal edge, then the problem is exactly line clipping from there on.

You could start at the Wikipedia article on the topic, and investigate from there.

Joseph O'Rourke
  • 4,346
  • 16
  • 25
9

A simple algorithm that will give an approximate answer is sampling.

Divide one of your rectangles up into grids of small squares. For each intersection point, check if that point is inside the other rectangle. The number of points that lie inside the other rectangle will be a fairly good approximation to the area of the overlapping region. Increasing the density of points will increase the accuracy of the calculation, at the cost of performance.

Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
  • 1
    Because development time is at more of a premium than either efficiency or accuracy in my case, I selected this answer. However, see the other answers for more efficient/accurate solutions. – Nate Thorn Jul 26 '12 at 14:15
  • 1
    If you have a grid you can use the Pick's theorem http://en.wikipedia.org/wiki/Pick%27s_theorem – Ismael Dec 11 '13 at 17:19
4

In any case, computing the exact intersection polygon of two convex polygons is an easy task, since any convex polygon can be seen as an intersection of half-planes. "Sequential cutting" does the job.

Choose one rectangle (any) as the cutting rectangle. Iterate through the sides of the cutting rectangle, one by one. Cut the second rectangle by the line that contains the current side of the cutting rectangle and discard everything that lies in the "outer" half-plane.

Once you finish iterating through all cutting sides, what remains of the other rectangle is the result.

AnT stands with Russia
  • 312,472
  • 42
  • 525
  • 765
3

You can actually compute the exact area.

  1. Make one polygon out of the two rectangles. See this question (especially this answer), or use the gpc library.
  2. Find the area of this polygon. See here.

  3. The shared area is

    area of rectangle 1 + area of rectangle 2 - area of aggregated polygon
Community
  • 1
  • 1
Shahbaz
  • 46,337
  • 19
  • 116
  • 182
  • The link you provided doesn't seem to fully explain how to implement step 1? The question has no accepted answer. – Mark Byers Jul 26 '12 at 13:49
  • @MarkByers, yes, but the OP of that question has 30% unaccepted answers. There are many solutions there, surely one of them would work. I'll search more though. – Shahbaz Jul 26 '12 at 13:51
  • I'm glad I'm not the only one; I thought I understood but now that I'm trying to implement it I'm stuck on trying to form the union of the two rectangles; Assuming I can find the points of intersection, what order do the points go in? – Nate Thorn Jul 26 '12 at 13:53
  • @NateThorn, I updated my answer introducing a library that does this. You can also search for this specific sub-problem more on the internet. – Shahbaz Jul 26 '12 at 13:55
  • If you're going to use the gpc library, there's no need for these three steps. It can directly calculate the intersection. "Difference, **intersection**, exclusive-or and union clip operations are supported." – Mark Byers Jul 26 '12 at 13:57
  • I don't want to have to pay to use the gpc library commercially; this is really a side feature in my program and isn't worth the hassle of paying for an entire library. – Nate Thorn Jul 26 '12 at 13:58
  • @NateThorn, make sure you look at the answer I linked. The idea is to find the intersection points, diving the edges and making each rectangle into a more complex polygon. Then, you can simply remove the edges that are totally inside the other rectangle and make a union of the edges. – Shahbaz Jul 26 '12 at 14:00
  • @NateThorn, also gpc is free if your program is not commercial. – Shahbaz Jul 26 '12 at 14:00
1

Take each line segment of each rectangle and see if they intersect. There will be several possibilities:

  1. If none intersect - shared area is zero - unless all points of one are inside the other. In that case the shared area is the area of the smaller one.

  2. a If two consecutive edges of one rectactangle intersect with a single edge of another rectangle, this forms a triangle. Compute its area.

    b. If the edges are not consequtive, this forms a quadrilateral. Compute a line from two opposite corners of the quadrilateral, this makes two triangles. Compute the area of each and sum.

  3. If two edges of one intersect with two edges of another, then you will have a quadrilateral. Compute as in 2b.

  4. If each edge of one intersects with each edge of the other, you will have an octagon. Break it up into triangles ( e.g. draw a ray from one vertex to each other vertex to make 4 triangles )

@edit: I have a more general solution.

Check the special case in 1.

Then start with any intersecting vertex, and follow the edges from there to any other intersection point until you are back to the first intersecting vertex. This forms a convex polygon. draw a ray from the first vertex to each opposite vetex ( e.g. skip the vertex to the left and right. ) This will divide it into a bunch of triangles. compute the area for each and sum.

Rafael Baptista
  • 11,181
  • 5
  • 39
  • 59
1

A brute-force-ish way:

  • take all points from the set of [corners of rectangles] + [points of intersection of edges]
  • remove the points that are not inside or on the edge of both rectangles.
  • Now You have corners of intersection. Note that the intersection is convex.
  • sort the remaining points by angle between arbitrary point from the set, arbitrary other point, and the given point.
  • Now You have the points of intersection in order.
  • calculate area the usual way (by cross product)

.

maniek
  • 7,087
  • 2
  • 20
  • 43