7.1.5 Rectangle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

/*

Common axis-aligned rectangle calculations in two dimensions. The functions are templated on the
point type `Pt`, which should accept `Point`, `PointD`, or `PointI` from 7.1.1, or any struct with
numeric `.x` and `.y` fields.

- `point_in_rectangle(p, v, w, h, include_boundary = true)` returns whether `p` is inside the
  axis-aligned rectangle whose opposite corners are `v` and (`v.x + w`, `v.y + h`). Negative widths
  and heights are supported. The `include_boundary` flag controls whether boundary points count.
- `point_in_rectangle(p, a, b, include_boundary = true)` returns whether `p` is inside the
  axis-aligned rectangle with opposite corners `a` and `b`.
- `rectangle_intersection(a1, b1, a2, b2, &p, &q, include_boundary = true)` finds the intersection
  of two axis-aligned rectangles, where `a1`/`b1` and `a2`/`b2` are opposite-corner pairs. Returns
  $-1$ if the rectangles are disjoint, $0$ if they partially intersect, $1$ if the first rectangle
  is completely inside the second, and $2$ if the second rectangle is completely inside the first.
  If an intersection exists, its lower-left and upper-right corners are stored in `p` and `q` when
  those pointers are non-null. The `include_boundary` flag controls whether boundary-only contact
  counts as intersecting.

Floating-point inputs use EPS-based comparisons.

Overflow warning: For integer-coordinate inputs, comparisons are exact as long as intermediate
coordinate additions, subtractions, and min/max values do not overflow.

Time Complexity:
- O(1) per operation.

Space Complexity:
- O(1) auxiliary for all operations.

*/

#include <algorithm>
#include <cmath>
#include <type_traits>

const double EPS = 1e-9;

template<typename T, typename U, typename C = std::common_type_t<T, U>>
bool EQ(T a, U b) {
  if constexpr (std::is_floating_point_v<C>) return C(a) == C(b) || std::fabs(C(a) - C(b)) <= EPS;
  return C(a) == C(b);
}

template<typename T, typename U, typename C = std::common_type_t<T, U>>
bool LT(T a, U b) {
  if constexpr (std::is_floating_point_v<C>) return C(a) < C(b) - EPS;
  return C(a) < C(b);
}

// clang-format off
template<typename T, typename U> bool GT(T a, U b) { return LT(b, a); }
template<typename T, typename U> bool LE(T a, U b) { return !LT(b, a); }
template<typename T, typename U> bool GE(T a, U b) { return !LT(a, b); }
// clang-format on

template<typename Pt, typename T>
bool point_in_rectangle(
    const Pt &p, const Pt &v, const T &w, const T &h, bool include_boundary = true
) {
  if (w < 0) {
    return point_in_rectangle(p, Pt(v.x + w, v.y), -w, h, include_boundary);
  }
  if (h < 0) {
    return point_in_rectangle(p, Pt(v.x, v.y + h), w, -h, include_boundary);
  }
  return include_boundary ? (GE(p.x, v.x) && LE(p.x, v.x + w) && GE(p.y, v.y) && LE(p.y, v.y + h))
                          : (GT(p.x, v.x) && LT(p.x, v.x + w) && GT(p.y, v.y) && LT(p.y, v.y + h));
}

template<typename Pt>
bool point_in_rectangle(const Pt &p, const Pt &a, const Pt &b, bool include_boundary = true) {
  auto xl = std::min(a.x, b.x), yl = std::min(a.y, b.y);
  auto xh = std::max(a.x, b.x), yh = std::max(a.y, b.y);
  return point_in_rectangle(p, Pt(xl, yl), xh - xl, yh - yl, include_boundary);
}

template<typename Pt>
int rectangle_intersection(
    const Pt &a1, const Pt &b1, const Pt &a2, const Pt &b2, Pt *p = nullptr, Pt *q = nullptr,
    const bool include_boundary = true
) {
  // Normalize each rectangle to [xl, xh] x [yl, yh] with coordinate-wise min/max only.
  // (Using auto keeps the native coordinate type, so integer rectangles stay exact.)
  auto xl1 = std::min(a1.x, b1.x), xh1 = std::max(a1.x, b1.x);
  auto yl1 = std::min(a1.y, b1.y), yh1 = std::max(a1.y, b1.y);
  auto xl2 = std::min(a2.x, b2.x), xh2 = std::max(a2.x, b2.x);
  auto yl2 = std::min(a2.y, b2.y), yh2 = std::max(a2.y, b2.y);
  // The intersection is the overlap of the two coordinate intervals.
  auto ixl = std::max(xl1, xl2), ixh = std::min(xh1, xh2);
  auto iyl = std::max(yl1, yl2), iyh = std::min(yh1, yh2);
  bool disjoint =
      include_boundary ? (GT(ixl, ixh) || GT(iyl, iyh)) : (GE(ixl, ixh) || GE(iyl, iyh));
  if (disjoint) {
    return -1;  // Completely disjoint.
  }
  // Opposing corners of the overlap: bottom-left in p, top-right in q.
  if (p != nullptr) {
    *p = Pt(ixl, iyl);
  }
  if (q != nullptr) {
    *q = Pt(ixh, iyh);
  }
  // The overlap equals a rectangle exactly when that rectangle is contained in the other.
  if (EQ(ixl, xl1) && EQ(ixh, xh1) && EQ(iyl, yl1) && EQ(iyh, yh1)) {
    return 1;  // Rectangle 1 completely inside 2.
  }
  if (EQ(ixl, xl2) && EQ(ixh, xh2) && EQ(iyl, yl2) && EQ(iyh, yh2)) {
    return 2;  // Rectangle 2 completely inside 1.
  }
  return 0;  // Partial intersection.
}

/*** Example Usage ***/

#include <cassert>

struct Point {
  double x, y;
  Point(double x = 0, double y = 0) : x(x), y(y) {}
  bool operator==(const Point &p) const { return x == p.x && y == p.y; }
};

int main() {
  assert(point_in_rectangle(Point(0, -1), Point(0, -3), 3, 2));
  assert(!point_in_rectangle(Point(0, -1), Point(0, -3), 3, 2, false));
  assert(point_in_rectangle(Point(2, -2), Point(3, -3), -3, 2));
  assert(!point_in_rectangle(Point(0, 0), Point(3, -1), -3, -2));
  assert(point_in_rectangle(Point(2, -2), Point(3, -3), Point(0, -1)));
  assert(!point_in_rectangle(Point(0, -1), Point(3, -3), Point(0, -1), false));
  assert(!point_in_rectangle(Point(-1, -2), Point(3, -3), Point(0, -1)));

  Point p, q;
  // Output coordinates come directly from input coordinates via min/max, so exact equality is safe.
  assert(-1 == rectangle_intersection(Point(0, 0), Point(1, 1), Point(2, 2), Point(3, 3)));
  assert(0 == rectangle_intersection(Point(1, 1), Point(7, 7), Point(5, 5), Point(0, 0), &p, &q));
  assert(p == Point(1, 1) && q == Point(5, 5));
  assert(1 == rectangle_intersection(Point(1, 1), Point(0, 0), Point(0, 0), Point(1, 10), &p, &q));
  assert(p == Point(0, 0) && q == Point(1, 1));
  assert(2 == rectangle_intersection(Point(0, 5), Point(5, 7), Point(1, 6), Point(2, 5), &p, &q));
  assert(p == Point(1, 5) && q == Point(2, 6));
  assert(
      -1 ==
      rectangle_intersection(Point(0, 0), Point(1, 1), Point(1, 1), Point(2, 2), &p, &q, false)
  );
  return 0;
}