3.3.7. QuadTree

3.3.7.1. Image compression With QuadTree

Quadtree is a tree data structure in which each internal node either is a leaf node or has exactly 4 children. Quadtrees are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. One of the common use cases of quadtree is image compression.

If all the 4 leaf nodes have the same value, we can use one leaf node to represent all of them. for example:

Input Image:                          Quadtree representation:
+---------+--------+                   +---------+--------+
|  2 |  2 |  3 | 3 |                   |         |        |
+----|----|----|---|                   |    2    |    3   |
|  2 |  2 |  3 | 3 |                   |         |        |
+----+----|--------|      ====>        +----+----|--------|
|  4 |  2 |  5 | 5 |                   | 4  | 2  |        |
+----|----|----|---|                   +----|----|    5   |
|  2 |  3 |  5 | 5 |                   | 2  | 3  |        |
+----+----+--------+                   +----+----+--------+

Design the quadtree data structure and write a function that builds a quadtree for an input image, where image will be given as a two-d array of integers.

We can split the matrix recursively to 4 sub-matrices a, b, c and d as the following:

+-----------------------------> (Y Axis)
|     y1       ym        y2
|  x1 +---------+--------+
|     |         |        |
|     +-   a   -|-   b  -|
|     |         |        |
|  xm +----+----|--------|
|     |         |        |
|     +-   c   -|-   d  -|
|     |         |        |
|  x2 +----+----+--------+
|
v (X Axis)

Please be noted that the x1, y1, x2, y2 are inclusive indices.

 1#include <gtest/gtest.h>
 2using namespace std;
 3
 4namespace ns_quadtree_image_compression {
 5  struct quadtree {
 6    int val; // leaf node has value
 7    quadtree *cn[4] = {}; // children number is 4, so it is called quad
 8    quadtree(int v) : val(v) {} // construct a leaf node
 9    quadtree(quadtree *a, quadtree *b, quadtree *c, quadtree *d) { // construct an inner node
10      cn[0] = a, cn[1] = b, cn[2] = c, cn[3] = d;
11    }
12    bool is_leaf() {return all_of(cn, cn + 3, [](quadtree *x) { return x == nullptr; });}
13  };
14
15  bool valid_index(vector<vector<int>> &m, int x1, int x2, int y1, int y2) {
16    return x1 <= x2 and y1 <= y2 and x2 < m.size() and y2 < m[0].size();
17  }
18
19  quadtree* dfs(vector<vector<int>> &m, int x1, int x2, int y1, int y2) {
20    if (x1 == x2 and y1 == y2) { return new quadtree(m[x1][y1]); }
21    quadtree *a = nullptr, *b = nullptr, *c = nullptr, *d = nullptr;
22    int xm = x1 + (x2 - x1) / 2, ym = y1 + (y2 - y1) / 2;
23    if (valid_index(m, x1, xm, y1, ym)) a = dfs(m, x1, xm, y1, ym);
24    if (valid_index(m, x1, xm, ym + 1, y2)) b = dfs(m, x1, xm, ym + 1, y2);
25    if (valid_index(m, xm + 1, x2, y1, ym)) c = dfs(m, xm + 1, x2, y1, ym);
26    if (valid_index(m, xm + 1, x2, ym + 1, y2)) d = dfs(m, xm + 1, x2, ym + 1, y2);
27    if (a == nullptr or b == nullptr or c == nullptr or d == nullptr)
28      return new quadtree(a, b, c, d);
29    if (a->val == b->val and b->val == c->val and c->val == d->val) // merge the same value leaf nodes
30      return new quadtree(a->val);
31    return new quadtree(a, b, c, d); // not merge
32  }
33
34  quadtree *make_quadtree(vector<vector<int>> &m) {
35    if (m.empty() or m[0].empty()) return nullptr;
36    int R = m.size(), C = m[0].size();
37    return dfs(m, 0, R - 1, 0, C - 1);
38  }
39} // namespace ns_quadtree_image_compression
40using namespace ns_quadtree_image_compression;
41TEST(quadtree, a) {
42  vector<vector<int>> m = {{2, 2, 3, 3}, {2, 2, 3, 3}, {4, 2, 5, 5}, {2, 3, 5, 5}};
43  quadtree *q = make_quadtree(m);
44  EXPECT_EQ(q->cn[0]->val, 2);
45  EXPECT_TRUE(q->cn[0]->is_leaf());
46  EXPECT_FALSE(q->is_leaf());
47  m = {{2, 2, 3, 3, 3}, {2, 2, 3, 3, 3}, {4, 2, 5, 5, 5}, {2, 3, 5, 5, 5}};
48  quadtree *q2 = make_quadtree(m);
49  EXPECT_EQ(q2->cn[0]->val, 2);
50  EXPECT_TRUE(q2->cn[0]->is_leaf());
51  EXPECT_FALSE(q2->is_leaf());
52}

  • Why is this question good?

Quadtree is a relatively new concept to most candidates. This can test candidate’s ability to handle a new concept. Also this is a decent recursion problem. If candidate can understand this very well and sort out the recursion steps and termination condition, this problem can be solved with very simple and elegant code. Otherwise, the code could be very messy. So, ability to handle new concept and clean coding would be two main things to test from this question.

👽 Possible follow up: Speed up the construction algorithm: build sub-trees concurrently

3.3.7.2. K Nearest Neighbours

The self-driving car needs refueling or maintenance. Please find and return to the gas station within K distance near the car.

y
^
|    (tl)
|     +-----------
|     |          |
|     |          |
|     -----------+
|                (br)
+-------------------> x  (coordinates of 1st quadrant)
../_images/knn.png

Figure 3.3.4 K Nearest Neighbors

  1#include <gtest/gtest.h>
  2#include <bits/stdc++.h>
  3
  4using namespace std;
  5namespace ns_spatial_indices{
  6struct Point {
  7  double x, y;
  8  Point(double _x=0, double _y=0) : x(_x), y(_y) {}
  9  bool operator==(const Point& p) {return x==p.x and y==p.y;}
 10};
 11
 12struct BB {  // bounding box or RECT
 13  Point tl, br; // top-left and bottom-right
 14  BB(Point x={}, Point y={}) { tl = x, br = y; }
 15  int width() { return br.x - tl.x; }
 16  int height() { return br.y - tl.y; }
 17  Point centroid() { return Point{(br.x - tl.x) / 2.0, (br.y - tl.y) / 2.0}; }
 18  bool overlapped(const BB &o) {
 19    return !(o.tl.x > br.x or o.br.x < tl.x or o.tl.y > br.y or o.br.y < tl.y);
 20  }
 21  bool contain(const Point &p) const {
 22    return tl.x <= p.x and p.x <= br.x and tl.y <= p.y and p.y <= br.y;
 23  }
 24};
 25
 26struct Node {  // quadtree node contains point + data
 27  Point pt;
 28  int data;
 29  Node(Point _pt, int _data) : pt(_pt), data(_data) {}
 30  Node(double x, double y, int _data) : pt(x, y), data(_data) {}
 31  Node() : data(0) {}
 32};
 33
 34struct comp {
 35  bool operator()(pair<int, Node*> a, pair<int, Node*> b) { return a.first > b.first; }
 36};
 37
 38using PriorityQueueT = priority_queue<pair<int, Node*>, vector<pair<int, Node*>>, comp>;
 39
 40int distance_square(const Point &a, const Point &b) {
 41  int x = a.x - b.x, y = a.y - b.y;
 42  return x * x + y * y;
 43}
 44
 45class quadtree {  // The main quadtree class
 46  BB bb;   // bounding box
 47
 48  vector<Node*> nodes;  // all nodes located in bb/quadtree
 49  array<quadtree*, 4> children;  // Children of this tree - *tl, *tr, *bl, *br
 50  const int MIN_BB_LEN = 4;
 51
 52  Node* nn_dfs(const Point &p, int &mx2);
 53  void knn_dfs(const Point &p, int &mx2, PriorityQueueT &);
 54  void neighbors_in_circle_dfs(const Point &p, int distance, vector<Node*> &);
 55  void neighbors_in_rect_dfs(const BB &o, vector<Node*>&);
 56
 57public:
 58  quadtree(Point topL, Point botR);
 59  quadtree(const BB &b);
 60  void insert(Node*);
 61  // point query
 62  Node*point_query(Point);  // search point to get Node(and data)
 63  // range_query
 64  vector<Node*> neighbors_in_rect(const BB &);
 65  vector<Node*> neighbors_in_circle(const Point &p, int distance);  // neighbors in k miles
 66  Node*nn(const Point &);                    // nearest neighbor
 67  vector<Node*> knn(const Point &p, int k);  // k nearest neighbor
 68  bool inBB(Point);                           // inside bounding box
 69};
 70
 71quadtree::quadtree(Point topL, Point botR) { // constructor 1
 72  bb = {topL, botR};
 73  fill(children.begin(), children.end(), nullptr);
 74}
 75
 76quadtree::quadtree(const BB &b) { // constructor 2
 77  bb = b;
 78  fill(children.begin(), children.end(), nullptr);
 79}
 80
 81// Check if current quadtree contains the point
 82bool quadtree::inBB(Point p) {  // depends on the direction of coordinate system
 83  return (p.x >= bb.tl.x and p.x <= bb.br.x and p.y >= bb.tl.y and p.y <= bb.br.y);
 84}
 85
 86// Insert a node into the quadtree
 87void quadtree::insert(Node*node) {
 88  if (node == NULL or !inBB(node->pt))  // Current quad cannot contain it
 89    return;
 90  // We are at a quad of unit area, We cannot subdivide this quad further
 91  if (bb.width() <= MIN_BB_LEN and bb.height() <= MIN_BB_LEN) {
 92    nodes.push_back(node);
 93    return;
 94  }
 95
 96  if (bb.centroid().x >= node->pt.x) {
 97    if (bb.centroid().y >= node->pt.y) { // Indicates tl
 98      if (children[0] == NULL)
 99        children[0] = new quadtree(BB{bb.tl, {bb.centroid().x, bb.centroid().y}});
100      children[0]->insert(node);
101    } else {  // Indicates bl
102      if (children[1] == NULL)
103        children[1] = new quadtree(Point(bb.tl.x, (bb.tl.y + bb.br.y) / 2),
104                                   Point((bb.tl.x + bb.br.x) / 2, bb.br.y));
105      children[1]->insert(node);
106    }
107  } else {  // Indicates tr
108    if ((bb.tl.y + bb.br.y) / 2 >= node->pt.y) {
109      if (children[2] == NULL)
110        children[2] = new quadtree(Point((bb.tl.x + bb.br.x) / 2, bb.tl.y),
111                                   Point(bb.br.x, (bb.tl.y + bb.br.y) / 2));
112      children[2]->insert(node);
113    } else {  // Indicates br
114      if (children[3] == NULL)
115        children[3] = new quadtree(Point((bb.tl.x + bb.br.x) / 2, (bb.tl.y + bb.br.y) / 2),
116                                   Point(bb.br.x, bb.br.y));
117      children[3]->insert(node);
118    }
119  }
120}
121
122// Find a node in a quadtree
123Node*quadtree::point_query(Point p) {
124  // Current quad cannot contain it
125  if (!inBB(p)) return NULL;
126  // We are at a quad of unit length, We cannot subdivide this quad further
127  if (!nodes.empty()) {  // ONLY leaf nodes have data information
128    for (Node*nd : nodes) {
129      if (nd->pt.x == p.x and nd->pt.y == p.y) return nd;
130    }
131    return NULL;
132  }
133  if ((bb.tl.x + bb.br.x) / 2 >= p.x) {
134    if ((bb.tl.y + bb.br.y) / 2 >= p.y) {  // Indicates tl
135      return children[0] ? children[0]->point_query(p) : NULL;
136    } else {  // Indicates bl
137      return children[1] ? children[1]->point_query(p) : NULL;
138    }
139  } else {
140    if ((bb.tl.y + bb.br.y) / 2 >= p.y) {  // Indicates tr
141      return children[2] ? children[2]->point_query(p) : NULL;
142    } else {  // Indicates br
143      return children[3] ? children[3]->point_query(p) : NULL;
144    }
145  }
146}
147
148vector<Node*> quadtree::neighbors_in_rect(const BB &o) {
149  vector<Node*> v;
150  neighbors_in_rect_dfs(o, v);
151  return v;
152}
153
154void quadtree::neighbors_in_rect_dfs(const BB &o, vector<Node*> &res) {
155  if (bb.overlapped(o)) {
156    if (!nodes.empty()) {
157      for (Node*n : nodes) {
158        if (o.contain(n->pt)) {
159          res.push_back(n);
160        }
161      }
162    } else {
163      for (int i = 0; i < 4; i++) {
164        if (children[i] == nullptr) continue;
165        children[i]->neighbors_in_rect_dfs(o, res);
166      }
167    }
168  }
169}
170
171vector<Node*> quadtree::neighbors_in_circle(const Point &p, int distance) {
172  vector<Node*> res;
173  neighbors_in_circle_dfs(p, distance * distance, res);
174  return res;
175}
176
177void quadtree::neighbors_in_circle_dfs(const Point &p, int dd, vector<Node*> &res) {
178  if (!inBB(p)) {  //////
179    // compare with (point ~ BB) distance; ~ To be improved!
180    int dis_square_to_BB = min(min((bb.tl.x - p.x) * (bb.tl.x - p.x),
181                                   (bb.br.x - p.x) * (bb.br.x - p.x)),
182                               min((bb.tl.y - p.y) * (bb.tl.y - p.y),
183                                   (bb.br.y - p.y) * (bb.br.y - p.y)));
184    if (dd < dis_square_to_BB) return;
185  }
186  if (!nodes.empty()) {  // quadtree leaf node
187    for (Node*n : nodes) {
188      int d = distance_square(p, n->pt);
189      if (d <= dd) res.emplace_back(n);
190    }
191  } else {  // other qts
192    for (int i = 0; i < 4; i++) {
193      if (children[i] == nullptr) continue;
194      children[i]->neighbors_in_circle_dfs(p, dd, res);
195    }
196  }
197};
198
199Node*quadtree::nn(const Point &p) {
200  if (!inBB(p)) return NULL;
201  int distance = INT_MAX;
202  return nn_dfs(p, distance);
203}
204
205Node*quadtree::nn_dfs(const Point &p, int &mx2) {
206  if (!inBB(p)) {  //////
207    // compare with (point - BB) distance; ~ To be improved!
208    int dis_square_to_BB = min(min((bb.tl.x - p.x) * (bb.tl.x - p.x),
209                                   (bb.br.x - p.x) * (bb.br.x - p.x)),
210                               min((bb.tl.y - p.y) * (bb.tl.y - p.y),
211                                   (bb.br.y - p.y) * (bb.br.y - p.y)));
212    if (mx2 < dis_square_to_BB) return NULL;
213  }
214  Node*res = NULL;
215  if (!nodes.empty()) {  // leaf qt node
216    for (Node*n : nodes) {
217      int d = distance_square(p, n->pt);
218      if (d < mx2) mx2 = d, res = n;
219    }
220  } else {  // other qts
221    for (int i = 0; i < 4; i++) {
222      if (children[i] == nullptr) continue;
223      auto tmp = children[i]->nn_dfs(p, mx2);
224      if (tmp) {
225        res = tmp;
226      }
227    }
228  }
229  return res;
230}
231
232vector<Node*> quadtree::knn(const Point &p, int k) {
233  if (k <= 0) return {};
234  vector<Node*> res;
235  priority_queue<pair<int, Node*>, vector<pair<int, Node*>>, comp> q;
236  int distance = INT_MAX;
237  knn_dfs(p, distance, q);
238  while (k-- and !q.empty()) {
239    res.push_back(q.top().second), q.pop();
240  }
241  return res;
242}
243
244void quadtree::knn_dfs(const Point &p, int &mx2, PriorityQueueT &q) {
245  if (!inBB(p)) {  //////
246    // compare with (point - BB) distance; ~ To be improved!
247    int dis_square_to_BB = min(min((bb.tl.x - p.x) * (bb.tl.x - p.x),
248                                   (bb.br.x - p.x) * (bb.br.x - p.x)),
249                               min((bb.tl.y - p.y) * (bb.tl.y - p.y),
250                                   (bb.br.y - p.y) * (bb.br.y - p.y)));
251    if (mx2 < dis_square_to_BB) return;
252  }
253  if (!nodes.empty()) {  // leaf qt node
254    for (Node*n : nodes) {
255      int d = distance_square(p, n->pt);
256      q.emplace(d, n);
257    }
258  } else {  // other qts
259    for (int i = 0; i < 4; i++) {
260      if (children[i] == nullptr) continue;
261      children[i]->knn_dfs(p, mx2, q);
262    }
263  }
264}
265}
266
267using namespace ns_spatial_indices;
268
269TEST(all_points_in_Kmiles, a) {
270  quadtree qt(Point(0, 0), Point(8, 8));
271  vector<Node> vn = {{1., 1., 1},
272                     {2.,  5.,  2},
273                     {7.,  6.,  3},
274                     {3.,  0.,  0},
275                     {7.,  7.,  7}};
276  for (auto &n: vn) qt.insert(&n);
277  auto ns = qt.neighbors_in_rect({Point(0, 0), Point(8, 8)});
278  EXPECT_EQ(ns.size(), 5);
279  ns = qt.neighbors_in_rect({Point(0, 0), Point(1, 1)});
280  EXPECT_EQ(ns.size(), 1);
281  auto r = qt.knn(Point(3, 3), 2);
282  EXPECT_EQ(r[0]->data, 2);
283  EXPECT_EQ(r[1]->data, 1);
284  EXPECT_TRUE(qt.point_query(Point(1, 1))->data == 1);
285  EXPECT_TRUE(qt.point_query(Point(2, 5))->data == 2);
286  EXPECT_TRUE(qt.point_query(Point(7, 6))->data == 3);
287  EXPECT_TRUE(nullptr == qt.point_query(Point(5, 5)));
288  EXPECT_TRUE(qt.nn(Point(3, 3))->pt == Point(2, 5));
289  EXPECT_TRUE(qt.nn(Point(2, 3))->pt == Point(2, 5));
290  EXPECT_TRUE(qt.nn(Point(2, 4))->pt == Point(2, 5));
291  EXPECT_TRUE(qt.nn(Point(2, 1))->pt == Point(1, 1));
292  auto nns = qt.neighbors_in_circle(Point(3, 3), 5);
293  EXPECT_EQ(nns.size(), 4);
294}