What is NGL
NGL (Neighborhood Graph Library) is a lightweight library written in C++
that supports a variety of geometric neighborhood graphs
in arbitrary dimensions.
Neighborhood graphs include:
- Relative neighbor graph
- Gabriel graph
- beta-Skeleton
News
- (20 October 2012) NGL released
Getting NGL
The latest version of NGL can be downloaded from here:
Check out also the google project page for code updates and latest versions:
http://code.google.com/p/ngl/
Documentation
More information on experimental results in using neighborhood graphs for analysis and clustering of multi-dimensional data
can be found in the following papers:
Carlos D. Correa and Peter Lindstorm,
"Locally-Scaled Spectral Clustering using Empty Region Graphs".
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2012
[ PDF ]
Carlos D. Correa and Peter Lindstorm,
"Towards Robust Topology of Sparsely Sampled Data".
EEE Transactions on Visualization and Computer Graphics (Proceedings Visualization / Information Visualization 2011), vol. 17, no. 12, Dec. 2011.
[ PDF ]
Example
The following is an example on how to use NGL. For the full code, refer to the example in binsrc/getNeighborGraph.cpp
#include "ngl.h"
int dims = 3;
Geometry::init(dims); // Initialize NGL for 3-dimensional points
float *pts;
int n;
//
// Allocate memory and populate pts with n 3-dimensional points
//
ANNPointSet P(pts, n); // Initialize Point set using ANN (computes a kd-tree)
NGLParams params;
params.iparam0 = KMAX; // Initialize parameters
// Only computes Gabriel graph from the KMAX nearest
// neighbor graph, computed using ANN
IndexType *indices;
int numEdges;
ngl::getGabrielGraph(P, &indices, numEdges, params); // Get graph
// Iterate over indices to output neighbor pairs
for(int i=0;i<numEdges;i++)
{
fprintf(stdout, "%d %d\n", indices[2*i], indices[2*i+1]);
}
Conditions of use
NGL is distributed under the terms of the BSD License.
If you use this library in scientific work, we kindly ask you that you cite the following reference:
Citation
Carlos D. Correa and Peter Lindstorm,
"Towards Robust Topology of Sparsely Sampled Data".
IEEE Transactions on Visualization and Computer Graphics 17, 12 (December 2011), 1852-1861.
Bibtex
@article{Correa:2011,
author = {Correa, Carlos and Lindstrom, Peter},
title = {Towards Robust Topology of Sparsely Sampled Data},
journal = {IEEE Transactions on Visualization and Computer Graphics},
issue_date = {December 2011},
volume = {17},
number = {12},
month = dec,
year = {2011},
issn = {1077-2626},
pages = {1852--1861},
numpages = {10},
doi = {10.1109/TVCG.2011.245},
}
Questions
email :