Sign in to follow this  
Dospro

QuadTree vs List and Recursion

Recommended Posts

Hi.

I'm testing some data structures and algorithms in python so i can decide which ones and when to use them in the project i'm implementing.

 

The problem is simple. I have a list of rectangles in different positions and with different sizes. Given a list of points i want to know which rectangle contains each point. The list of rectangles may be up to 10000 (perhaps even more).

 

My first attempt just to get something working and a reference for profiling, was to use a bruteforce algorithm. For each point for each rect check interesection.

 

The two data structures i'm testing are QuadTree and HashGrid.

QuadTree made a wonderful job:

 

 

Test for: 5
List: 0.111369848251
Tree: 0.202666044235
Ratio: 54.9523965258%

Test for: 10
List: 0.590306997299
Tree: 0.719012022018
Ratio: 82.0997395345%

Test for: 20
List: 0.869105100632
Tree: 0.626720905304
Ratio: 138.674981683%

Test for: 40
List: 0.842307090759
Tree: 0.356130123138
Ratio: 236.516665127%

Test for: 80
List: 0.208228111267
Tree: 0.0534420013428
Ratio: 389.633819908%

Test for: 100
List: 0.297593832016
Tree: 0.0617258548737
Ratio: 482.121847685%

Test for: 200
List: 0.686511993408
Tree: 0.0824010372162
Ratio: 833.135135917%

Test for: 400
List: 1.10695695877
Tree: 0.0750210285187
Ratio: 1475.52890253%

 

Test for n means Number of rectangles inserted randomly.

Until there the results are promising, excepts, that for 600 Rects:

 

 

Exception RuntimeError: 'maximum recursion depth exceeded while calling a Python object' in  ignored

 

For 600 this occurs randomly. But for 800 is almost a 100% to occur. I can't even get to 1000.

 

I don't know if there even exists a language which can handle this levels of recursion. So it seems, i have to do something about it.

 

In my code there are to sections i use recursion: When inserting a rect, and when getting the rects near the point. My max number of objects per node is 4, and there is no limit in the number of levels the tree can have.

 

Are there better ways to implement a QuadTree perhaps without recursion? Or should i limit the levels of the tree? Tweak the maxObjects per level?

For 10000~ rectangles, what would you do? Perhaps not using QuadTree although its efficiency is really good for big number of quads?

Share this post


Link to post
Share on other sites

Whoa!!!

 

I found the reason for the high recursion. It seems to be a very rare problem.

Let's say max objects per level is 4.

If you have 5 rects exactly at the same position (x, y). Then When inserting the rect into the Quad Tree it will recurse infinitly. n my implementation the quadtree regions become negative!!!

 

Well, as long as i dont have more than maxObjectsPerLevel in the same place, everything will work fine.

 

I would still like your opinions.

 

Share this post


Link to post
Share on other sites

It sounds like you've found your bug, but it may still be useful to have some insight into why you're unlikely to need a lot of recursion even for huge numbers of rectangles.

 

A quadtree can be constructed and traversed in logarithmic time, i.e. the number of recursive calls you make should only grow by log(N) every time you increase your data set by N rectangles. A quick look at a plot of a logarithmic function will show you (in case you're not familiar) that it takes an extremely long time to need each additional level of recursion. By the time you need 50 levels of recursion, for example, you could store something like 1,000 [i]trillion[/i] rectangles.

Share this post


Link to post
Share on other sites

It sounds like you've found your bug, but it may still be useful to have some insight into why you're unlikely to need a lot of recursion even for huge numbers of rectangles.

 

A quadtree can be constructed and traversed in logarithmic time, i.e. the number of recursive calls you make should only grow by log(N) every time you increase your data set by N rectangles. A quick look at a plot of a logarithmic function will show you (in case you're not familiar) that it takes an extremely long time to need each additional level of recursion. By the time you need 50 levels of recursion, for example, you could store something like 1,000 trillion rectangles.

Indeed. That works in a perfectly even distribution of the rectangles. If most rectangles are almost in the same place, the number of recursion increments linearly instead of logarithmically.

Of course, the idea of using a Quad Tree is for rectangles that you expect are more or less evenly distributed. Jajaja. For the test, by using random rects, this problem arose but it shouldn't in "normal" case scenario. Although i put a Max level of recursion just in case....

Share this post


Link to post
Share on other sites

I don't know if there even exists a language which can handle this levels of recursion.

Python can.

Well, it cannot handle infinite recursion of course, but Python has a limit of 1000 nested calls depth built-in. I assume they did that to avoid the Python interpreter crashing on infinite recursion (and instead give an error message like you had).
You can change the max depth if you want, but as others have said, it shouldn't be necessary in quad trees.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this