Monday, July 1, 2013

C# QuadTreeLib example for indexing and querying point items

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;
}

No comments: