Python: Algorithm for fast boundings box collision between two large sets of m and n rectangles

AABB: Axis Aligned Bounding Box

ALGORITHM:

Compare m number of AABB to n number of AABB to find if there is a collision between m and n sets.

PROBLEM:

Slow implementation for large number of rectangles (m>1000)(n>100000)

POSSIBLE SOLUTION/QUESTION

Is there any algorithm such that bounding boxes are joined together? / A type of data structure to store n AABB so that with a query of an AABB it can tell if there is intersection/collision with another AABB in the data structure. Any libraries welcome as they will probably be better than anything i can do.

CURRENT INEFFICIENT SOLUTION:

(>200 s of runtime for m = 1000, n= 100000)

import time
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd



if __name__ == '__main__':

    # TEST PATHs
    radius = 380
    n = 100
    angle = np.linspace(-np.pi, np.pi, n)
    angle2 = np.linspace(0, 10*np.pi, n)
    x = (radius + 30*np.sin(angle2))* np.sin(angle)+np.random.normal(0, 1, len(angle))
    y = (radius + 30*np.sin(angle2)) * np.cos(angle)+np.random.normal(0, 1, len(angle))
    N_df = pd.DataFrame(np.vstack((x, y)).T,columns=['X', 'Y'])

    radius = 400
    m= 10000
    angle = np.linspace(0, np.pi, m)
    x = (radius * np.sin(angle) + np.random.normal(0, 0.1, len(angle)))
    y = radius * np.cos(angle) + np.random.normal(0, 0.1, len(angle))
    M_df = pd.DataFrame(np.vstack((x, y)).T,columns=['X', 'Y'])


    N_segments_df = N_df.copy(deep=True)
    N_segments_df[['X2','Y2']] =  N_df[['X','Y']].shift(-1)
    N_segments_df = N_segments_df[:-1]

    # Create AABB for N segments
    N_segments_df['left'] = N_segments_df[['X', 'X2']].min(axis=1)
    N_segments_df['right'] = N_segments_df[['X', 'X2']].max(axis=1)
    N_segments_df['top'] = N_segments_df[['Y', 'Y2']].max(axis=1)
    N_segments_df['bottom'] = N_segments_df[['Y', 'Y2']].min(axis=1)

    M_segments_df = M_df.copy(deep=True)
    M_segments_df[['X2','Y2']] =  M_segments_df[['X','Y']].shift(-1)
    M_segments_df = M_segments_df[:-1]

    # Create AABB for M segments
    M_segments_df['left'] = M_segments_df[['X', 'X2']].min(axis=1)
    M_segments_df['right'] = M_segments_df[['X', 'X2']].max(axis=1)
    M_segments_df['top'] = M_segments_df[['Y', 'Y2']].max(axis=1)
    M_segments_df['bottom'] = M_segments_df[['Y', 'Y2']].min(axis=1)


    #SLOW PART
    start_time = time.time()
    N_segments_df['CollisionBounded'] = [
            (np.invert((l > M_segments_df['right']) | (r < M_segments_df[
                'left']) | (t < M_segments_df['bottom']) | (
                        b > M_segments_df['top'])))for l,r,t,b in zip(M_segments_df['left'],M_segments_df['right'],M_segments_df['top'],M_segments_df['bottom'])]

    print("--- %s seconds ---" % (time.time() - start_time))

    plt.plot(N_df['X'],N_df['Y'],'*')
    plt.plot(M_df['X'],M_df['Y'],'+')

Result of the current algorithm:(N_segments_df['CollisionBounded'] variable)

m rows
   | [True, True, False, ..... False] (n elements)
   | [False, True, False, ..... False] (n elements)
   | [False, True, False, ..... True] (n elements)
   | [False, False, False, ..... False] (n elements)