Area of rectangle-rectangle intersection

by

Since you stated that the rectangles may not be aligned, possible answers may be nothing, a point, a line segment, or a polygon with 3-8 sides.

The usual way to do this 2d boolean operation is to choose a counterclockwise ordering of the edges, and then evaluate edge segments between critical points (intersections or corners). At each intersection you switch between an edge segment of the first rectangle to an edge of the second, or visa-versa. You always pick the segment to the left of the previous segment.

enter image description here

There are LOTS of details, but the basic algorithm is to find all intersections and order them on their edges with an appropriate data structure. Choose an intersection (if there is one) and choose a line segment leading away from that intersection. Find the segment of the other rectangle to the left of the chosen starting segment. In the picture, we choose the green segment on intersection a (in the direction indicated by the arrow) as the reference segment. The segment of the other rectangle that is to the right, is the segment from a to b. Use that as the next reference segment, and choose a green segment to the left of it. That’s the segment from b to c. Find segment cd the same way. The next segment is from d to the corner, so the corner is in the vertex list for the intersection as well. From the corn we get back to a.

To choose the left side each time, you use the determinate of the coordinates of the direction vectors for the edges that meet. If the determinant for the ordered pair of directed edges is positive, you’re going the right way.

Now that you have the vertices of the intersection polygon, you can use the surveyor’s formula to get the area.

Some of the details that I’m leaving to you are:

  • What if a corner is coincident to to an edge or vertex of the other triangle?

  • What if there are no intersections? (one rectangle is inside the other, or they are disjoint–you can use point-in-polygon checks to figure this out. See the Wikipedia article on polygons.

  • What if the intersection is a single point or a segment?

More Related Contents:

  1. how can i increase the speed of my C++ calculation [closed]
  2. Why does my code work? Simple arithmetics
  3. Integer division always zero [duplicate]
  4. C/C++: Pointer Arithmetic
  5. Can’t make value propagate through carry
  6. How does photoshop blend two images together? [closed]
  7. Creating all possible k combinations of n items in C++
  8. Finding all the subsets of a set
  9. Direct way of computing clockwise angle between 2 vectors
  10. Calculating normals in a triangle mesh
  11. How to convert Euler angles to directional vector?
  12. Why isn’t `int pow(int base, int exponent)` in the standard C++ libraries?
  13. Uses of a C++ Arithmetic Promotion Header
  14. Math to convert seconds since 1970 into date and vice versa
  15. Does casting to an int after std::floor guarantee the right result?
  16. Rotate and translate object in local and global orientation using glm
  17. Compute objects moving with arrows and mouse
  18. Fastest implementation of sine, cosine and square root in C++ (doesn’t need to be much accurate)
  19. Random number generator that produces a power-law distribution?
  20. Fastest algorithm for primality test [closed]
  21. Special simple random number generator
  22. How computer does floating point arithmetic?
  23. Confusion between C++ and OpenGL matrix order (row-major vs column-major)
  24. Efficiently getting all divisors of a given number
  25. What is half open range and off the end value
  26. Convert string to mathematical evaluation [closed]
  27. Inverting a 4×4 matrix
  28. Best library for statistics in C++? [closed]
  29. Fast divisibility tests (by 2,3,4,5,.., 16)?
  30. How can I safely average two unsigned ints in C++?

Leave a Comment