In GIS, quad trees are usually used for spatial indexing of geographical features. I found this great
C# QuadTree Implementation (QuadTreeLib) library project at
http://blog.bluetoque.ca/products/quadtree/. The library project comes with an example of indexing rectangles but not for points. So I thought of posting a simple example for points. In this example, the points in a LiDAR LAS file is read and spatially indexed using this library.
//include these name spaces
using System.Drawing;
using QuadTreeLib;
//Implement the QuadTreeLib's IHasPoint interface as my own class e.g. PointItem.
class PointItem : QuadTreeLib.IHasPoint
{
private PointF _point;
private uint _seq;
public PointF Point
{
get { return _point; }
}
public uint Seq
{
get { return _seq; }
}
public PointItem(double x, double y,uint seq)
{
PointF p = new PointF((float)x, (float)y);
_point = p;
_seq = seq;
}
}
//...etc...
//Declare and initialize the PointQuadTree for storing PointItem classes
private PointQuadTree<PointItem> quadTree = null;
static void Main(string[] args)
{
//...etc...
LASReader reader = new LASReader(@"C:\Temp\myfile.las");
LASHeader header = reader.GetHeader().Copy();
//Create a rectangle encompassing the dataset bounds
System.Drawing.RectangleF lasRect = new System.Drawing.RectangleF((float)header.GetMinX(), (float)header.GetMinY(), (float)(header.GetMaxX()-header.GetMinX()),(float)(header.GetMaxY()-header.GetMinY()));
//Create the PointQuadTree class
quadTree = new PointQuadTree<PointItem>(lasRect);
//Populate the quad tree with the points from the LiDAR file
uint counter = 0;
while (reader.GetNextPoint())
{
counter++;
LASPoint lasPnt = reader.GetPoint().Copy();
PointItem p = new PointItem(lasPnt.X, lasPnt.Y, counter);
quadTree.Insert(p);
lasPnt.Dispose();
}
header.Dispose();
reader.Dispose();
//Define a query window bounds
double xlo = 0;
double xhi = 100000;
double ylo = 0;
double yhi = 200000;
//Query the quad tree and get the points within the window
ArrayList candidates = GetCandidates(xlo, ylo, xhi, yhi);
}
public ArrayList GetCandidates(double xlo, double ylo, double xhi, double yhi)
{
ArrayList candidates = new ArrayList();
RectangleF window = new RectangleF((float)xlo, (float)ylo, (float) (xhi - xlo), (float) (yhi - ylo));
//Call the PointQuadTree's Query method to find all the points within the window
List<PointItem> list = quadTree.Query(window);
for (int i = 0; i < list.Count; i++)
{
PointItem p = (PointItem) list[i];
candidates.Add(p.Seq);
}
return candidates;
}
