Quadtree visualization in JavaScript

Today's post will be about Quadtrees. I have coded a little visualization, which may help you understand this data structure.

Hot to use it

Click on the first or second bitmap (A or B) to edit it. Quadtrees of bitmaps are drawn on the right side. Then you can rebuild the last bitmap (C) depending on A and B by clicking the right button.

What is Quadtree

Quadtree is a data strucutre, which is used to representa bitmap as a tree. Conversion from a bitmap to the tree can be described as follows:

  • a tree for a constatn-colored bitmap is a leaf of this color
  • otherwise it is an inner node, it's for children are trees for it's for quadrants

Nice features

Array representation

A very nice feature is, that quadtree can be represented in an array with values T, 0, 1. T means inner node, 0 and 1 are colors of leaves, T has 4 child values right after it (for example, T000T000T0001 is a quadtree 8x8 with black bottom-right bit).

Comprimation

In some cases, quadtree is much smaller than a bitmap (it can be used for comprimation, bitmap can be any binary data). When 2 trees are small, some logic operations on them can be performed faster than on bitmaps.

Collision detection

Sometimes we have an objects inside a 2D plane and we have to check, wich of them are colliding (overlaying) each other. Basically, we should check collision between every 2 objects ($O(n^2)$). We can also put these objects into quadtree, we can recrsively subdivide quadrants, so each object will be in it's own leaf with no other objects in it. Then we can check the collision of each object only with objects in it's neighboring quadrants, depending on it's size ($O(n*log(n))$).

The code

A qadtree node has a method for copying the tree, QNode.Copy(bool p). When "p" is true, it inverts it's colors ("negation").

Logic operations on trees

function GetLogic(a, b, op)  // tree a, tree b, operation, returns tree
{
   if(a.leaf)
   {
      if(op=="and") return (a.black ? b.Copy(false) : a.Copy(false));
      if(op=="or" ) return (a.black ? a.Copy(false) : b.Copy(false));
      if(op=="xor") return (a.black ? b.Copy(true ) : b.Copy(false));
      if(op=="min") return (a.black ? b.Copy(true ) : a.Copy(false));
   }
   else if(b.leaf)
   {
      if(op=="and") return (b.black ? a.Copy(false) : b.Copy(false));
      if(op=="or" ) return (b.black ? b.Copy(false) : a.Copy(false));
      if(op=="xor") return (b.black ? a.Copy(true ) : a.Copy(false));
      if(op=="min") return (b.black ? b.Copy(true ) : a.Copy(false));
   }
   else
   {
      var t = new QNode();
      t.c1 = GetLogic(a.c1, b.c1, op);
      t.c2 = GetLogic(a.c2, b.c2, op);
      t.c3 = GetLogic(a.c3, b.c3, op);
      t.c4 = GetLogic(a.c4, b.c4, op);
      return t;
   }
}

Old comments (closed because of spam)

One Comment

  1. torquent said:

    oGffUDFug6r

    February 20th, 2025