Index: src/Common/SharpMap/Utilities/Indexing/SpatialIndexing.cs =================================================================== diff -u -r8f6ae890fed8e8eae3a32f9c0498a10f82e0ddf9 -r5fc71a385897af92ccb092f2f969b5709afab85a --- src/Common/SharpMap/Utilities/Indexing/SpatialIndexing.cs (.../SpatialIndexing.cs) (revision 8f6ae890fed8e8eae3a32f9c0498a10f82e0ddf9) +++ src/Common/SharpMap/Utilities/Indexing/SpatialIndexing.cs (.../SpatialIndexing.cs) (revision 5fc71a385897af92ccb092f2f969b5709afab85a) @@ -18,396 +18,413 @@ using System; using System.Collections.Generic; using System.Collections.ObjectModel; +using System.IO; using GeoAPI.Geometries; using GisSharpBlog.NetTopologySuite.Geometries; using GeometryFactory = SharpMap.Converters.Geometries.GeometryFactory; namespace SharpMap.Utilities.SpatialIndexing { - /// - /// Heuristics used for tree generation - /// - public struct Heuristic - { - /// - /// Maximum tree depth - /// - public int maxdepth; - /// - /// Minimum object count at node - /// - public int mintricnt; - /// - /// Target object count at node - /// - public int tartricnt; - /// - /// Minimum Error metric � the volume of a box + a unit cube. - /// The unit cube in the metric prevents big boxes that happen to be flat having a zero result and muddling things up. - /// - public int minerror; - } - - /// - /// Constructs a Quad-tree node from a object list and creates its children recursively - /// - public class QuadTreeOld : IDisposable - { - private List _objList; - private IEnvelope _box = new Envelope(); - private QuadTreeOld _child0; - private QuadTreeOld _child1; - /// - /// Nodes depth in a tree - /// - protected uint _Depth; - /// - /// Node ID - /// - public uint? _ID; + /// + /// Heuristics used for tree generation + /// + public struct Heuristic + { + /// + /// Maximum tree depth + /// + public int maxdepth; - /// - /// BoundingBox and Feature ID structure used for storing in the quadtree - /// - public struct BoxObjects - { - /// - /// Boundingbox - /// - public IEnvelope box; - /// - /// Feature ID - /// - public uint ID; - } + /// + /// Minimum object count at node + /// + public int mintricnt; - /// - /// Creates a node and either splits the objects recursively into sub-nodes, or stores them at the node depending on the heuristics. - /// Tree is built top->down - /// - /// Geometries to index - /// Current depth of tree - /// Heuristics data - public QuadTreeOld(List objList, uint depth, Heuristic heurdata) - { - _Depth = depth; - _box = new Envelope(objList[0].box); - for (int i = 0; i < objList.Count;i++ ) - _box.ExpandToInclude(objList[i].box); - - // test our build heuristic - if passes, make children - if (depth < heurdata.maxdepth && objList.Count > heurdata.mintricnt && - (objList.Count > heurdata.tartricnt || ErrorMetric(_box) > heurdata.minerror)) - { - List[] objBuckets = new List[2]; // buckets of geometries - objBuckets[0] = new List(); - objBuckets[1] = new List(); + /// + /// Target object count at node + /// + public int tartricnt; - string longaxis = LongestAxis(_box); // longest axis - double geoavg = 0; // geometric average - midpoint of ALL the objects + /// + /// Minimum Error metric � the volume of a box + a unit cube. + /// The unit cube in the metric prevents big boxes that happen to be flat having a zero result and muddling things up. + /// + public int minerror; + } - // go through all bbox and calculate the average of the midpoints - double frac = 1.0f / objList.Count; - for (int i = 0; i < objList.Count;i++ ) - { - if (longaxis=="X") - geoavg += objList[i].box.Centre.X * frac; - else - geoavg += objList[i].box.Centre.Y * frac; - } + /// + /// Constructs a Quad-tree node from a object list and creates its children recursively + /// + public class QuadTreeOld : IDisposable + { + /// + /// Node ID + /// + public uint? _ID; -// // bucket bbox based on their midpoint's side of the geo average in the longest axis - for (int i = 0; i < objList.Count;i++ ) - { - if(longaxis=="X") - objBuckets[geoavg > objList[i].box.Centre.X ? 1 : 0].Add(objList[i]); - else - objBuckets[geoavg > objList[i].box.Centre.Y ? 1 : 0].Add(objList[i]); - } + /// + /// Nodes depth in a tree + /// + protected uint _Depth; - //If objects couldn't be splitted, just store them at the leaf - //TODO: Try splitting on another axis - if (objBuckets[0].Count == 0 || objBuckets[1].Count == 0) - { - _child0 = null; - _child1 = null; - // copy object list - _objList = objList; - } - else - { - // create new children using the buckets - _child0 = new QuadTreeOld(objBuckets[0], depth + 1, heurdata); - _child1 = new QuadTreeOld(objBuckets[1], depth + 1, heurdata); - } - } - else - { - // otherwise the build heuristic failed, this is - // set the first child to null (identifies a leaf) - _child0 = null; - _child1 = null; - // copy object list - _objList = objList; - } - } + private List _objList; + private IEnvelope _box = new Envelope(); - /// - /// This instantiator is used internally for loading a tree from a file - /// - private QuadTreeOld() - { - } + /// + /// Creates a node and either splits the objects recursively into sub-nodes, or stores them at the node depending on the heuristics. + /// Tree is built top->down + /// + /// Geometries to index + /// Current depth of tree + /// Heuristics data + public QuadTreeOld(List objList, uint depth, Heuristic heurdata) + { + _Depth = depth; + _box = new Envelope(objList[0].box); + for (int i = 0; i < objList.Count; i++) + { + _box.ExpandToInclude(objList[i].box); + } - #region Read/Write index to/from a file + // test our build heuristic - if passes, make children + if (depth < heurdata.maxdepth && objList.Count > heurdata.mintricnt && + (objList.Count > heurdata.tartricnt || ErrorMetric(_box) > heurdata.minerror)) + { + List[] objBuckets = new List[2]; // buckets of geometries + objBuckets[0] = new List(); + objBuckets[1] = new List(); - private const double INDEXFILEVERSION = 1.0; + string longaxis = LongestAxis(_box); // longest axis + double geoavg = 0; // geometric average - midpoint of ALL the objects - internal class ObsoleteFileFormatException : System.Exception - { - /// - /// Exception thrown when layer rendering has failed - /// - /// - public ObsoleteFileFormatException(string message) - : base(message) - { - } - } + // go through all bbox and calculate the average of the midpoints + double frac = 1.0f/objList.Count; + for (int i = 0; i < objList.Count; i++) + { + if (longaxis == "X") + { + geoavg += objList[i].box.Centre.X*frac; + } + else + { + geoavg += objList[i].box.Centre.Y*frac; + } + } - /// - /// Loads a quadtree from a file - /// - /// - /// - public static QuadTreeOld FromFile(string filename) - { - System.IO.FileStream fs = new System.IO.FileStream(filename, System.IO.FileMode.Open,System.IO.FileAccess.Read); - System.IO.BinaryReader br = new System.IO.BinaryReader(fs); - if (br.ReadDouble() != INDEXFILEVERSION) //Check fileindex version - { - fs.Close(); - fs.Dispose(); - throw new ObsoleteFileFormatException("Invalid index file version. Please rebuild the spatial index by either deleting the index"); - } - QuadTreeOld node = ReadNode(0, ref br); - br.Close(); - fs.Close(); - return node; - } +// // bucket bbox based on their midpoint's side of the geo average in the longest axis + for (int i = 0; i < objList.Count; i++) + { + if (longaxis == "X") + { + objBuckets[geoavg > objList[i].box.Centre.X ? 1 : 0].Add(objList[i]); + } + else + { + objBuckets[geoavg > objList[i].box.Centre.Y ? 1 : 0].Add(objList[i]); + } + } - /// - /// Reads a node from a stream recursively - /// - /// Current depth - /// Binary reader reference - /// - private static QuadTreeOld ReadNode(uint depth, ref System.IO.BinaryReader br) - { - QuadTreeOld node = new QuadTreeOld(); - node._Depth = depth; - node.Box = GeometryFactory.CreateEnvelope(br.ReadDouble(),br.ReadDouble(),br.ReadDouble(),br.ReadDouble()); - bool IsLeaf = br.ReadBoolean(); - if (IsLeaf) - { - int FeatureCount = br.ReadInt32(); - node._objList = new List(); - for (int i = 0; i < FeatureCount; i++) - { - BoxObjects box = new BoxObjects(); - box.box = GeometryFactory.CreateEnvelope(br.ReadDouble(), br.ReadDouble(), br.ReadDouble(), br.ReadDouble()); - box.ID = (uint)br.ReadInt32(); - node._objList.Add(box); - } - } - else - { - node.Child0 = ReadNode(node._Depth + 1, ref br); - node.Child1 = ReadNode(node._Depth + 1, ref br); - } - return node; - } + //If objects couldn't be splitted, just store them at the leaf + //TODO: Try splitting on another axis + if (objBuckets[0].Count == 0 || objBuckets[1].Count == 0) + { + Child0 = null; + Child1 = null; + // copy object list + _objList = objList; + } + else + { + // create new children using the buckets + Child0 = new QuadTreeOld(objBuckets[0], depth + 1, heurdata); + Child1 = new QuadTreeOld(objBuckets[1], depth + 1, heurdata); + } + } + else + { + // otherwise the build heuristic failed, this is + // set the first child to null (identifies a leaf) + Child0 = null; + Child1 = null; + // copy object list + _objList = objList; + } + } - /// - /// Saves the Quadtree to a file - /// - /// - public void SaveIndex(string filename) - { - System.IO.FileStream fs = new System.IO.FileStream(filename, System.IO.FileMode.Create); - System.IO.BinaryWriter bw = new System.IO.BinaryWriter(fs); - bw.Write(INDEXFILEVERSION); //Save index version - SaveNode(this, ref bw); - bw.Close(); - fs.Close(); - } - /// - /// Saves a node to a stream recursively - /// - /// Node to save - /// Reference to BinaryWriter - private void SaveNode(QuadTreeOld node, ref System.IO.BinaryWriter sw) - { - //Write node boundingbox - sw.Write(node.Box.MinX); - sw.Write(node.Box.MinY); - sw.Write(node.Box.MaxX); - sw.Write(node.Box.MaxY); - sw.Write(node.IsLeaf); - if (node.IsLeaf) - { - sw.Write(node._objList.Count); //Write number of features at node - for (int i = 0; i < node._objList.Count;i++ ) //Write each featurebox - { - sw.Write(node._objList[i].box.MinX); - sw.Write(node._objList[i].box.MinY); - sw.Write(node._objList[i].box.MaxX); - sw.Write(node._objList[i].box.MaxY); - sw.Write(node._objList[i].ID); - } - } - else if (!node.IsLeaf) //Save next node - { - SaveNode(node.Child0, ref sw); - SaveNode(node.Child1, ref sw); - } - } + /// + /// This instantiator is used internally for loading a tree from a file + /// + private QuadTreeOld() {} - #endregion + /// + /// Determines whether the node is a leaf (if data is stored at the node, we assume the node is a leaf) + /// + public bool IsLeaf + { + get + { + return (_objList != null); + } + } - /// - /// Calculate the floating point error metric - /// - /// - public double ErrorMetric(IEnvelope box) - { - ICoordinate temp = SharpMap.Converters.Geometries.GeometryFactory.CreateCoordinate(1 + (box.MaxX-box.MinX), 1 + (box.MaxY-box.MinY)); - return temp.X*temp.Y; - } - - /// - /// Determines whether the node is a leaf (if data is stored at the node, we assume the node is a leaf) - /// - public bool IsLeaf - { - get { return (_objList != null); } - } + ///// + ///// Gets/sets the list of objects in the node + ///// + //public List ObjList + //{ + // get { return _objList; } + // set { _objList = value; } + //} - ///// - ///// Gets/sets the list of objects in the node - ///// - //public List ObjList - //{ - // get { return _objList; } - // set { _objList = value; } - //} + /// + /// Gets/sets the Axis Aligned Bounding Box + /// + public IEnvelope Box + { + get + { + return _box; + } + set + { + _box = value; + } + } - /// - /// Gets/sets the Axis Aligned Bounding Box - /// - public IEnvelope Box - { - get { return _box; } - set { _box = value; } - } + /// + /// Gets/sets the left child node + /// + public QuadTreeOld Child0 { get; set; } - /// - /// Gets/sets the left child node - /// - public QuadTreeOld Child0 - { - get { return _child0; } - set { _child0 = value; } - } + /// + /// Gets/sets the right child node + /// + public QuadTreeOld Child1 { get; set; } - /// - /// Gets/sets the right child node - /// - public QuadTreeOld Child1 - { - get { return _child1; } - set { _child1 = value; } - } - /// - /// Gets the depth of the current node in the tree - /// - public uint Depth - { - get { return _Depth; } - } + /// + /// Gets the depth of the current node in the tree + /// + public uint Depth + { + get + { + return _Depth; + } + } - /// - /// Disposes the node - /// - public void Dispose() - { - //this._box = null; - this._child0 = null; - this._child1 = null; - this._objList = null; - } + /// + /// Calculate the floating point error metric + /// + /// + public double ErrorMetric(IEnvelope box) + { + ICoordinate temp = GeometryFactory.CreateCoordinate(1 + (box.MaxX - box.MinX), 1 + (box.MaxY - box.MinY)); + return temp.X*temp.Y; + } - /// - /// Searches the tree and looks for intersections with the boundingbox 'bbox' - /// - /// Boundingbox to intersect with - public Collection Search(IEnvelope box) - { - Collection objectlist = new Collection(); - IntersectTreeRecursive(box, this, ref objectlist); - return objectlist; - } + /// + /// Searches the tree and looks for intersections with the boundingbox 'bbox' + /// + /// Boundingbox to intersect with + public Collection Search(IEnvelope box) + { + Collection objectlist = new Collection(); + IntersectTreeRecursive(box, this, ref objectlist); + return objectlist; + } - /// - /// Recursive function that traverses the tree and looks for intersections with a boundingbox - /// - /// Boundingbox to intersect with - /// Node to search from - /// List of found intersections - private void IntersectTreeRecursive(IEnvelope box, QuadTreeOld node, ref Collection list) - { - if (node.IsLeaf) //Leaf has been reached - { + /// + /// Disposes the node + /// + public void Dispose() + { + //this._box = null; + Child0 = null; + Child1 = null; + _objList = null; + } + + /// + /// Recursive function that traverses the tree and looks for intersections with a boundingbox + /// + /// Boundingbox to intersect with + /// Node to search from + /// List of found intersections + private void IntersectTreeRecursive(IEnvelope box, QuadTreeOld node, ref Collection list) + { + if (node.IsLeaf) //Leaf has been reached + { for (int i = 0; i < node._objList.Count; i++) { list.Add((int) node._objList[i].ID); } - } - else - { - if(node.Box.Intersects(box)) - { - IntersectTreeRecursive(box, node.Child0, ref list); - IntersectTreeRecursive(box, node.Child1, ref list); - } - } - } - - /// - /// Intersection scalar (used for weighting in building the tree) - /// #Todo - /// - private string LongestAxis(IEnvelope box) - { - ICoordinate boxdim = GeometryFactory.CreateCoordinate(box.MaxX-box.MinX,box.MaxY-box.MinY); - string la = String.Empty; // longest axis - double lav = 0; // longest axis length - // for each dimension - //for (uint ii = 0; ii < 2; ii++) - //{ - // check if its longer - if (boxdim.X > lav) - { - la = "X"; - lav = boxdim.X; - } + } + else + { + if (node.Box.Intersects(box)) + { + IntersectTreeRecursive(box, node.Child0, ref list); + IntersectTreeRecursive(box, node.Child1, ref list); + } + } + } - if (boxdim.Y > lav) - { - la = "Y"; - lav = boxdim.Y; - } - return la; - } - } -} + /// + /// Intersection scalar (used for weighting in building the tree) + /// #Todo + /// + private string LongestAxis(IEnvelope box) + { + ICoordinate boxdim = GeometryFactory.CreateCoordinate(box.MaxX - box.MinX, box.MaxY - box.MinY); + string la = String.Empty; // longest axis + double lav = 0; // longest axis length + // for each dimension + //for (uint ii = 0; ii < 2; ii++) + //{ + // check if its longer + if (boxdim.X > lav) + { + la = "X"; + lav = boxdim.X; + } + + if (boxdim.Y > lav) + { + la = "Y"; + lav = boxdim.Y; + } + return la; + } + + /// + /// BoundingBox and Feature ID structure used for storing in the quadtree + /// + public struct BoxObjects + { + /// + /// Boundingbox + /// + public IEnvelope box; + + /// + /// Feature ID + /// + public uint ID; + } + + #region Read/Write index to/from a file + + private const double INDEXFILEVERSION = 1.0; + + internal class ObsoleteFileFormatException : Exception + { + /// + /// Exception thrown when layer rendering has failed + /// + /// + public ObsoleteFileFormatException(string message) + : base(message) {} + } + + /// + /// Loads a quadtree from a file + /// + /// + /// + public static QuadTreeOld FromFile(string filename) + { + FileStream fs = new FileStream(filename, FileMode.Open, FileAccess.Read); + BinaryReader br = new BinaryReader(fs); + if (br.ReadDouble() != INDEXFILEVERSION) //Check fileindex version + { + fs.Close(); + fs.Dispose(); + throw new ObsoleteFileFormatException("Invalid index file version. Please rebuild the spatial index by either deleting the index"); + } + QuadTreeOld node = ReadNode(0, ref br); + br.Close(); + fs.Close(); + return node; + } + + /// + /// Reads a node from a stream recursively + /// + /// Current depth + /// Binary reader reference + /// + private static QuadTreeOld ReadNode(uint depth, ref BinaryReader br) + { + QuadTreeOld node = new QuadTreeOld(); + node._Depth = depth; + node.Box = GeometryFactory.CreateEnvelope(br.ReadDouble(), br.ReadDouble(), br.ReadDouble(), br.ReadDouble()); + bool IsLeaf = br.ReadBoolean(); + if (IsLeaf) + { + int FeatureCount = br.ReadInt32(); + node._objList = new List(); + for (int i = 0; i < FeatureCount; i++) + { + BoxObjects box = new BoxObjects(); + box.box = GeometryFactory.CreateEnvelope(br.ReadDouble(), br.ReadDouble(), br.ReadDouble(), br.ReadDouble()); + box.ID = (uint) br.ReadInt32(); + node._objList.Add(box); + } + } + else + { + node.Child0 = ReadNode(node._Depth + 1, ref br); + node.Child1 = ReadNode(node._Depth + 1, ref br); + } + return node; + } + + /// + /// Saves the Quadtree to a file + /// + /// + public void SaveIndex(string filename) + { + FileStream fs = new FileStream(filename, FileMode.Create); + BinaryWriter bw = new BinaryWriter(fs); + bw.Write(INDEXFILEVERSION); //Save index version + SaveNode(this, ref bw); + bw.Close(); + fs.Close(); + } + + /// + /// Saves a node to a stream recursively + /// + /// Node to save + /// Reference to BinaryWriter + private void SaveNode(QuadTreeOld node, ref BinaryWriter sw) + { + //Write node boundingbox + sw.Write(node.Box.MinX); + sw.Write(node.Box.MinY); + sw.Write(node.Box.MaxX); + sw.Write(node.Box.MaxY); + sw.Write(node.IsLeaf); + if (node.IsLeaf) + { + sw.Write(node._objList.Count); //Write number of features at node + for (int i = 0; i < node._objList.Count; i++) //Write each featurebox + { + sw.Write(node._objList[i].box.MinX); + sw.Write(node._objList[i].box.MinY); + sw.Write(node._objList[i].box.MaxX); + sw.Write(node._objList[i].box.MaxY); + sw.Write(node._objList[i].ID); + } + } + else if (!node.IsLeaf) //Save next node + { + SaveNode(node.Child0, ref sw); + SaveNode(node.Child1, ref sw); + } + } + + #endregion + } +} \ No newline at end of file