Skip to content

Instantly share code, notes, and snippets.

@EtsuNDmA
Created February 7, 2018 12:15
Show Gist options
  • Save EtsuNDmA/0b662be824c8fb1bb171017c1f33a9fc to your computer and use it in GitHub Desktop.
Save EtsuNDmA/0b662be824c8fb1bb171017c1f33a9fc to your computer and use it in GitHub Desktop.
import numpy as np
from itertools import chain
intervals_a=[(0, 3), (5, 8), (11, 12), (14, 15)]
intervals_b=[(1, 2), (4, 6), (7, 9), (10, 13), (14, 15)]
def intersect_intervals(intervals_a, intervals_b):
# Create events like
# [[<point_a_0>, <open_a>, <miss_b>], [<point_a_1>, <close_a>, <miss_b>], ...]
# and [[<point_b_0>, <miss_a>, <open_b>], [<point_b_1>, <miss_a>, <close_b>], ...]
events_a = np.array([list(chain(*intervals_a)), [1, -1]*len(intervals_a), [0, 0]*len(intervals_a)]).T
events_b = np.array([list(chain(*intervals_b)), [0, 0]*len(intervals_b), [1, -1]*len(intervals_b)]).T
# Merge events
events = np.concatenate([events_a, events_b],axis=0)
# Sort events by point
events = events[events[:,0].argsort()]
# Compute state for a and b, and generate interval if both opened
states = np.zeros([2,2])
for i, event in enumerate(events[:, 1:], start=1):
states[0,:], states[1,:] = states[1,:], states[1,:] + event
if np.all(states[1,:]) and events[i-1, 0] != events[i, 0]:
yield events[i-1, 0], events[i, 0]
list(intersect_intervals(intervals_a, intervals_b))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment