IntervalTree

class typhon.trees.IntervalTree(intervals)[source]

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)[source]

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.