IntervalTree

class typhon.trees.IntervalTree(intervals)

Tree to implement fast 1-dimensional interval searches.

Based on the description in Wikipedia (https://en.wikipedia.org/wiki/Interval_tree#Centered_interval_tree) and the GitHub repository by tylerkahn (https://github.com/tylerkahn/intervaltree-python).

Examples

Check 1000 intervals on 1000 other intervals:

import numpy as np
from typhon.trees import IntervalTree

intervals = np.asarray([np.arange(1000)-0.5, np.arange(1000)+0.5]).T
tree = IntervalTree(intervals)
query_intervals = [[i-1, i+1] for i in range(1000)]
results = tree.query(query_intervals)

__init__(intervals)

Creates an IntervalTree object.

Parameters

intervals – A list or numpy.array containing the intervals (list of two numbers).

Methods

__init__(intervals)	Creates an IntervalTree object.
interval_contains(interval, point)	Checks whether a point lies in a interval.
interval_overlaps(interval1, interval2)	Checks whether two intervals overlap each other.
query(intervals)	Find all overlaps between this tree and a list of intervals.
query_points(points)	Find all intervals of this tree which contain one of those points.