| 1 |
Overview: |
| 2 |
|
| 3 |
An interval tree can be used to efficiently find a set of numeric |
| 4 |
intervals overlapping or containing another interval. |
| 5 |
|
| 6 |
This library provides a basic implementation of an interval tree using |
| 7 |
C++ templates, allowing the insertion of arbitrary types into the |
| 8 |
tree. |
| 9 |
|
| 10 |
|
| 11 |
Usage: |
| 12 |
|
| 13 |
Add #include "IntervalTree.h" to the source files in which you will |
| 14 |
use the interval tree. |
| 15 |
|
| 16 |
To make an IntervalTree to contain objects of class T, use: |
| 17 |
|
| 18 |
vector<Interval<T> > intervals; |
| 19 |
T a, b, c; |
| 20 |
intervals.push_back(Interval<T>(2, 10, a)); |
| 21 |
intervals.push_back(Interval<T>(3, 4, b)); |
| 22 |
intervals.push_back(Interval<T>(20, 100, c)); |
| 23 |
IntervalTree<T> tree; |
| 24 |
tree = IntervalTree<T>(intervals); |
| 25 |
|
| 26 |
Now, it's possible to query the tree and obtain a set of intervals |
| 27 |
which are contained within the start and stop coordinates. |
| 28 |
|
| 29 |
vector<Interval<T> > results; |
| 30 |
tree.findContained(start, stop, results); |
| 31 |
cout << "found " << results.size() |
| 32 |
<< " overlapping intervals" << endl; |
| 33 |
|
| 34 |
The function IntervalTree::findOverlapping provides a method to find |
| 35 |
all those intervals which are contained or partially overlap the |
| 36 |
interval (start, stop). |
| 37 |
|
| 38 |
|
| 39 |
Author: Erik Garrison <[email protected]> |
| 40 |
|
| 41 |
License: MIT |