## 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
{
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
{
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 (found == null) return default(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 (found == null)
{
found = new Chunk<T>(xm, ym);
Chunks.Add(found);
}
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
{
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 (!Chunks.ContainsKey(key)) return default(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 (!Chunks.ContainsKey(key))
{
Chunks.Add(key, new Chunk<T>(xm, ym));
}
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>
{
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; }
QuadrantNode<T>[,] ChildrenNodes;
T[,] ChildrenTs;
public QuadrantNode(int height)
{
Height = height;
Size = (int)Math.Pow(2, height);
SizeOver2 = Size / 2;
if (IsLeaf)
{
ChildrenTs = new T[2, 2];
}
else
{
ChildrenNodes = new QuadrantNode<T>[2, 2];
}
}
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);
}
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;
}
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;
}
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;
}
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>
{
public int Height { get { return Root.Height; } }
QuadrantNode<T> Root;
public QuadrantMap()
{
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);
if (qx >= -1 && qx <= 0 && qy >= -1 && qy <= 0) return true;
return false;
}
public void PushDown()
{
QuadrantNode<T> newRoot = new QuadrantNode<T>(Root.Height + 1);
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 (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);
}
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);
}
Root = newRoot;
}
public T this[int x, int y]
{
get
{
int qx, qy;
if (!InMap(x, y, out qx, out qy)) return default(T);
x += Root.SizeOver2;
y += Root.SizeOver2;
QuadrantNode<T> current = Root;
while (current != null && current.IsLeaf == false)
{
current.GetQuadrant(x, y, out qx, out qy);
int sx, sy;
sx = qx * current.SizeOver2;
sy = qy * current.SizeOver2;
current.GetNode(x, y, out current);
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();
x += Root.SizeOver2;
y += Root.SizeOver2;
QuadrantNode<T> current = Root;
while (current.IsLeaf == false)
{
current.GetQuadrant(x, y, out qx, out qy);
int sx, sy;
sx = qx * current.SizeOver2;
sy = qy * current.SizeOver2;
QuadrantNode<T> deeper;
current.GetNode(x, y, out deeper);
if (deeper == null)
{
deeper = new QuadrantNode<T>(current.Height - 1);
current.SetNode(x, y, deeper);
}
current = deeper;
x -= sx;
y -= sy;
}
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()