Get the points of intersection from 2 rectangles

c++ algorithm geometry scheme rectangles
NoSense picture NoSense · Nov 3, 2013 · Viewed 30.1k times · Source

Let say that we have two rectangles, defined with their bottom-left and top-right corners. For example: rect1 (x1, y1)(x2, y2) and rect2 (x3, y3)(x4, y4). I'm trying to find the coordinates(bottom-left and top-right) of the intersected rectangle.

Any ideas, algorithm, pseudo code, would be greatly appreciated.

p.s. I found similar questions but they check only if 2 rectangle intersect.

Answer

AnT picture AnT · Nov 3, 2013

If the input rectangles are normalized, i.e. you already know that x1 < x2, y1 < y2 (and the same for the second rectangle), then all you need to do is calculate

int x5 = max(x1, x3);
int y5 = max(y1, y3);
int x6 = min(x2, x4);
int y6 = min(y2, y4);

and it will give you your intersection as rectangle (x5, y5)-(x6, y6). If the original rectangles do not intersect, the result will be a "degenerate" rectangle (with x5 >= x6 and/or y5 >= y6), which you can easily check for.

P.S. As usual, small details will depend on whether you have to consider touching rectangles as intersecting.

Related questions

Determine if two rectangles overlap each other?

I am trying to write a C++ program that takes the following inputs from the user to construct rectangles (between 2 and 5): height, width, x-pos, y-pos. All of these rectangles will exist parallel to the x and the y axis, that …

Read More
Algorithm for a geodesic sphere

I have to make a sphere out of smaller uniformely distributed balls. I think the optimal way is to build a triangle-based geodesic sphere and use the vertices as the middle points of my balls. But I fail to write …

Read More
Rasterizing a 2D polygon

I need to create a binary bitmap from a closed 2D polygon represented as a list of points. Could you please point me to efficient and sufficiently simple algorithms to do that, or, even better, some C++ code? Thanks a …

Read More