1
$\begingroup$

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)
$\endgroup$
7
  • 1
    $\begingroup$ This is actually fairly similar to a common coding interview problem. Here is a description of the problem and the solution: geeksforgeeks.org/… . I don't know if it is implemented professionally anywhere. $\endgroup$ May 28 at 3:37
  • $\begingroup$ Don't you just have to compute the overlap of two intervals? The overlap is either empty or is an interval itself, and there are only four cases to consider when computing the overlap, based on the relative positions of the left and right end points. It seems hardly necessary to resort to some external library for this -- unless I misunderstand what your goal is. $\endgroup$ May 28 at 3:50
  • $\begingroup$ @Wolfgang Bangerth I would argue that with two segments one can distinguish six different cases rather than four; but also from the link provided by Abdullah Ali Sivas it looks like for arrays of segments there are different ways to do it, some more efficient than others. $\endgroup$ May 28 at 4:17
  • $\begingroup$ @MaximUmansky, can you provide a small example dataset so that I can test my code, please? $\endgroup$ May 28 at 15:55
  • $\begingroup$ @Abdullah Ali Sivas I have included a Python script that produces datasets that the code can be tested on. So far I implemented there the straightforward algorithm checking every pair of cells; but what you propose looks interesting and should be tried too. $\endgroup$ May 28 at 19:42
2
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.