Given a set of x,y data points, a viewport and the recursion depth, calculate box counts at a particular level.

gistfile2.txt

Henon.py

def quarter((x0, y0, x1, y1)):
    quadrants = []
    
    # Define the width and height as half the width and height of the given box
    width = (max(x0,x1) - min(x0,x1)) / 2.0
    height = (max(y0,y1) - min(y0,y1)) / 2.0
    
    # Starting with the bottom left corner
    x = min(x0,x1)
    # Go through all 4 combinations of adding width and height to x and y
    while x < max(x0,x1):
        y = min(y0,y1)
        while y < max(y0,y1):
            quadrants.append((x,y,x + width, y + width))
            y += height
        x += width
    # Return the list of the 4 quadrants we just generated
    return quadrants

def minimize(data, window, levels):
    # Coordinates to use for the first box
    x0,y0,x1,y1 = window
    
    # Define the queue that will hold boxes
    boxQueue = []
    
    # Set the current level to the number of levels we want to do
    currentLevel = levels
    
    # Define the dictionary that will hold box counts per level
    levelCount = {}
    
    # Push the first box and the currentLevel to the queue
    boxQueue.append((currentLevel, window))
    
    # While the queue isn't empty
    while len(boxQueue) > 0:
        # Get the next level and box from the queue
        currentLevel, currentBox = boxQueue.pop(0)
        # Expand the dimensions of the currentBox
        x0, y0, x1, y1 = currentBox
        # Check each data point
        for x,y in data:
            # If it is contained within the current box
            if x >= x0 and x <= x1 and y >= y0 and y <= y1:
                # Increment the box count for the current level
                levelCount[currentLevel] = levelCount.get(currentLevel,0) + 1
                # If we haven't reached the depth limit of recursion
                if currentLevel > 0:
                    # Get the quadrants of the current box
                    quadrants = quarter(currentBox)
                    # Add each of the 4 quadrants to the queue
                    for quadrant in quadrants:
                        boxQueue.append((currentLevel - 1, quadrant))
                    # We can stop checking data points for this box now
                    break
    return levelCount
    

x = [0.1]
y = [0.3]
A = 1.4
B = 0.3
for i in xrange(200):
    x.append(1.0 - A*x[i]*x[i] + y[i])
    y.append(B*x[i])
    
data = zip(x,y)

levels = minimize(data, (-1.3,-1.3,1.3,1.3), 15)

for level, count in levels.items():
    print "%d\t%d" % (level, count)