So as a part of an assignment i was given , i had to basically plot rectangles in a given space probably like a predefined space in python only .
The rectangles are given in format like {rbx , rby , tlx , tly , id} rb -> right bottom , tl -> top left
I have to carry out computations such as finding overlapping rectangles , non overlapping rectangles , rectangles enclosing a point etc .
I tried two ways , one was the naive approach and as a optimized approach i tried to implement a quad tree , the results were fantastic for upto 100 - 150 rectangles but as soon as i touched the 500-1000 rectangle range , it started to take a very large amount of time to create the quad tree(insertion of all the nodes etc).
I want to know what is going wrong with my code or is it an issue with quad tree implementation , if it is what could i use instead of a quad tree which would suit my needs for upto 10,000 rectangles to lets say 200,000 rectangles
I am doing all this in google colab here is a link to my code https://colab.research.google.com/drive/1Ja5xwT9xE4z_6S3HgAN8CrBAU-dE61EY?usp=sharing
here is an example dataset
{{1, 4, 13, 7, 16},
{2, 10, 13, 13, 16},
{3, 3, 11, 13, 18},
{4, 6, 7, 11, 12},
{5, 7, 8, 9, 10},
{6, 11, 8, 15, 10},
{7, 13, 10, 19, 18},
{8, 16, 14, 19, 17},
{9, 10, 15, 11,18},
{10, 3, 5, 7, 9}}
Copy it into notepad and upload it in the code while running to see outputs