关于四叉树的原理我想应该不需要多说啦，大家都懂得，实在不晓得的话，百度吧~
由于四叉树索引效率还可以并且非常简单，因此在Gis中广泛的应用也是毋庸置疑的。
本次就自己实现一个地图四叉树索引，但是还有一些问题也希望各位路过的大神能指点一下。
首先，结合一下应用场景（我们需要用四叉树来索引地图数据），考虑一下使用四叉树索引地图数据存在的一些问题。
1.什么时候建立四叉树索引，四叉树索引如何存储（序列化还是自己写算法来存储四叉树）？第一次加载数据的时候建立四叉树，当对地图数据操作的时候动态的维护四叉树，关闭地图的时候，保存内存中的四叉树实例，以避免每次建立四叉树耗时。目前我直接使用四叉树序列化。
2.什么东西可能会影响到四叉树索引地图数据的效率？树的深度，空节点每次还要被搜索，使用不平衡四叉树来避免无意义的搜索；每个节点上所关联的地图数据个数。子节点已经包含了地图数据的实例，则父节点不包含，减少数据的冗余。
为了可以在四叉树节点上关联地图数据，设计如下结构来表示地图数据。
/// /// 包含有包络线的对象接口定义 /// public interface IHasBoundingBox { /// /// 几何对象的包络线 /// BoundingBox Box { get; set; } } /// /// 几何对象的的ID和包络线构成索引对象 /// public class GeoBox:IHasBoundingBox { BoundingBox _box; /// /// 几何对象的Id /// public uint ID; #region IHasBoundingBox 成员 public BoundingBox Box { get { return _box; } set { _box = value; } } #endregion }
四叉树节点的定义：
/// /// 四叉树节点 /// ///
节点中所包含的数据类型
public class QuadNode
{ private int _depth; private List
_datas; private BoundingBox _rect; private QuadNode
_lt; private QuadNode
_rt; private QuadNode
_lb; private QuadNode
_rb; private bool _isLeaf; private QuadNodeLimit _limit; public QuadNodeLimit Limit { get { return _limit; } } public bool IsLeaf { get { return _isLeaf; } set { _isLeaf = value; } } public int Depth { get { return _depth; } set { _depth = value; } } public List
Datas { get { return _datas; } set { _datas = value; } } public BoundingBox Rect { get { return _rect; } set { _rect = value; } } public QuadNode
LT { get { return _lt; } set { _lt = value; } } public QuadNode
RT { get { return _rt; } set { _rt = value; } } public QuadNode
LB { get { return _lb; } set { _lb = value; } } public QuadNode
RB { get { return _rb; } set { _rb = value; } } public QuadNode(BoundingBox box,QuadNodeLimit limit, int depth) { _datas = new List
(); _rect = box; _lt = null; _rt = null; _lb = null; _rb = null; _isLeaf = true; _depth = depth; _limit = limit; } public bool Insert(T data) { QuadNode
ret = QueryNode((data as IHasBoundingBox).Box); if (ret != null) { //此处开始分裂子节点，不是平衡四叉树 if ( ret.Datas.Count >= _limit.MaxObjNum && ret.Depth < _limit.MaxDepth) { BoundingBox childBox; double xmin = 0; double ymin = 0; double xmax = 0; double ymax = 0; // 开始分裂子节点 if (ret.LT == null) { xmin = _rect.Min.X; ymin = _rect.Min.Y; xmax = _rect.Min.X + _rect.Width / 2; ymax = _rect.Min.Y + _rect.Height/2; childBox = new BoundingBox(xmin, ymin, xmax, ymax); if (childBox.Contains((data as IHasBoundingBox).Box)) { ret.LT = new QuadNode
(childBox, ret.Limit, ret.Depth + 1); ret.IsLeaf = false; SplitDatas(ret.LT, ret.Datas); ret = ret.LT; } } if (ret.RT == null) { xmin = _rect.Min.X + _rect.Width / 2; ymin = _rect.Min.Y; xmax = _rect.Max.X; ymax = _rect.Min.Y + _rect.Height / 2; childBox = new BoundingBox(xmin, ymin, xmax, ymax); if (childBox.Contains((data as IHasBoundingBox).Box)) { ret.RT = new QuadNode
(childBox, ret.Limit, ret.Depth + 1); ret.IsLeaf = false; SplitDatas(ret.RT, ret.Datas); ret = ret.RT; } } if (ret.LB == null) { xmin = _rect.Min.X; ymin = _rect.Min.Y + _rect.Height / 2; xmax = _rect.Min.X + _rect.Width / 2; ymax = _rect.Max.Y; childBox = new BoundingBox(xmin, ymin, xmax, ymax); if (childBox.Contains((data as IHasBoundingBox).Box)) { ret.LB = new QuadNode
(childBox, ret.Limit, ret.Depth + 1); ret.IsLeaf = false; SplitDatas(ret.LB, ret.Datas); ret = ret.LB; } } if (ret.RB == null) { xmin = _rect.Min.X + _rect.Width / 2; ymin = _rect.Min.Y + _rect.Height / 2; xmax = _rect.Max.X; ymax = _rect.Max.Y; childBox = new BoundingBox(xmin, ymin, xmax, ymax); if (childBox.Contains((data as IHasBoundingBox).Box)) { ret.RB = new QuadNode
(childBox, ret.Limit, ret.Depth + 1); ret.IsLeaf = false; SplitDatas(ret.RB, ret.Datas); ret = ret.RB; } } } ret.Datas.Add(data); return true; } else return false; } public void Remove(T data) { QuadNode
ret = QueryNode((data as IHasBoundingBox).Box); if (ret != null) ret.Datas.Remove(data); } public QuadNode
QueryNode(BoundingBox env) { QuadNode
ret = null; if (Rect.Contains(env) || Rect.Equals(env)) { ret = this; } else if (env.Contains(Rect)) { return this; } else { return null; } if (LT != null && LT.Rect.Contains(env)) { ret = LT.QueryNode(env); } else if (RT != null && RT.Rect.Contains(env)) { ret = RT.QueryNode(env); } else if (LB != null && LB.Rect.Contains(env)) { ret = LB.QueryNode(env); } else if (RB != null && RB.Rect.Contains(env)) { ret = RB.QueryNode(env); } return ret; } public void QueryData(QuadNode
node, ref List
datas) { QuadNode
tempNode = node; datas.AddRange(tempNode.Datas); if (tempNode.LT != null) { QueryData(tempNode.LT, ref datas); } if (tempNode.LB != null) { QueryData(tempNode.LB, ref datas); } if (tempNode.RT != null) { QueryData(tempNode.RT, ref datas); } if (tempNode.RB != null) { QueryData(tempNode.RB, ref datas); } } private void SplitDatas(QuadNode
node, List
datas) { for (int i = 0; i < datas.Count; i++) { if (node.Rect.Contains((datas[i] as IHasBoundingBox).Box)) { node.Datas.Add(datas[i]); } } //是否去掉父节点重复的节点，若是去掉获取数据消耗时间会变长，若是没有去掉则树中会有大量的冗余数据 for (int i = 0; i < node.Datas.Count; i++) { datas.Remove(node.Datas[i]); } } }
四叉树的定义：
/// /// 四叉树地图索引 /// 四叉树必须要保证层数不能太深，同时也要保证节点保存对象数目不能大于规定的最大对象数目 /// 上述两个条件冲突时以深度为优先判断要素 /// 节点保存对象数目小于规定的最小保存数目时该节点则该节点不再分裂子节点 /// 注意：删除数据时该树不会自动萎缩，用户可以调用重新构造树的方法进行维护树 /// devCopper 2013.9.12 /// ///
保存对象的数据类型
public class QuadTree
where T : IHasBoundingBox { QuadNode
_root; List
_datas; ///
/// 四叉树的根节点 /// public QuadNode
Root { get { return _root; } set { _root = value; } } ///
/// 所有被索引的对象 /// public List
Datas { get { return _datas; } set { _datas = value; } } public QuadTree() { } ///
/// 构造函数 /// ///
根节点的包围盒 public QuadTree(BoundingBox env, QuadNodeLimit limit) { _root = new QuadNode
(env, limit, 0); _datas = new List
(); } ///
/// 插入一个对象 /// ///
插入的数据 public void Insert(T data) { _root.Insert(data); _datas.Add(data); } /// /// 移除一个对象 /// /// 移除的对象,该对象的BoundingBox属性值不需要关心 public void Remove(T data) { _root.Remove(data); _datas.Remove(data); } /// /// 遍历四叉树查询矩形框所包含的对象 /// /// 查询条件 ///
包含对象的节点
public List
Query(BoundingBox env) { List
data = new List
(); QuadNode
ret = _root.QueryNode(env); if (ret != null) ret.QueryData(ret, ref data); return data; } ///
/// 初始化四叉树 /// ///
初始化对象 public void Initialize(List
datas) { for (int i = 0; i < datas.Count; i++) { if(_root.Insert(datas[i])) _datas.Add(datas[i]); } } ///
/// 重新构造索引 /// public void Rebuild() { for (int i = 0; i < _datas.Count; i++) { _root.Insert(_datas[i]); } } ///
/// 从文件中读取四叉树索引 /// ///
文件 ///
一颗四叉树
public static QuadTree
FromFile(string file) { System.IO.FileStream fs = new System.IO.FileStream(file, System.IO.FileMode.Open); BinaryFormatter bf = new BinaryFormatter(); QuadTree
tree = (QuadTree
)bf.Deserialize(fs); fs.Close(); return tree; } ///
/// 保存四叉树索引 /// ///
四叉树对象 /// 保存的文件 public static void SaveIndex(QuadTree
tree, string file) { System.IO.FileStream fs = new System.IO.FileStream(file, System.IO.FileMode.CreateNew); BinaryFormatter bf = new BinaryFormatter(); bf.Serialize(fs, tree); fs.Close(); } }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/217074.html原文链接：https://javaforall.net
