Overlapping 1D grids

Question

I have two 1D grids, each of them is a finite collection of cells, where the cell is defined by the left end and the right end, $[cell]_{i}$=$[x_{i}^{left}$,$x_{i}^{right}$]. I need to find the overlap of these grids, i.e., what cell of grid #1 overlaps with what cell of grid #2, and what is the overlapping area (length).

This must be a very standard problem, and probably there is a standard algorithm for it. Is it implemented in a standard library, preferably in Python?

Below I am including a Python script that solves this problem in a simple way, checking every pair of grid cells. The code can print grids used, if keyword is set show=True in test_grid_overlap()

# Usage (in Python)
# > exec(open("grid_overlap.py").read())
# > test_grid_overlap()
#==============================================#

import numpy as np
import time



def overlap(min1, max1, min2, max2):
    #-find overlap of two segments
    return max(0, min(max1, max2) - max(min1, min2))

def grid_overlap(grid1, grid2):
    #-calculate overlap between cells of two 1D grids
    ngrid1=len(grid1[0,:])
    ngrid2=len(grid2[0,:])

    ovlap=np.zeros([ngrid1,ngrid2])
    
    for i in range(0,ngrid1):
        for j in range(0,ngrid2):
            ovlap[i,j] = overlap(grid1[0,i], grid1[1,i], grid2[0,j], grid2[1,j])

    return ovlap

def make_1D_grid(ngrid):
    #-generate a 1D grid as a 2D array combining left and right boundaries of cells
    
    #generate a random monotonic sequence
    arr = np.sort(np.random.rand(ngrid+1))
    left = arr[0:ngrid]
    right = arr[1:ngrid+1]

    #-combine two 1D arrays (left,right) in a 2D array
    grid=np.concatenate([[left],[right]])
    
    return grid

def test_grid_overlap(n1=5, n2=3, show=False):
    #-see how it all works

    grid1 = make_1D_grid(n1)
    grid2 = make_1D_grid(n2)


    start=time.time()
    res = grid_overlap(grid1, grid2)
    end=time.time()    
    print ("Time elapsed:", end - start)

    
    
    if show:
        print("grid1:")
        print(grid1)

        print("grid2:")
        print(grid2)

        print("overlap:")
        print(res)

Answer 1

Assuming that the arrays are passed already sorted (which is a reasonable assumption since you are starting from two 1D grids), I have a solution which is $\mathcal{O}(n+m)$ where $n$ and $m$ are the respective sizes of the arrays. I wrote the code in MATLAB/Octave, but should be easy to translate to Python.

% Compare two arrays for overlaps
% Test 1 - Easy
%arr1 = [0 1 2 3 4];
%arr2 = [0 1.5 3.2 5];

% Test 2 - Harder (broke the first version of the code)
arr1 = -10:10;
arr2 = [0 1.5 3.2 5];

ptr = 1; curr = ptr;
for i=1:length(arr1)-1
    while ptr<length(arr2)
        begin1 = arr1(i); end1 = arr1(i+1);
        begin2 = arr2(ptr); end2 = arr2(ptr+1);
    
        if (begin2<=end1)
            fprintf("Overlap found between %d-th interval of first set and %d-th interval of the second set\n",i,ptr);
            fprintf("Overlap length: %g\n", abs(min(end2,end1)-max(begin2,begin1)))
            curr = ptr;
            ptr = ptr + 1;
        else
            break
        end
    end
    if (end2>end1)
        ptr=max(ptr-1,curr);
    end
end

Edit: 1 "if" condition was misplaced and introduced a bug. I think it works fine now. Testing may be necessary.

Edit 2: Added curr variable to prevent out-of-bound access issues caused by Test 2.

# Python Code
import numpy as np
import time


def overlap(min1, max1, min2, max2):
    #-find overlap of two segments
    return max(0, min(max1, max2) - max(min1, min2))

def grid_overlap(grid1, grid2):
    #-calculate overlap between cells of two 1D grids
    ngrid1=len(grid1[0,:])
    ngrid2=len(grid2[0,:])

    ovlap=np.zeros([ngrid1,ngrid2])
    
    for i in range(0,ngrid1):
        for j in range(0,ngrid2):
            ovlap[i,j] = overlap(grid1[0,i], grid1[1,i], grid2[0,j], grid2[1,j])

    return ovlap
    
def grid_overlap_linear(grid1, grid2):
    ngrid1=len(grid1[0,:])
    ngrid2=len(grid2[0,:])
    
    ovlap=np.zeros([ngrid1,ngrid2])
    
    ptr = 0
    curr = 0
    
    for i in range(0,ngrid1):
        while ptr<ngrid2:
            if grid2[0,ptr] <= grid1[1,i]:
                ovlap[i,ptr] = overlap(grid1[0,i],grid1[1,i],grid2[0,ptr],grid2[1,ptr])
                
                curr = ptr
                ptr = ptr + 1
            else:
                break
        if grid2[1,ptr-1]>grid1[1,i]:
            ptr = np.max([ptr-1,curr])
            
    return ovlap


def make_1D_grid(ngrid):
    #-generate a 1D grid as a 2D array combining left and right boundaries of cells
    
    #generate a random monotonic sequence
    arr = np.sort(np.random.rand(ngrid+1))
    left = arr[0:ngrid]
    right = arr[1:ngrid+1]

    #-combine two 1D arrays (left,right) in a 2D array
    grid=np.concatenate([[left],[right]])
    
    return grid

def test_grid_overlap(n1=5, n2=3, show=False):
    #-see how it all works

    grid1 = make_1D_grid(n1)
    grid2 = make_1D_grid(n2)


    start=time.time()
    res = grid_overlap(grid1, grid2)
    end=time.time()    
    print ("Time elapsed:", end - start)
    
    start=time.time()
    res2 = grid_overlap_linear(grid1, grid2)
    end=time.time()    
    print ("Time elapsed:", end - start)

    
    
    if show:
        print("grid1:")
        print(grid1)

        print("grid2:")
        print(grid2)

        print("overlap:")
        print(res)

        print("overlap2:")
        print(res2)
        
        print(np.linalg.norm(res-res2))
        
        
test_grid_overlap(n1=50, n2=30, show=True)

Edit 3: Added a Python version based on Maxim Umansky's code. Compares the outputs to check if the algorithm I suggested agrees with the simple algorithm, and also checks complexity naively by measuring time spent. For small inputs (n1=5, n2=3), the simple algorithm outperforms. But the optimized algorithm seems to be $\mathcal{O}(n+m)$. The output matrices res and res2 matched in 10 random tests ($\| res-res2\| = 0$).