Quadrant Map

Introduction

If you've ever had the desire for an infinite 2D array, but realize that the implementation of such is impossible with a fixed 2D array, this is the solution solution. The implementation here is done in C# using generics (or templates).

What is meant by Quadrant Map is that you are able to represent the full 4 Quadrants of the typical euclidean coordinate system, instead of being restricted to just positive integers. This means that you can have negative x and y indices as you might expect with a full Field of data.

The method by which this is implemented also allows for sparse input and data retrieval. If no data value has been set, its value is the default of T. 

If you use this code, please cite this article. Thanks.

Purpose

The purpose of this article is to provide a general concept of how to develop a Quadrant Map, and secondly provide the source for the project.

A Quadrant Map allows for a 2D infinite array in all directions without costly re-sizing or poor scaling that is described below. 

Other Methods 

There are many methods by which you could implement an infinite 2D array. This section describes some of my previous attempts and failures. 

This section will also be referring to a Chunk, which is a class that holds a 2D array with an offset.

class Chunk<T>
{
    public static int Size = 16;
    public int OffsetX, OffsetY;
    public T[,] Data = new T[Size, Size];

    public Chunk(int x, int y) 
    {
        OffsetX = x;
        OffsetY = y;
    }

    public T this[int x, int y]
    {
        get
        {
            //shift x & y into your quadrant space
            x %= Size;
            y %= Size;
            return Data[x, y];
        }
        set
        {
            x %= Size;
            y %= Size;
            Data[x, y] = value;
        }
    }
}  

List  

A potential solution, that is easier to implement, is creating a List<Chunk>. Whenever you search for a specific location in the 2D space, you must instead search the list, for the Chunk offset, and then index into that Chunk's array. 

This is a valid solution so long as your List stays relatively small. The longer the list, the slower the search.

Example of how to search the list:

class ListMap<T>
{
    List<Chunk<T>> Chunks = new List<Chunk<T>>();

    public T this[int x, int y]
    {
        get
        {
            //find chunk offset
            int xm = (int)Math.Floor((double)x / Chunk<T>.Size);
            int ym = (int)Math.Floor((double)y / Chunk<T>.Size);
            Chunk<T> found = FindChunk(xm, ym);

            //if chunk doesn't exist, return default value for T
            if (found == null) return default(T);

            //otherwise return T
            return found[x, y];
        }
        set
        {
            int xm = (int)Math.Floor((double)x / Chunk<T>.Size);
            int ym = (int)Math.Floor((double)y / Chunk<T>.Size);
            Chunk<T> found = FindChunk(xm, ym);

            //if chunk doesn't exist, make it
            if (found == null)
            {
                found = new Chunk<T>(xm, ym);
                Chunks.Add(found);
            }

            //otherwise return T
            found[x, y] = value;
        }
    }

    public Chunk<T> FindChunk(int x, int y)
    {
        return Chunks.Find(
            delegate(Chunk<T> query)
            {
                return query.OffsetX == x && query.OffsetY == y;
            }
        );
    }
} 

Dictionary

The second approach might be using a Dictionary<string, Chunk>, where the key is a unique string based on its offset. This works much better, but it is still a hash table, and there is the difficulty of making and constantly constructing the hash each time you want to retrieve a Chunk.

This is a valid solution that can handle much larger sizes, more efficiently than the list, but you need a good quick unique hash method, If you ever have a collision, this system will fail. When you fail this way you will either overwrite or read existing data, when you expect new data to be created. 

class DictionaryMap<T>
{
    Dictionary<string, Chunk<T>> Chunks = new Dictionary<string, Chunk<T>>();

    public T this[int x, int y]
    {
        get
        {
            //find chunk offset
            int xm = (int)Math.Floor((double)x / Chunk<T>.Size);
            int ym = (int)Math.Floor((double)y / Chunk<T>.Size);
            string key = xm + ":" + ym;

            //if chunk doesn't exist, return default value for T
            if (!Chunks.ContainsKey(key)) return default(T);

            //otherwise return T
            return Chunks[key][x, y];
        }
        set
        {
            int xm = (int)Math.Floor((double)x / Chunk<T>.Size);
            int ym = (int)Math.Floor((double)y / Chunk<T>.Size);
            string key = xm + ":" + ym;

            //if chunk doesn't exist, make it
            if (!Chunks.ContainsKey(key))
            {
                Chunks.Add(key, new Chunk<T>(xm, ym));
            }

            //otherwise return T
            Chunks[key][x, y] = value;
        }
    }
} 

Overview

So, how to solve this problem? Well no doubt this is done before, but the this solution uses a system similar to a binary search tree. 

Binary Search Trees

If you know how binary search trees work, skip past this section. Although I will be describing a special kind of Binary Search Tree (BST). 

To understand how a quad tree works in 2D space we must first analyze a BST. A BST has a Root Node, with two pointers, Left and Right. The Left and Right pointers both may point to null or another Node. This is similar to a List, however, we can store many Nodes, with a shorter path (or equal) from the Root to any other node (this is true if the tree is balanced). 

Example 

        ()
      /    \
    ()      ()
  /       /    \
()      ()      ()

An important feature of BSTs is that Nodes are placed in the tree based on their data. This means the data is inserted based on some function that allows you to find it faster in the future. A default BST has data at each node, and places all data on the Left that compares to be left from the data at the current Node, and all data on the Right that compares to be right from the data. This comparison is done recursively so that you may, for example, place a Node down the path Left, Left, Right, Left, Right.

Example with data 

       (5)
      /   \
   (3)    (8)
  /      /   \
(1)   (6)    (9)

However, I want to discuss a different kind of BST. Instead of each node containing data. Instead data can only be contained at the lowest level of the BST. Each node contains information as to what ranges of data are contained below it. Now all the data is lined up at the bottom. However there is difficulty with this. We need to have a 3rd pointer, that is only used when the Node is a leaf node. This pointer points to the data. 

        (0-7)
       /     \
    (0-3)    (4-7)
   /    \        \
 (0-1) (2-3)      (6-7)
 /     /          /   \
(0)   (2)        (6)  (7)

Also we have the problem that we no longer can just wantonly insert data. Instead if we need to insert data that is beyond the range of the Root Node, we have to make a new Root Node, doubling the range, and placing the previous Root under the new Root. You may also note there is more Nodes created than in the previous example, and I'm only storing 4 bits of data.

Lets take a look at the example of what this tree would look like after inserting the value 8 (which exceeds the Root's range of [0-7]). 

                  (0-15)
               /          \
         (0-7)              (8-15)
        /     \             /
     (0-3)    (4-7)        (8-11)
    /    \       \         /
  (0-1) (2-3)    (6-7)    (8-9)
  /     /        /   \    /
(0)   (2)       (6) (7)  (8)

Notice, that we create a new Root Node, with double the range of the previous Root. Then as we decent to the location where 8 will be placed, we create nodes along the way, each time reducing the range by half. 

Also note, that as you decent the Tree, the range is halved at each step, until you reach a Leaf node, at which point it can point to 0, 1 or 2 points of data. Also the Node representing (4-5) doesn't exist. We didn't need to create it because there is no data down that path.  

Now everyone who knows BSTs well, is going to be yelling at me, but that is okay. This is a feature that is required for moving on to my solution the Quadrant Map 

Quadrant Map 

We are going to use this modified BST to store our Quadrant Map (QM) except that each Node has 4 pointers down, to represent the 4 main quadrants.

Example with 1 Root node, and 4 locations stored (-1,-1), (0,-1), (-1,0) and (0,0). "<>" indicates a value and "[]" indicates a Node: 

<(-1,-1)>              <( 0,-1)>
    \                      /
      [(-1,-1) to ( 0, 0)] 
    /                      \
<(-1, 0)>              <( 0, 0)>  

It gets more complicated the deeper you go, but as you want to store a value at (1,1) you need to push down and double the range of the Root node, so it would represent ranges from (-2, -2) to (1, 1). This is important as you keep expanding the map, you only push down when you need new space, and then only allocate nodes along the tree till you get to the leaf level when adding new nodes.

After 1 push down, and adding value (1, 1). 

[(-2,-2) to (-1,-1)]              [( 0,-2) to (1,-1)] 
             \   \                /  /
              \ <(-1,-1)>  <(0,-1)> /
               [(-2,-2) to ( 1, 1)] 
              / <(-1,0)>   <(0,0)> \
             /   /               \  \
[(-2, 0) to (-1, 1)]              [( 0, 0) to ( 1, 1)]     
                                                     \
                                                   <(1,1)> 

This push down in a Quadrant Map is a bit more complicated. You must create 4 new child Nodes, and each one then gains 1 element from the previous Root Node. Then the Root Node is replaced by a new Root with twice the range. Finally, the (1,1) data point is added to the tree down the appropriate chain.

Code 

The theory above is simplified in the code. The important difference is that the Root node is the only one aware of the negative values. And subsequently, all children nodes are 0 indexed.

To determine the size of each node Height variable is used to compute its Size in the form of 2^Height. Thus a Leaf Node has a Height of 1, and is of size 2. Thus each time a push down is performed a the new Root node has twice the Height of the previous Root, allowing for it to be twice the Size.

The Node Class:

class QuadrantNode<T>
{
    //an indicator if the node is at the leaf height
    public bool IsLeaf { get { return Height == 1; } }
    public int Height { get; protected set; }
    public int Size { get; protected set; }
    public int SizeOver2 { get; protected set; }

    //pointers to other nodes if not a leaf
    QuadrantNode<T>[,] ChildrenNodes;
    //pointers to data if is a leaf
    T[,] ChildrenTs;

    public QuadrantNode(int height)
    {
        Height = height;
        //determin size of node
        Size = (int)Math.Pow(2, height);
        SizeOver2 = Size / 2;

        //allocate pointer arrays depending on node type
        if (IsLeaf)
        {
            ChildrenTs = new T[2, 2];
        }
        else
        {
            ChildrenNodes = new QuadrantNode<T>[2, 2];
        }
    }
    
    //determins the quadrant the x and y values will follow down.
    //and sets them back into the out values
    public void GetQuadrant(int x, int y, out int qx, out int qy)
    {
        qx = (int)Math.Floor((double)x / SizeOver2);
        qy = (int)Math.Floor((double)y / SizeOver2);
    }

    //getter for leaf values
    public bool GetT(int x, int y, out T leafValue)
    {
        leafValue = default(T);
        if (!IsLeaf) return false;
        int qx, qy;
        GetQuadrant(x, y, out qx, out qy);
        leafValue = ChildrenTs[qx, qy];
        return true;
    }

    //settter for leaf values
    public bool SetT(int x, int y, T leafValue)
    {
        if (!IsLeaf) return false;
        int qx, qy;
        GetQuadrant(x, y, out qx, out qy);
        ChildrenTs[qx, qy] = leafValue;
        return true;
    }

    //getter for node values
    public bool GetNode(int x, int y, out QuadrantNode<T> node)
    {
        node = null;
        if (IsLeaf) return false;
        int qx, qy;
        GetQuadrant(x, y, out qx, out qy);
        node = ChildrenNodes[qx, qy];
        return true;
    }
    
    //setter for node values
    public bool SetNode(int x, int y, QuadrantNode<T> node)
    {
        if (IsLeaf) return false;
        int qx, qy;
        GetQuadrant(x, y, out qx, out qy);
        ChildrenNodes[qx, qy] = node;
        return true;
    }
}

The Map class: 

 using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace QuadrantMap
{
    public class QuadrantMap<T>
    {
        //gets height of the root (ie how tall is entire tree)
        public int Height { get { return Root.Height; } }

        QuadrantNode<T> Root;

        public QuadrantMap()
        {
            //set root to leaf node
            Root = new QuadrantNode<T>(1);
        }

        public bool InMap(int x, int y, out int qx, out int qy)
        {
            Root.GetQuadrant(x, y, out qx, out qy);

            //this is different from the node quadrent check, because 
            //we allow negative values thus cover the full x & y field
            if (qx >= -1 && qx <= 0 && qy >= -1 && qy <= 0) return true;
            return false;
        }

        public void PushDown()
        {
            //create a new node 1 taller than the previous (will double size)
            QuadrantNode<T> newRoot = new QuadrantNode<T>(Root.Height + 1);

            //set the children of the new root to nodes
            newRoot.SetNode(0, 0, new QuadrantNode<T>(Root.Height));
            newRoot.SetNode(0, newRoot.SizeOver2, new QuadrantNode<T>(Root.Height));
            newRoot.SetNode(newRoot.SizeOver2, 0, new QuadrantNode<T>(Root.Height));
            newRoot.SetNode(newRoot.SizeOver2, newRoot.SizeOver2, new QuadrantNode<T>(Root.Height));

            QuadrantNode<T> tempNode;

            //if the root is a leaf node, then the children are, so copy T
            if (Root.IsLeaf)
            {
                T tempChild;
                newRoot.GetNode(0, 0, out tempNode);
                Root.GetT(0, 0, out tempChild);
                tempNode.SetT(tempNode.SizeOver2, tempNode.SizeOver2, tempChild);

                newRoot.GetNode(0, newRoot.SizeOver2, out tempNode);
                Root.GetT(0, Root.SizeOver2, out tempChild);
                tempNode.SetT(tempNode.SizeOver2, 0, tempChild);

                newRoot.GetNode(newRoot.SizeOver2, 0, out tempNode);
                Root.GetT(Root.SizeOver2, 0, out tempChild);
                tempNode.SetT(0, tempNode.SizeOver2, tempChild);

                newRoot.GetNode(newRoot.SizeOver2, newRoot.SizeOver2, out tempNode);
                Root.GetT(Root.SizeOver2, Root.SizeOver2, out tempChild);
                tempNode.SetT(0, 0, tempChild);
            }
            //root is not a leaf node, so copy quad nodes
            else
            {
                QuadrantNode<T> tempChild;
                newRoot.GetNode(0, 0, out tempNode);
                Root.GetNode(0, 0, out tempChild);
                tempNode.SetNode(tempNode.SizeOver2, tempNode.SizeOver2, tempChild);

                newRoot.GetNode(0, newRoot.SizeOver2, out tempNode);
                Root.GetNode(0, Root.SizeOver2, out tempChild);
                tempNode.SetNode(tempNode.SizeOver2, 0, tempChild);

                newRoot.GetNode(newRoot.SizeOver2, 0, out tempNode);
                Root.GetNode(Root.SizeOver2, 0, out tempChild);
                tempNode.SetNode(0, tempNode.SizeOver2, tempChild);

                newRoot.GetNode(newRoot.SizeOver2, newRoot.SizeOver2, out tempNode);
                Root.GetNode(Root.SizeOver2, Root.SizeOver2, out tempChild);
                tempNode.SetNode(0, 0, tempChild);
            }

            //overwrite root
            Root = newRoot;
        }

        public T this[int x, int y]
        {
            get
            {
                int qx, qy;
                if (!InMap(x, y, out qx, out qy)) return default(T);

                //shift x and y to use normal corrdinate systems
                x += Root.SizeOver2;
                y += Root.SizeOver2;

                QuadrantNode<T> current = Root;
                while (current != null && current.IsLeaf == false)
                {
                    //determin the quadrant to use.
                    current.GetQuadrant(x, y, out qx, out qy);
                    
                    //shift x and y according to the quadrant values
                    int sx, sy;
                    sx = qx * current.SizeOver2;
                    sy = qy * current.SizeOver2;
                    
                    //get the node
                    current.GetNode(x, y, out current);

                    //shift the x and y down
                    x -= sx;
                    y -= sy;
                }

                if (current == null) return default(T);

                T value;
                current.GetT(x, y, out value);
                return value;
            }
            set
            {
                int qx, qy;
                
                while (!InMap(x, y, out qx, out qy)) PushDown();

                //shift x and y to use normal corrdinate systems
                x += Root.SizeOver2;
                y += Root.SizeOver2;

                QuadrantNode<T> current = Root;
                while (current.IsLeaf == false)
                {
                    //determin the quadrant to use.
                    current.GetQuadrant(x, y, out qx, out qy);

                    //shift x and y according to the quadrant values
                    int sx, sy;
                    sx = qx * current.SizeOver2;
                    sy = qy * current.SizeOver2;

                    //get the node
                    QuadrantNode<T> deeper;
                    current.GetNode(x, y, out deeper);

                    //if next node down is empty, make a new one
                    if (deeper == null)
                    {
                        deeper = new QuadrantNode<T>(current.Height - 1);
                        current.SetNode(x, y, deeper);
                    }
                    current = deeper;

                    //shift the x and y down
                    x -= sx;
                    y -= sy;
                }

                //save the value
                current.SetT(x, y, value);
            }
        }
    }
} 

Using the code  

The code comes wrapped in a class two classes QuadrantMap<T> and QuadrantNode<T> ready to be exported as a DLL with only QuadrantMap<T> public.

Usage:

QuadrantMap<string> map = new QuadrantMap<string>();
map[4, 5] = "hello";
map[4, 6] = "world";

Console.WriteLine(map[4, 5] + map[4, 6]);

Source  

Download QuadrantMapv1.1.zip 

Deficiencies and Errors 

If you notice any deficiencies or errors, please comment with corrections.  

Change Log

31 Oct 2012 - Fixed several Bugs in QuadrantMap<T>.PushDown()