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

//Declare and initialize the PointQuadTree for storing PointItem classes
private PointQuadTree<PointItem> quadTree = null;
static void Main(string[] args)


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())
LASPoint lasPnt = reader.GetPoint().Copy();
PointItem p = new PointItem(lasPnt.X, lasPnt.Y, counter);
//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];
return candidates;

No comments:

Related Posts with Thumbnails