Efficient way to find overlapping of N rectangles

Question

I am trying to find an efficient solution for finding overlapping of n rectangles where rectangles are stored in two separate lists. We are looking for all rectangles in listA that overlap with rectangles in listB (and vice versa). Comparing one element from the first list to second list could take immensely large amount of time. I am looking for an efficient solution.

I have two list of rectangles

rect = Rectangle(10, 12, 56, 15)
rect2 = Rectangle(0, 0,1, 15)
rect3 = Rectangle (10,  12, 56, 15)

listA = [rect, rect2]
listB = [rect3]

which is created from the class:

import numpy as np
import itertools as it

class  Rectangle(object):
    def __init__(self, left, right, bottom, top):
        self.left = left
        self.bottom = right
        self.right = bottom
        self.top = top

    def overlap(r1, r2):
        hoverlaps = True
        voverlaps = True
        if (r1.left > r2.right) or (r1.right < r2.left):
            hoverlaps = False
        if (r1.top < r2.bottom) or (r1.bottom > r2.top):
            voverlaps = False
        return hoverlaps and voverlaps

I need to compare rectangle in listA to listB the code goes like this which is highly inefficient - comparing one by one

for a in it.combinations(listB):
    for b in it.combinations(listA):
        if a.overlap(b):

Any better efficient method to deal with the problem?

Chalfant

Try [rect] instead. It seems to be what you want to do. – Winterfeed

list_of_rectangles = [rect, rect2]. Or list_of_rectangles = list() list_of_rectangles.append(rect) list_of_rectangles.append(rect2) on 3 separate lines. – Deoxyribose

You are expected to 1) give a forum a fair chance to answer a question (my take: 60 hours at least, 8 days welcome) 2) plant cross-references yourself. – Djokjakarta

Can rectangles in each list overlap? – Sloe

@nm yes. Each list can overlap – Chalfant

Am I correct, that you want an efficient algorithm to find all pairs of rectangles (R1, R2) where R1 is from the first list and R2 is from the second list and R1 and R2 are overlapping? – Boilermaker

@Boilermaker Yes. Thats what we are looking for – Chalfant

So the third code block should be for a in listA: for b in listB: if a.overlap(b): ... right? – Philharmonic

@Philharmonic Yeah that is also possbile – Chalfant

Rectangle.__init__ still looks weird: self.bottom = right self.right = bottom. With left, right, bottom, top, rect2 has zero width (just saying), and the other rectangles have top < bottom. (If and when you edit this, have a look at Andrew Svetlov's edit to save vertical space, and consider to follow user7138814's suggestion.) – Djokjakarta

Answer 1

First off: As with many a problem from computational geometry, specifying the parameters for order-of-growth analysis needs care: calling the lengths of the lists m and n, the worst case in just those parameters is Ω(m×n), as all areas might overlap (in this regard, the algorithm from the question is asymptotically optimal). It is usual to include the size of the output: t = f(m, n, o) (Output-sensitive algorithm).
Trivially, f ∈ Ω(m+n+o) for the problem presented.

---

Line Sweep is a paradigm to reduce geometrical problems by one dimension - in its original form, from 2D to 1D, plane to line.

Imagine all the rectangles in the plane, different colours for the lists.
 Now sweep a line across this plane - left to right, conventionally, and infinitesimally further to the right "for low y-coordinates" (handle coordinates in increasing x-order, increasing y-order for equal x).
 For all of this sweep (or scan), per colour keep one set representing the "y-intervals" of all rectangles at the current x-coordinate, starting empty. (In a data structure supporting insertion, deletion, and enumerating all intervals that overlap a query interval: see below.)
 Meeting the left side of a rectangle, add the segment to the data structure for its colour. Report overlapping intervals/rectangles in any other colour.
 At a right side, remove the segment.
 Depending on the definition of "overlapping", handle left sides before right sides - or the other way round.

---

There are many data structures supporting insertion and deletion of intervals, and finding all intervals that overlap a query interval. Currently, I think Augmented Search-Trees may be easiest to understand, implement, test, analyse…
Using this, enumerating all o intersecting pairs of axis-aligned rectangles (a, b) from listA and listB should be possible in O((m+n)log(m+n)+o) time and O(m+n) space. For sizeable problem instances, avoid data structures needing more than linear space ((original) Segment Trees, for one example pertaining to interval overlap).

---

Another paradigm in algorithm design is Divide&Conquer: with a computational geometry problem, choose one dimension in which the problem can be divided into independent parts, and a coordinate such that the sub-problems for "coordinates below" and "coordinates above" are close in expected run-time. Quite possibly, another (and different) sub-problem "including the coordinate" needs to be solved. This tends to be beneficial when a) the run-time for solving sub-problems is "super-log-linear", and b) there is a cheap (linear) way to construct the overall solution from the solutions for the sub-problems.
This lends itself to concurrent problem solving, and can be used with any other approach for sub-problems, including line sweep.

---

There will be many ways to tweak each approach, starting with disregarding input items that can't possibly contribute to the output. To "fairly" compare implementations of algorithms of like order of growth, don't aim for a fair "level of tweakedness": try to invest fair amounts of time for tweaking.

Djokjakarta

An animation of the sweep-line algorithm as applied to the problem of rectangle intersection can be found can be found here The implementation is in Javascript, should be easily portable to Python. This program finds intersections within a single list, as opposed to between two lists, but this shouldn't matter much. – Sloe

@n.m. I intended to look for something like that (seems to need scripting enabled for ocks.org & d3js.org, btw.), but including inclusion (overlap without intersecting edges) and the operation of the segment tree, too. finds intersections within a single list, as opposed to between two lists, but this shouldn't matter much Not much, then again, it is the only excuse not to flag this as a duplicate. – Djokjakarta

This method handles overlap without intersecting edges no problem. – Sloe

This=sweepline. The animation only shows line intersections but inclusion is handled naturally by the algorithm. – Sloe

Since search/insert/delete in a balanced tree is log(N), the complexity appears to be O((m+n)*log(m+n)). – Sketchy

(I remember going from O(o+(m+n)*log²(m+n)) to O(o+(m+n)*log(m+n)) to be quite an effort in the segment tree implementation. Don't have a good book, didn't find my lecture notes (from one third of a century ago), …) – Djokjakarta

Not versed in python, I rather started a code review on Find overlaps between lists of axis-aligned rectangles using line sweep. – Djokjakarta

Answer 2

A couple of potential minor efficiency improvements. First, fix your overlap() function, it potentially does calculations it needn't:

def overlap(r1, r2):

    if r1.left > r2.right or r1.right < r2.left:
        return False

    if r1.top < r2.bottom or r1.bottom > r2.top:
        return False

    return True

Second, calculate the contaning rectangle for one of the lists and use it to screen the other list -- any rectangle that doesn't overlap the container doesn't need to be tested against all the rectangles that contributed to it:

def containing_rectangle(rectangles):
    return Rectangle(min(rectangles, key=lambda r: r.left).left,
        max(rectangles, key=lambda r: r.right).right,
        min(rectangles, key=lambda r: r.bottom).bottom,
        max(rectangles, key=lambda r: r.top).top
    )

c = containing_rectangle(listA)

for b in listB:
    if b.overlap(c):
        for a in listA:
            if b.overlap(a):

In my testing with hundreds of random rectangles, this avoided comparisons on the order of single digit percentages (e.g. 2% or 3%) and occasionally increased the number of comparisons. However, presumably your data isn't random and might fare better with this type of screening.

Depending on the nature of your data, you could break this up into a container rectangle check for each batch of 10K rectangles out of 50K or what ever slice gives you maximum efficiency. Possibly presorting the rectangles (e.g. by their centers) before assigning them to container batches.

We can break up and batch both lists with container rectangles:

listAA = [listA[x:x + 10] for x in range(0, len(listA), 10)]

for i, arrays in enumerate(listAA):
    listAA[i] = [containing_rectangle(arrays)] + arrays

listBB = [listB[x:x + 10] for x in range(0, len(listB), 10)]

for i, arrays in enumerate(listBB):
    listBB[i] = [containing_rectangle(arrays)] + arrays

for bb in listBB:
    for aa in listAA:
        if bb[0].overlap(aa[0]):
            for b in bb[1:]:
                if b.overlap(aa[0]):
                    for a in aa[1:]:
                        if b.overlap(a):

With my random data, this decreased the comparisons on the order of 15% to 20%, even counting the container rectangle comparisons. The batching of rectangles above is arbitrary and you can likely do better.

Tullus

Answer 3

The exception you're getting comes from the last line of the code you show. The expression list[rect] is not valid, since list is a class, and the [] syntax in that context is trying to index it. You probably want just [rect] (which creates a new list containing the single item rect).

There are several other basic issues, with your code. For instance, your Rect.__init__ method doesn't set a left attribute, which you seem to expect in your collision testing method. You've also used different capitalization for r1 and r2 in different parts of the overlap method (Python doesn't consider r1 to be the same as R1).

Those issues don't really have anything to do with testing more than two rectangles, which your question asks about. The simplest way to do that (and I strongly advise sticking to simple algorithms if you're having basic issues like the ones mentioned above), is to simply compare each rectangle with each other rectangle using the existing pairwise test. You can use itertools.combinations to easily get all pairs of items from an iterable (like a list):

list_of_rects = [rect1, rect2, rect3, rect4] # assume these are defined elsewhere

for a, b in itertools.combinations(list_of_rects, 2):
    if a.overlap(b):
        # do whatever you want to do when two rectangles overlap here

Terrilynterrine

That means there are more efficient algorithms are there to solve that problem. Could you please suggest me those algorithms? I am sure that my solution would be extremely inefficient – Chalfant

For a relatively small number of rectangles (e.g. 10 or 20 rather than 10000), the performance of this algorithm will be fine. Don't worry about performance for bigger problems unless you are absolutely certain that you need to (e.g. because you've tried the simple algorithm and it was too slow). – Terrilynterrine

I have more than 50000 rectangles to check. I could update the code – Chalfant

Answer 4

This implementation using numpy is about 35-40 times faster according to a test I did. For 2 lists each with 10000 random rectangles this method took 2.5 secs and the method in the question took ~90 sec. In terms of complexity it's still O(N^2) like the method in the question.

import numpy as np

rects1=[
    [0,10,0,10],
    [0,100,0,100],
]

rects2=[
    [20,50,20,50],
    [200,500,200,500],
    [0,12,0,12]
]

data=np.asarray(rects2)


def find_overlaps(rect,data):
    data=data[data[::,0]<rect[1]]
    data=data[data[::,1]>rect[0]]
    data=data[data[::,2]<rect[3]]
    data=data[data[::,3]>rect[2]]
    return data


for rect in rects1:
    overlaps = find_overlaps(rect,data)
    for overlap in overlaps:
        pass#do something here

Grier

Answer 5

Obviously, if your list (at least listB) is sorted by r2.xmin, you can search for r1.xmax in listB and stop testing overlap of r1 in this listB (the rest will be to the right). This will be O(n·log(n)).

A sorted vector has faster access than a sorted list.

I'm supposing that the rectangles edges are oriented same as axis.

Also fix your overlap() function as cdlane explained.

Chart

Answer 6

If you know the upper and lower limits for coordinates, you can narrow the search by partitioning the coordinate space into squares e.g. 100x100.

• Make one "set" per coordinate square.
• Go through all squares, putting them in the "set" of any square they overlap.

See also Tiled Rendering which uses partitions to speed up graphical operations.

    // Stores rectangles which overlap (x, y)..(x+w-1, y+h-1)
    public class RectangleSet
    {
       private List<Rectangle> _overlaps;

       public RectangleSet(int x, int y, int w, int h);
    }

    // Partitions the coordinate space into squares
    public class CoordinateArea
    {
       private const int SquareSize = 100;

       public List<RectangleSet> Squares = new List<RectangleSet>();

       public CoordinateArea(int xmin, int ymin, int xmax, int ymax)
       {
          for (int x = xmin; x <= xmax; x += SquareSize)
          for (int y = ymin; y <= ymax; y += SquareSize)
          {
              Squares.Add(new RectangleSet(x, y, SquareSize, SquareSize);
          }
       }

       // Adds a list of rectangles to the coordinate space
       public void AddRectangles(IEnumerable<Rectangle> list)
       {
          foreach (Rectangle r in list)
          {
              foreach (RectangleSet set in Squares)
              {
                  if (r.Overlaps(set))
                      set.Add(r);
              }
          }
       }
    }

Now you have a much smaller set of rectangles for comparison, which should speed things up nicely.

CoordinateArea A = new CoordinateArea(-500, -500, +1000, +1000);
CoordinateArea B = new CoordinateArea(-500, -500, +1000, +1000);  // same limits for A, B

A.AddRectangles(listA);
B.AddRectangles(listB);

for (int i = 0; i < listA.Squares.Count; i++)
{
    RectangleSet setA = A[i];
    RectangleSet setB = B[i];

    // *** small number of rectangles, which you can now check thoroghly for overlaps ***

}

Nepil

Answer 7

I think you have to setup an additional data structure (spatial index) in order to have fast access to nearby rectangles that potentially overlap in order to reduce the time complexity from quadratic to linearithmic.

See also:

• https://en.wikipedia.org/wiki/Spatial_database
• Spatial Index for Rectangles With Fast Insert
• find overlapping rectangles algorithm

Boilermaker

(You don't exactly need to add an answer to add something to an answer: use the edit button.) There a set_/_static problems, and there are query_/_dynamic problems: this question stated a set problem; the links are about query problems, far as I can tell. (Query algorithms give an upper bound for set problem complexity.) – Djokjakarta

@greybeard, you are right. However, often the same data structure can be used for an efficient solution of a set problem. Instead of using it for individual queries, the same data structure often can be used for an iteration that solves the set problem. A spatial index could be used to iterate over pairs of rectangles that are candidates for overlapping. – Boilermaker

Answer 8

Here is what I use to calculate overlap areas of many candidate rectangles (with candidate_coords [[l, t, r, b], ...]) with a target one (target_coords [l, t, r, b]):

comb_tensor = np.zeros((2, candidate_coords.shape[0], 4))

comb_tensor[0, :] = target_coords
comb_tensor[1] = candidate_coords

dx = np.amin(comb_tensor[:, :, 2].T, axis=1) - np.amax(comb_tensor[:, :, 0].T, axis=1)
dy = np.amin(comb_tensor[:, :, 3].T, axis=1) - np.amax(comb_tensor[:, :, 1].T, axis=1)

dx[dx < 0] = 0
dy[dy < 0] = 0 

overlap_areas = dx * dy

This should be fairly efficient especially if there are many candidate rectangles as all is done using numpy functions operating on ndarrays. You can either do a loop calculating the overlap areas or perhaps add one more dimension to comb_tensor.

Tuchun

The OP precisely wants to avoid exhaustive comparison, is this will have a cost of order 50000². – Quadrennium

Answer 9

I think the below code will be useful.

print("Identifying Overlap between n number of rectangle")
#List to be used in set and get_coordinate_checked_list
coordinate_checked_list = []

def get_coordinate_checked_list():
    #returns the overlapping coordinates of rectangles
    """
    :return: list of overlapping coordinates
    """
    return coordinate_checked_list

def set_coordinate_checked_list(coordinates):
    #appends the overlapping coordinates of rectangles
    """
    :param coordinates: list of overlapping coordinates to be appended in coordinate_checked_list
    :return:
    """
    coordinate_checked_list.append(coordinates)

def overlap_checked_for(coordinates):
    # to find rectangle overlap is already checked, if checked "True" will be returned else coordinates will be added
    # to coordinate_checked_list and return "False"
    """
    :param coordinates: coordinates of two rectangles
    :return: True if already checked, else False
    """
    if coordinates in get_coordinate_checked_list():
        return True
    else:
        set_coordinate_checked_list(coordinates)
        return False

def __isRectangleOverlap(R1, R2):
    #checks if two rectangles overlap
    """
    :param R1: Rectangle1 with cordinates [x0,y0,x1,y1]
    :param R2: Rectangle1 with cordinates [x0,y0,x1,y1]
    :return: True if rectangles overlaps else False
    """
    if (R1[0] >= R2[2]) or (R1[2] <= R2[0]) or (R1[3] <= R2[1]) or (R1[1] >= R2[3]):
        return False
    else:
        print("Rectangle1 {} overlaps with Rectangle2 {}".format(R1,R2))
        return True


def __splitByHeightandWidth(rectangles):
    # Gets the list of rectangle, divide the paged with respect to height and width and position
    # the rectangle in suitable section say left_up,left_down,right_up,right_down and returns the list of rectangle
    # grouped with respect to section

    """
    :param rectangles: list of rectangle coordinates each designed as designed as [x0,y0,x1,y1]
    :return:list of rectangle grouped with respect to section, suspect list which holds the rectangles
            positioned in more than one section
    """

    lu_Rect = []
    ll_Rect = []
    ru_Rect = []
    rl_Rect = []
    sus_list = []
    min_h = 0
    max_h = 0
    min_w = 0
    max_w = 0
    value_assigned = False
    for rectangle in rectangles:
        if not value_assigned:
            min_h = rectangle[1]
            max_h = rectangle[3]
            min_w = rectangle[0]
            max_w = rectangle[2]
        value_assigned = True
        if rectangle[1] < min_h:
            min_h = rectangle[1]
        if rectangle[3] > max_h:
            max_h = rectangle[3]
        if rectangle[0] < min_w:
            min_w = rectangle[0]
        if rectangle[2] > max_w:
            max_w = rectangle[2]

    for rectangle in rectangles:
        if rectangle[3] <= (max_h - min_h) / 2:
            if rectangle[2] <= (max_w - min_w) / 2:
                ll_Rect.append(rectangle)
            elif rectangle[0] >= (max_w - min_w) / 2:
                rl_Rect.append(rectangle)
            else:
                # if rectangle[0] < (max_w - min_w) / 2 and rectangle[2] > (max_w - min_w) / 2:
                ll_Rect.append(rectangle)
                rl_Rect.append(rectangle)
                sus_list.append(rectangle)
        if rectangle[1] >= (max_h - min_h) / 2:
            if rectangle[2] <= (max_w - min_w) / 2:
                lu_Rect.append(rectangle)
            elif rectangle[0] >= (max_w - min_w) / 2:
                ru_Rect.append(rectangle)
            else:
                # if rectangle[0] < (max_w - min_w) / 2 and rectangle[2] > (max_w - min_w) / 2:
                lu_Rect.append(rectangle)
                ru_Rect.append(rectangle)
                sus_list.append(rectangle)
        if rectangle[1] < (max_h - min_h) / 2 and rectangle[3] > (max_h - min_h) / 2:
            if rectangle[0] < (max_w - min_w) / 2 and rectangle[2] > (max_w - min_w) / 2:
                lu_Rect.append(rectangle)
                ll_Rect.append(rectangle)
                ru_Rect.append(rectangle)
                rl_Rect.append(rectangle)
                sus_list.append(rectangle)
            elif rectangle[2] <= (max_w - min_w) / 2:
                lu_Rect.append(rectangle)
                ll_Rect.append(rectangle)
                sus_list.append(rectangle)
            else:
                # if rectangle[0] >= (max_w - min_w) / 2:
                ru_Rect.append(rectangle)
                rl_Rect.append(rectangle)
                sus_list.append(rectangle)
    return [lu_Rect, ll_Rect, ru_Rect, rl_Rect], sus_list

def find_overlap(rectangles):
    #Find all possible overlap between the list of rectangles
    """
    :param rectangles: list of rectangle grouped with respect to section
    :return:
    """
    split_Rectangles , sus_list = __splitByHeightandWidth(rectangles)
    for section in split_Rectangles:
        for rect in range(len(section)-1):
            for i in range(len(section)-1):
                if section[0] and section[i+1] in sus_list:
                    if not overlap_checked_for([section[0],section[i+1]]):
                        __isRectangleOverlap(section[0],section[i+1])
                else:
                    __isRectangleOverlap(section[0],section[i+1])
            section.pop(0)

arr =[[0,0,2,2],[0,0,2,7],[0,2,10,3],[3,0,4,1],[6,1,8,8],[0,7,2,8],[4,5,5,6],[4,6,10,7],[9,3,10,5],[5,3,6,4],[4,3,6,5],[4,3,5`enter code here`,6]]
find_overlap(arr)

Loathing

Answer 10

For a simple solution that improves on pure brute force if the rectangles are relatively sparse:

• sort all Y ordinates in a single list, and for every ordinate store the index of the rectangle, the originating list and a flag to distinguish bottom and top;

• scan the list from bottom to top, maintaining two "active lists", one per rectangle set;

  • when you meet a bottom, insert the rectangle index in its active list and compare to all rectangles in the other list to detect overlaps on X;

  • when you meet a top, remove the rectangle index from its active list.

Assuming simple linear lists, the updates and searches will take time linear in the size of the active lists. So instead of M x N comparisons, you will perform M x n + m x N comparisons, where m and n denote the average list sizes. (If the rectangles do not overlap within their set, one can expect an average list length not exceeding √M and √N.)

Quadrennium

Answer 11

I had the same problem, and I came up with this solution. The function does the calculation in about 11 seconds (Intel i5 - 50,000 random rectangles). It uses numexpr instead of numpy which is about 5 times faster, and creates temporary lookup dicts.

import pandas as pd
import numpy as np
import numexpr


def find_rectangle_intersections(
    df: pd.DataFrame,
    columns: tuple | list = ("start_x", "start_y", "end_x", "end_y"),
    new_column: str | int | float = "aa_intersecting",
    dtype: np.float32 | np.float64 | np.int32 | np.int64 = np.int32,
    convert_to_tuples: bool = False,
) -> pd.DataFrame:
    """
    Finds rectangle intersections in a DataFrame and populates a new column with results.
    The function utilizes NumExpr for calculations, which can significantly improve
    performance when dealing with large datasets of rectangles

    Args:
        df (pd.DataFrame): Input DataFrame containing rectangle coordinates.
        columns (tuple or list, optional): Names of columns containing rectangle coordinates
            (start_x, start_y, end_x, end_y). Defaults to ("start_x", "start_y", "end_x", "end_y").
        new_column (str, int, float, optional): Name of the new column to store intersection results.
            Defaults to "aa_intersecting".
        dtype (np.float32 | np.float64 | np.int32 | np.int64, optional): Data type for calculations. Defaults to np.int32.
        convert_to_tuples (bool, optional): If True, converts intersection results to tuples.
            Defaults to False.

    Returns:
        pd.DataFrame: Input DataFrame with the new_column populated with intersection results.

    Example:
        import time
        import pandas as pd
        import numpy as np
        min_x = 1
        max_x = 100
        min_y = 1
        max_y = 100
        size = 50000
        min_width = 1
        max_width = 1000
        min_height = 1
        max_height = 1000
        df = pd.DataFrame(
            [
                (startx := np.random.randint(min_x, max_x, size=size)),
                (starty := np.random.randint(min_y, max_y, size=size)),
                startx + np.random.randint(min_width, max_width, size=size),
                starty + np.random.randint(min_height, max_height, size=size),
            ]
        ).T.rename(columns={0: "start_x", 1: "start_y", 2: "end_x", 3: "end_y"})
        start = time.perf_counter()
        df = find_rectangle_intersections(
            df,
            columns=("start_x", "start_y", "end_x", "end_y"),
            new_column="aa_intersecting",
            dtype=np.int32,
            convert_to_tuples=False,
        )
        print(time.perf_counter() - start)


    """

    def find_overlaps(rect):
        numexpr.evaluate(
            "y1 | y2 | y3 | y4",
            global_dict={},
            local_dict={
                "y1": data2smaller[rect[0]],
                "y2": data0bigger[rect[2]],
                "y3": data1bigger[rect[3]],
                "y4": data3smaller[rect[1]],
            },
            out=tmparray,
            casting="no",
        )
        subresult = datatuples[np.where(tmparray)]
        if convert_to_tuples:
            return tuple(subresult)
        else:
            return subresult

    datadf = df[[*columns]].astype(dtype)
    data = datadf.__array__()
    if convert_to_tuples:
        datatuples = np.fromiter(map(tuple, data), dtype="object")
    else:
        datatuples = data

    box2_0 = datadf[columns[0]].unique().__array__()
    box2_1 = datadf[columns[1]].unique().__array__()
    box2_2 = datadf[columns[2]].unique().__array__()
    box2_3 = datadf[columns[3]].unique().__array__()

    box1_0 = datadf[columns[0]].__array__()
    box1_1 = datadf[columns[1]].__array__()
    box1_2 = datadf[columns[2]].__array__()
    box1_3 = datadf[columns[3]].__array__()
    tmparray = np.zeros_like(box1_0).astype(bool)

    data2smaller = {
        k: numexpr.evaluate(
            f"(box1_2 < {k})",
            global_dict={},
            local_dict={"box1_2": box1_2},
        )
        for k in box2_0
    }
    data0bigger = {
        k: numexpr.evaluate(
            f"(box1_0 > {k})",
            global_dict={},
            local_dict={"box1_0": box1_0},
        )
        for k in box2_2
    }
    data1bigger = {
        k: numexpr.evaluate(
            f"(box1_1 > {k})",
            global_dict={},
            local_dict={"box1_1": box1_1},
        )
        for k in box2_3
    }
    data3smaller = {
        k: numexpr.evaluate(
            f"(box1_3 < {k})",
            global_dict={},
            local_dict={"box1_3": box1_3},
        )
        for k in box2_1
    }
    df.loc[:, new_column] = df.apply(
        lambda x: find_overlaps(
            (x[columns[0]], x[columns[1]], x[columns[2]], x[columns[3]]),
        ),
        axis=1,
    )
    return df

Mongoose