QuadTree
================

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:

.. code-block:: text

    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:

.. code-block:: text

   +-----------------------------> (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.

.. literalinclude:: code/quadtree_image_compression_test.cpp
  :language: c++
  :linenos:

.. only:: html

    - 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.

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

    - https://en.wikipedia.org/wiki/Quadtree


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.

.. code-block:: text

   y
   ^
   |    (tl)
   |     +-----------
   |     |          |
   |     |          |
   |     -----------+
   |                (br)
   +-------------------> x  (coordinates of 1st quadrant)

.. figure:: code/knn.png
  :name: KNN
  :align: center

  K Nearest Neighbors

.. literalinclude:: code/all_points_in_Kmiles_test.cpp
  :language: c++
  :linenos:

.. only:: html

  - http://ericandrewlewis.github.io/how-a-quadtree-works/
  - http://bl.ocks.org/llb4ll/8709363
  - https://blog.insightdatascience.com/planting-quadtrees-for-apache-flink-b396ebc80d35
  - http://danielblazevski.github.io/assets/player/KeynoteDHTMLPlayer.html#12
  - https://developer.apple.com/documentation/gameplaykit/gkquadtree
  - https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=434773&highlight=cruise