Quadtrees

The code below implements some quadtree extensions, as discussed in another Dev.Mag tutorial about quadtrees (see Issue 27). The tutorial covers the following topics:

  • what to consider in choosing whether to use a quadtree or not;
  • tests to help you choose an appropriate threshold;
  • how to handle discrete data; and
  • some modifications to the basic algorithm.

Handling Discrete Data

When it comes to discrete data, the “average” of a number of pixels doesn’t make sense. However, we can give it meaning and still use it to get good approximations of the original data, as illustrated in the images below.

The original grid of discrete data. The grid contains integers from 0 to 4. Every integer is mapped to a colour in this image. (If this grid represented a tile map, every integer would be mapped to a different tile).
Here we allowed floating point numbers in the quadtree. Results of queries into the quadtree are rounded before mapping them to colours.
Here we used the floating point part of queries to bias a randomly selected integer. For example, a result of 1.25 will result in a 75% chance of yielding 2.
Here we use a quadtree with interpolation. The result is rounded before it is mapped.
Here we use a quadtree with interpolation, and use the floating point part of the number to bias a randomly selected tile, as above.

Download

Python Implementation

Download from: http://code-spot.co.za/python-image-code/ (See quadtree.py, quadtree_image.py, and quadtree_demo.py).

  • http://bydersjoint.wordpress.com Byder

    Hey,
    Just saw your article in the DevMag… looks awesome!
    Did you have any say on the layout, coz its very nice!!!
    ~C

  • admin

    Thanks 😉

    No – the cool layout is all the doing of the Dev.Mag guys – the file I give them is very raw.