4

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)
Briofit
  • 59
  • 2
  • 1
    It seems to me this question is more suited to be asked in the [Code Review Forum](https://codereview.stackexchange.com/). Code Review is a question and answer site for peer programmer code reviews. Please read the relevant guidance related to how to properly ask questions on this site before posting your question. – itprorh66 Jan 25 '22 at 20:43
  • 4
    I said exactly as this says https://stackoverflow.com/help/on-topic . Every time i post a question i'm answered that it doesn't belong here but this is clearly a software algorithm question. and i added the current minimal example to help. How come is this bad questioned? I spend time trying to be as clear and concise i can be. – Briofit Jan 25 '22 at 21:46
  • @itprorh66 please explain how come it doesn't fit in here. – Briofit Jan 25 '22 at 21:57
  • 1
    A line sweep algorithm may help. For each bounding box in both sets, create two events, one for the left `x` value, and the other for the right `x` value. Then sort the resulting list, and iterate, keeping track of which bounding boxes are active. A bounding box is active if its left event has been seen, but the right event has not been seen. Every time you see a left event, you need check that bounding box against the active bounding boxes of the other set. – user3386109 Jan 25 '22 at 22:15
  • 1
    @user3386109 I've search about what the line sweep you said and i found this website that explains how to do so in JavaScript. https://0fps.net/2015/01/18/collision-detection-part-2/ Once i translated it and test it i will post the solution here, thanks – Briofit Jan 25 '22 at 22:56
  • 3
    a spatial index such as a quadtree (https://stackoverflow.com/questions/2298517/are-any-of-these-quad-tree-libraries-any-good) or -rtree (https://pypi.org/project/Rtree/) will probably speed things up. – Ian Turton Jan 26 '22 at 08:31
  • 1
    [Interval trees](https://en.wikipedia.org/wiki/Interval_tree) should help too. – Jérôme Richard Jan 26 '22 at 18:48
  • For anyone following this thread: I've implemented a solution with https://rtree.readthedocs.io/en/latest/. Which is a bit faster in some cases but slower in others and now I'm implementing a solution using this one http://www.pygame.org/wiki/QuadTree. Once done i will paste an analysis of performance of all the different solutions suggested here. Thanks specially @IanTurton. – Briofit Jan 27 '22 at 15:46

0 Answers0