Rectangular Geometry
Rectangular geometry deals with rectangles whose sides are parallel to the coordinate axes. This section covers the basic operations used with these axis-aligned rectangles.
We assume that the positive \(X\)-axis points to the right and the positive \(Y\)-axis points upward.
Representing Points and Rectangles
A point contains a pair of coordinates: an \(x\)-coordinate and a \(y\)-coordinate. We can keep them together in a structure:
struct Point {
int x;
int y;
};An axis-aligned rectangle can be represented by its bottom-left and top-right points. We group those two points in another structure:
struct Rectangle {
Point bottom_left;
Point top_right;
};Throughout this section, we assume that every rectangle is normalized:
bottom_left.x <= top_right.xbottom_left.y <= top_right.y
Common Rectangle Operations
Width, Height, and Area
The width is the horizontal distance between the two sides:
width = r.top_right.x - r.bottom_left.x
The height is the vertical distance between the two sides:
height = r.top_right.y - r.bottom_left.y
The area is the product of the width and height:
area = width * height
int area(Rectangle r) {
int width = r.top_right.x - r.bottom_left.x;
int height = r.top_right.y - r.bottom_left.y;
return width * height;
}Checking for Intersection
Two rectangles intersect with positive area only when their ranges overlap on both the \(X\)-axis and the \(Y\)-axis. It is easier to check the opposite condition.
The rectangles are separated horizontally when either rectangle ends at or before the other one begins. They are separated vertically under the corresponding condition on the \(Y\)-axis. If either separation occurs, the rectangles do not intersect.
bool rectangles_intersect(Rectangle a, Rectangle b) {
bool separated_x = a.top_right.x <= b.bottom_left.x ||
b.top_right.x <= a.bottom_left.x;
bool separated_y = a.top_right.y <= b.bottom_left.y ||
b.top_right.y <= a.bottom_left.y;
return !separated_x && !separated_y;
}If two rectangles only touch at an edge or a corner, their common area is zero, so we do not count them as intersecting.
Finding the Intersection
If rectangles a and b intersect, their intersection is another rectangle. Its bottom-left point uses the larger lower coordinate on each axis, while its top-right point uses the smaller upper coordinate.
#include <algorithm>
using namespace std;
Rectangle rectangle_intersection(Rectangle a, Rectangle b) {
Rectangle c;
c.bottom_left.x = max(a.bottom_left.x, b.bottom_left.x);
c.bottom_left.y = max(a.bottom_left.y, b.bottom_left.y);
c.top_right.x = min(a.top_right.x, b.top_right.x);
c.top_right.y = min(a.top_right.y, b.top_right.y);
return c;
}Call rectangle_intersection only after rectangles_intersect confirms that the rectangles overlap.
One-Dimensional Geometry
The same ideas apply in one dimension, where we work with intervals instead of rectangles. An interval contains a left endpoint and a right endpoint:
struct Interval {
int left;
int right;
};We assume that every interval is normalized, so left <= right.
Length
The length of an interval is:
length = segment.right - segment.left
int length(Interval segment) {
return segment.right - segment.left;
}Checking for Intersection
Two intervals intersect with positive length unless one ends at or before the other begins:
bool intervals_intersect(Interval a, Interval b) {
return a.right > b.left && b.right > a.left;
}As with rectangles, intervals that only share an endpoint have zero overlap and are not considered intersecting.
Finding the Intersection
If intervals a and b intersect, their intersection begins at the larger left endpoint and ends at the smaller right endpoint:
#include <algorithm>
using namespace std;
Interval interval_intersection(Interval a, Interval b) {
Interval c;
c.left = max(a.left, b.left);
c.right = min(a.right, b.right);
return c;
}Example Problem
Fence Painting
We are given two intervals and must print the total length covered by them.
Solution
Add the lengths of both intervals, then subtract the length covered by both. If the intervals do not overlap, the common length is zero.
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
struct Interval {
int left;
int right;
};
int length(Interval segment) {
return segment.right - segment.left;
}
int overlap_length(Interval a, Interval b) {
int left = max(a.left, b.left);
int right = min(a.right, b.right);
return max(0, right - left);
}
int main() {
freopen("paint.in", "r", stdin);
freopen("paint.out", "w", stdout);
Interval a, b;
cin >> a.left >> a.right >> b.left >> b.right;
int total = length(a) + length(b) - overlap_length(a, b);
cout << total << "\n";
}