Spatial Partition-ing

Recently, I was given the framework for a unity project that creates a white circle on a black background. It ran and printed out how long it took to print out a set amount of said circles. The goal was to use some form of spatial partitioning to improved the efficiency of the program.


Ultimately I decided to use the grid method, as it was a fairly simple problem and I didn’t want to over complicate the problem and use a quad-tree, although I am well aware that it would have made the program even more efficient than my end result.


I started by creating the grid itself, iterating over the grid to give the cells correct width and height and than adding each circle to its own spot within the grid. After doing this I lowered the run time from 10.4 to 6.0, so its not far from being 50% more efficient. As mention above, I am sure that if I used a quad tree it would have been even faster but since the goal was to reduce run-time and not to make run-time as fast as possible and how the grid method is generally easier to implement than quad tree, I decided grid would suit this particular task.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s