a.smiet a.smiet - 3 years ago 57
Python Question

Get intersection range of two non-discrete intervals

Given an interval defined by a start and end point (both floats), I would like to determine the intersection range with a second interval. For example:

int1 = [2. , 5.]
int2 = [2.2, 7.]

>>> desired_function(int1, int2)
2.8


It should handle all intersection possibilities (no intersection, partial intersection, complete intersection, also negative ranges etc.). My attempt looks like this:

def intersection(int1, int2):

#case 1: partial intersection over the left or right border
if (int2[0]<=int1[0] and int2[1]<=int1[1]) or (int2[0]>=int1[0] and int2[1]>=int1[1]):
return min(int1[1],int2[1]) - max(int1[0],int2[0])

#case 2: complete overlap of one interval by the other
elif (int2[0]>=int1[0] and int2[1]<=int1[1]) or (int2[0]<=int1[0] and int2[1]>=int1[1]):
return min (int2[1]-int2[0] , int1[1]-int1[0])

#case 3: no overlap at all
else:
return 0


Question: Have I missed something and is there any build-in solution or package that does something similar since want to keep my code as simple and fast as possible?

Answer Source

You are making things too complicated, a simple function to do this is:

def interval_intersect(a,b):
    a0,a1 = a
    b0,b1 = b
    return max(0,min(a1,b1)-max(a0,b0))

We simply calculate the maximum of the start of the two intervals and the minimum of the end between these intervals. We then calculate the difference and use max(0,...) to make sure that if there is no interval, we will return 0.

We can generalize the function further into:

from operator import itemgetter

def interval_intersect(*args):
    return max(0,min(map(itemgetter(1),args))-max(map(itemgetter(0),args)))

to let it work with an arbitrary number of intervals. These both give:

>>> interval_intersect((2,5),(2.2,7))
2.8
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download