Overlap fraction between two numeric ranges

Question

I want to compute the overlap fraction of two numeric ranges. Let me illustrate my question with an example since I believe that it will be easier to understand.

Lets say that I have two numeric ranges:

A = [1,100]
B = [25,100]

What I want to know (and code) is how much is B overlapping A and viceversa (how much is A overlapping B)

In this case, A overlaps B (as a fraction of B) by 100% and B overlaps A (as a fraction of A) by 75% percent.

I have try been trying to code this in python, but I am struggling and I can't find the proper solution for computing both fractions

What I have been able to achieve so far is the following:

Given the start and end of both numeric ranges, I have been able to figure out if the two numerical ranges overlap (from other stackoverflow post)

I have done this with the following code

def is_overlapping(x1,x2,y1,y2):
    return max(x1,y1) <= min(x2,y2)

thanks!

Now you can subtract max(x1,y1) from min(x2,y2) and divide by the length of the range, isn't it? — koPytok, May 24 '18 at 12:43
B = [25,100] are boundaries inculded? If so then it must be [26, 100]. — Sumit Jha, May 24 '18 at 13:06

AndrejH · Accepted Answer · 2018-05-24T13:18:13.210

2

Here's a fast solution without for loops:

def overlapping(x1,x2,y1,y2):
    #A = [x1,x2]
    #B = [y1,y1]

    # Compute the B over A
    if(x1 <= y1 and x2 >= y2): # Total overlapping      
        return 1
    elif(x2 < y1 or y2 < x1):
        return 0
    elif(x2 == y1 or x1 == y2):
        return 1/float(y2 - y1 + 1)
    return (min(x2,y2) - max(x1,y1))/float(y2 - y1)

edited May 24 '18 at 13:18

answered May 24 '18 at 12:53

AndrejH

2,028
1
11
23

score 2 · Answer 2 · answered May 24 '18 at 12:58

One (less efficient) way to do this is by using sets. If you set up ranges

A = range(1,101)
B = range(25, 101)

then you can find your fractions as follows:

len(set(A)&set(B))/float(len(set(B)))

and

len(set(A)&set(B))/float(len(set(A)))

giving 1.0 and 0.76. There are 76 points in B that are also in A (since your ranges appear to be inclusive).

There are more efficient ways to do this using some mathematics as the other answers show, but this is general purpose.

score 0 · Answer 3 · answered May 24 '18 at 12:48

I believe there are countless ways of solving this problem. The first one that came into my mind is making best use of the sum function which can also sum up over an iterable:

a = range(1,100)
b = range(25,100)

sum_a = sum(1 for i in b if i in a)
sum_b = sum(1 for i in a if i in b)

share_a = sum_a*100 / len(b)
share_b = sum_b*100 / len(a)

print(share_a, share_b)
>>> 100  75

This might be a bit more robus, e.g. when you are not working with ranges but with unsorted lists.

score 0 · Answer 4 · answered May 24 '18 at 13:04

Here's my solution using numpy & python3

import numpy as np
def my_example(A,B):

    # Convert to numpy arrays
    A = np.array(A)
    B = np.array(B)

    # determine which elements are overlapping
    overlapping_elements=np.intersect1d(A, B)

    # determine how many there are
    coe=overlapping_elements.size

    #return the ratios 
    return coe/A.size , coe/B.size

# Generate two test lists
a=[*range(1,101)]    
b=[*range(25,101)]

# Call the example & print the results
x,y = my_example(a,b) # returns ratios, multiply by 100 for percentage
print(x,y)

Sumit Jha · Answer 5 · 2018-05-24T13:38:38.333

I have assumed both lower and upper bounds are included in the range. Here is my way of calculating overlapping distance with respect to other:

def is_valid(x):
    try:
        valid = (len(x) == 2) and (x[0] <= x[1])
    except:
        valid = False
    finally:
        return valid


def is_overlapping(x,y):
    return max(x[0],y[0]) <=  min(x[1],y[1])

def overlapping_percent(x,y):
    if(is_valid(x) and is_valid(y)) == False:
        raise ValueError("Invalid range")

    if is_overlapping(x,y):
        overlapping_distance =  min(x[1],y[1]) - max(x[0],y[0]) +  1
        width_x = x[1] - x[0] + 1
        width_y = y[1] - y[0] + 1
        overlap_x = overlapping_distance * 100.0/width_y
        overlap_y = overlapping_distance *100.0/width_x
        return (overlap_x, overlap_y)
    return (0,0);


if __name__ == '__main__':       
    try:
        print(overlapping_percent((1,100),(26,100)))
        print(overlapping_percent((26,100),(1,100)))
        print(overlapping_percent((26,50),(1,100)))
        print(overlapping_percent((1,100),(26,50)))
        print(overlapping_percent((1,100),(200,300)))
        print(overlapping_percent((26,150),(1,100)))
        print(overlapping_percent((126,50),(1,100)))
    except Exception as e:
        print(e)

Output:

(100.0, 75.0)
(75.0, 100.0)
(25.0, 100.0)
(100.0, 25.0)
(0, 0)
(60.0, 75.0)
Invalid range

I hope it helps.

Overlap fraction between two numeric ranges

5 Answers5