• разбиение пространства на адаптирующиеся ячейки (англ. adaptable cells),
• максимально возможный объём каждой ячейки,
• соответствие направления дерева пространственному разбиению.

• 1 Классификация
  • 1.1 Region quadtree
  • 1.2 Point quadtree
    • 1.2.1 Структура узла
  • 1.3 Edge quadtree
  • 1.4 Polygonal map quadtree
• 2 Варианты использования
• 3 Псевдокод
  • 3.1 Структуры данных
  • 3.2 Класс QuadTree
  • 3.3 Вставка
  • 3.4 Вхождение в диапазон
• 4 См. также
• 5 Ссылки
  • 5.1 Примечания
  • 5.2 Источники
• 6 Внешние ссылки

• 4 указателя: quad[‘NW’], quad[‘NE’], quad[‘SW’], и quad[‘SE’],
• точка, описываемая следующим образом:
  • ключ key, обычно выражает координаты x и y,
  • значение value, например, имя.

• Представление изображений.
  
• Пространственные базы данных.
• Эффективное обнаружение столкновений в двух измерениях.
• Отсечение невидимых частей ландшафта^[англ.] (англ. view frustum culling).
• Хранение данных для табличных или матричных вычислений.
• Вычисления, связанные с многомерными полями (в вычислительной гидродинамике, электромагнетизме).
• Симуляция игры Жизнь^[2].
• Вычисление состояний наблюдаемой динамической системы^[3].
• Анализ частей фрактальных изображений.

// Простая структура для представления точки или вектора
struct XY
{
  float x;
  float y;

  function __construct(float _x, float _y) {...}
}

// Ограничивающий параллелепипед, выровненный по координатным осям
// (axis-aligned bounding box, AABB), половинной размерности с центром
struct AABB
{
  XY center;
  XY halfDimension;

  function __construct(XY center, XY halfDimension) {...}
  function containsPoint(XY p) {...}
  function intersectsAABB(AABB other) {...}
}

class QuadTree
{
  // Константа — количество элементов, которые можно хранить в одном узле
  constant int QT_NODE_CAPACITY = 4;

  // Ограничивающий параллелепипед, выровненный по координатным осям,
  // показывает границы дерева
  AABB boundary;

  // Точки
  Array of XY [size = QT_NODE_CAPACITY] points;

  // Потомки
  QuadTree* northWest;
  QuadTree* northEast;
  QuadTree* southWest;
  QuadTree* southEast;

  // Методы
  function __construct(AABB _boundary) {...}
  function insert(XY p) {...}
  function subdivide() {...} // Создание 4 потомков, делящих квадрант на 4 равные части
  function queryRange(AABB range) {...}
}

class QuadTree {
 ...

  // Вставить точку
  function insert(XY p)
  {
    // Игнорировать объекты, не принадлежащие дереву
    if (!boundary.containsPoint(p))
      return false; // Объект не может быть добавлен

    // Если есть место, осуществить вставку 
    if (points.size < QT_NODE_CAPACITY)
    {
      points.append(p);
      return true;
    }

    // Далее необходимо разделить область и добавить точку в какой-либо узел
    if (northWest == null)
      subdivide();

    if (northWest->insert(p)) return true;
    if (northEast->insert(p)) return true;
    if (southWest->insert(p)) return true;
    if (southEast->insert(p)) return true;

    // По каким-то причинам вставка может не осуществиться (чего на самом деле не должно происходить)
    return false;
  }
}

class QuadTree
{
  ...

  // Найти точки, входящие в диапазон
  function queryRange(AABB range)
  {
    // Подготовить массив под результат
    Array of XY pointsInRange;

    // Отмена, если диапазон не совпадает с квадрантом
    if (!boundary.intersectsAABB(range))
      return pointsInRange; // Пустой список

    // Проверить объекты текущего уровня
    for (int p := 0; p < points.size; p++)
    {
      if (range.containsPoint(points[p]))
        pointsInRange.append(points[p]);
    }

    // Остановка, если больше нет потомков
    if (northWest == null)
      return pointsInRange;

    // Добавить все точки потомков
    pointsInRange.appendArray(northWest->queryRange(range));
    pointsInRange.appendArray(northEast->queryRange(range));
    pointsInRange.appendArray(southWest->queryRange(range));
    pointsInRange.appendArray(southEast->queryRange(range));

    return pointsInRange;
  }
}

• Двоичное разбиение пространства
• K-мерное дерево
• Октодерево
• R-дерево
• UB-дерево (англ. UB-tree)
• Пространственная база данных

1. Hanan Samet and Robert Webber. “Storing a Collection of Polygons Using Quadtrees”. ACM Transactions on Graphics July 1985: 182-222. InfoLAB. Web. 23 March 2012
2. Tomas G. Rokicki. An Algorithm for Compressing Space and Time  (неопр.) (1 апреля 2006). Дата обращения: 20 мая 2009. Архивировано 2 октября 2012 года.
3. Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation, Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, July, 2010.

1. Raphael Finkel and J.L. Bentley. Quad Trees: A Data Structure for Retrieval on Composite Keys (англ.) // Acta Informatica^[англ.] : journal. — 1974. — Vol. 4, no. 1. — P. 1—9. — doi:10.1007/BF00288933.
2. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry (неопр.). — 2nd revised. — Springer-Verlag, 2000. — ISBN 3-540-65620-0. Chapter 14: Quadtrees: pp. 291–306.
3. Webber, Robert; Samet, Hanan. [http://infolab.usc.edu/csci585/Spring2008/den_ar/p182-samet.pdf Storing a Collection of Polygons Using

• Java quad tree example and explanation
• A discussion of the Quadtree and an application
• Considerable discussion and demonstrations of Spatial Indexing
• Example C# code for a quad tree
• Javascript Implementation of the QuadTree used for collision detection
• C++ Implementation of a QuadTree used for spatial indexing of triangles
• Quadtree Search JavaScript implementation