象限图
用于 2D 空间的树形表示，允许无限扩展
引言
如果您曾有过想要一个无限二维数组的愿望，但又意识到使用固定二维数组实现它是不可能的，那么这就是解决方案。这里的实现是用 C# 使用泛型（或模板）完成的。
Quadrant Map 的意思是，您可以表示典型欧几里得坐标系的所有四个象限，而不仅仅局限于正整数。这意味着您可以使用完整的字段数据，拥有负数的 x 和 y 索引。
实现此功能的 **方法** 也支持稀疏输入和数据检索。如果未设置数据值，则其值为 T 的默认值。
如果您使用此代码，请引用本文。谢谢。
目的
本文旨在提供开发 Quadrant Map 的通用概念，并提供项目源代码。
Quadrant Map 允许在所有方向上实现二维无限数组，而无需昂贵的 **重新调整大小** 或下面描述的糟糕的 **扩展性**。
其他方法
有许多方法可以实现无限二维数组。本节将介绍我之前的一些尝试和失败。
本节还将 **引用** 一个 Chunk，它是一个带有偏移量的类，用于保存二维数组。
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
一种潜在的、更容易实现的解决方案是创建一个 List<Chunk>。每当您搜索二维空间中的特定位置时，您必须在列表中搜索 Chunk 的偏移量，然后索引到该 Chunk 的数组中。
只要您的列表保持相对较小，这都是一个有效的解决方案。列表越长，搜索速度越慢。
搜索列表的示例
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<string, Chunk>，其中键是基于其偏移量的唯一字符串。这效果更好，但它仍然是一个哈希表，并且每次想要检索 Chunk 时，都会有制作和不断构建哈希的困难。
这是一个有效的解决方案，可以比列表更有效地处理更大的尺寸，但您需要一个好的、快速的唯一哈希方法。如果您遇到冲突，此系统将失败。当您这样失败时，您将覆盖或读取现有数据，而您期望的是创建新数据。
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;
}
}
} 概述
那么，如何解决这个问题呢？嗯，毫无疑问，这个问题以前就被解决过，但这个解决方案使用了一个类似于二叉搜索树的系统。
二叉搜索树
如果您知道二叉搜索树是如何工作的，请跳过本节。尽管我将描述一种特殊的二叉搜索树 (BST)。
要理解四叉树在二维空间中是如何工作的，我们必须首先分析一个 BST。BST 有一个根节点，带有两个指针：左指针和右指针。左指针和右指针都可以指向 null 或另一个节点。这类似于列表，但是，我们可以存储许多节点，并且从根到任何其他节点的路径都更短（或相等）（如果树是平衡的，这是真的）。
示例
()
/ \
() ()
/ / \
() () () BST 的一个重要特性是节点是根据其数据放置在树中的。这意味着数据是基于某个函数插入的，该函数允许您将来更快地找到它。默认的 BST 在每个节点都有数据，并将所有与当前节点数据相比更小的数据放在左侧，将所有与当前节点数据相比更大的数据放在右侧。这个比较是递归进行的，因此，例如，您可以沿路径左、左、右、左、右放置一个节点。
数据示例
(5)
/ \
(3) (8)
/ / \
(1) (6) (9) 但是，我想讨论一种不同的 BST。每个节点不包含数据。相反，数据只能包含在 BST 的最低级别。每个节点都包含有关其下方包含的数据范围的信息。现在所有数据都排列在底部。但是这存在困难。我们需要有一个第三个指针，该指针仅在节点是叶节点时使用。此指针指向数据。
(0-7)
/ \
(0-3) (4-7)
/ \ \
(0-1) (2-3) (6-7)
/ / / \
(0) (2) (6) (7) 另外，我们还有一个问题，那就是我们不能再 **随意** 插入数据了。相反，如果我们想插入超出根节点范围的数据，我们必须创建一个新的根节点，将范围加倍，并将以前的根节点放在新根节点之下。您可能还会注意到创建的节点比上一个示例中的多，而且我只存储了 4 位数据。
让我们看一下在插入值 8（超出根节点的 [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) 请注意，我们创建了一个新的根节点，其范围是先前根节点的两倍。然后，当我们下降到放置 8 的位置时，我们沿途创建节点，每次将范围减半。
另请注意，当您下降树时，范围在每一步 **减半**，直到达到叶节点，此时它可以指向 0、1 或 2 个数据点。此外，表示 (4-5) 的节点不存在。我们不必创建它，因为该路径上没有数据。
现在，每个熟悉 BST 的人都会对我大喊大叫，但没关系。这是继续我的 Quadrant Map 解决方案所需的一个功能。
Quadrant Map
我们将使用这个修改后的 BST 来存储我们的 Quadrant Map (QM)，只不过每个节点都有 4 个向下的指针，代表四个主要象限。
具有 1 个根节点和 4 个已存储位置（-1,-1）、(0,-1)、(-1,0) 和 (0,0) 的示例。 "<>" 表示一个值，"[]" 表示一个节点：
<(-1,-1)> <( 0,-1)>
\ /
[(-1,-1) to ( 0, 0)]
/ \
<(-1, 0)> <( 0, 0)> 随着您深入，情况会变得更加复杂，但是当您想在 (1,1) 存储一个值时，您需要向下推并加倍根节点的范围，使其表示从 (-2, -2) 到 (1, 1) 的范围。当您不断扩展地图时，这一点很重要，您只在需要新空间时向下推，然后在添加新节点时，只分配树中的节点直到叶级别。
在向下推一次并添加值 (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)>
Quadrant Map 中的这个向下推过程要复杂一些。您必须创建 4 个新的子节点，每个子节点从先前的根节点获得 1 个元素。然后，根节点被一个范围是其两倍的新根节点替换。最后，(1,1) 数据点被添加到树中的相应链路上。
代码
上面的理论在代码中得到了简化。重要的区别在于，根节点是唯一知道负值的节点。因此，所有子节点都从 0 开始索引。
要确定每个节点的大小，会使用 Height 变量来计算其大小，形式为 2Height。因此，叶节点的高度为 1，大小为 2。因此，每次执行向下推操作时，新的根节点的高度是先前根节点高度的两倍，使其大小也增加一倍。
Node 类
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;
}
}Map 类：
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);
}
}
}
} 使用代码
代码被包装在两个类 QuadrantMap<T> 和 QuadrantNode<T> 中，可以导出为 DLL，只有 QuadrantMap<T> 是公共的。
用法
QuadrantMap<string> map = new QuadrantMap<string>();
map[4, 5] = "hello";
map[4, 6] = "world";
Console.WriteLine(map[4, 5] + map[4, 6]);
源代码
不足和错误
如果您注意到任何不足或错误，请发表评论进行更正。
更改日志
2012 年 10 月 31 日 - 修复了 QuadrantMap<T>.PushDown() 中的几个 Bug。