Tuesday, April 23, 2013


Google Maps, Python and the Mandelbrot Set

There's some surprising uses for a Mandelbrot set (or similar fractal). With just a small bit of code (and a little bit of computation), you can create an image that has detail at any level, and has varied features over the image so its possible to tell where you are. I've used this at work when debugging a scan system that could scan with fields-of-view from 2000nm to 1nm. It also had the ability to scan sections of the image. By writing a Mandelbrot generator as a test scan unit, I could test all of this functionality (I even had the number of iterations tied to the scan pixel time).

I was recently looking at creating a custom Google map, and I thought that using the Google Maps API to browse a Mandelbrot set might be pretty sweet.

It seems other people have had similar ideas, there's a version here and here, although I couldn't find the source for the first one, and the second doesn't include the continuous-zoom feature that Google maps has. This version only runs locally and needs Python for the webserver, and a browser for viewing the final page.

Creating the Mandelbrot Set

I wanted to use Python to create the Mandelbrot set and serve it locally. I split it into two files, one that creates a Mandelbrot set for a given set of coordinates, and another to respond to HTTP requests and return the requested image.

Creating the Mandelbrot set is relatively easy in Python, although a little different than I'd normally do so. Because whole-image operations are optimized in Python, it's faster to use them to create the set rather than iterate over each pixel individually (this also means that we don't escape from the algorithm once a pixel has diverged, we continue to process it for further iterations). I used a slightly modified version of the code from the scipy website, shown below:

#creates a mandelbrot for the given coordinates
import numpy as np

def mand(iters, tl, br, xpx, ypx=None):
    ypx = ypx or xpx
                       tl[1]   :br[1]   :ypx*1j])
    ret=np.ones(c.shape, dtype=np.int32)
    for it in xrange(iters):
        m *= m
        m += c
        ret += np.abs(m) < 2
    #want inf. iterations to be a single color, not based on # of iterations
    ret += -(iters+1)*(np.abs(m) < 2)
    return ret

def mand_and_write(file, iters, tl, br, xpx, ypx=None):
    from matplotlib import pyplot
    m=mand(iters, tl, br, xpx, ypx)
    pyplot.imsave(file, m, cmap='spectral', vmin=0, vmax=255)
if __name__=="__main__":
    from matplotlib import pyplot
    m=mand(16, (-2, -2), (2, 2), 256)
    pyplot.imshow(m, cmap='spectral') 

If you run this on it's own, it should show a small 256x256 Mandelbrot set:

The next step is to create the webserver, and route requests to our Mandelbrot generator. I decided to just split the request using '/'s, so a GET request with a path of /-2/-2/2/2/16 returns a 256x256 png from (-2,-2) to (2,2) with 16 iterations. The code is below:

#simple amnd server that returns pngs for a mandelbrot
from BaseHTTPServer import BaseHTTPRequestHandler, HTTPServer
import mandelbrot
use_threaded_server = True
if use_threaded_server:
    from SocketServer import ThreadingMixIn

import cStringIO

class MandServer(BaseHTTPRequestHandler):
    cache = {}

    def do_GET(self):
        self.send_header("content-type", "image/png")
        #we'll skip the leading slash
        if self.path not in self.cache:
            coords = self.path[1:].split('/')
            print self.path
            start = -1, -1
            end = 1, 1
            iters = 16
            if len(coords) >= 2:
                start = float(coords[0]), float(coords[1])
            if len(coords) >= 4:
                end = float(coords[2]), float(coords[3])
            if len(coords) >= 5:
                iters = int(coords[4])
            print "requesting ", iters, start, end
            memFile = cStringIO.StringIO()
            mandelbrot.mand_and_write(memFile, iters, start, end, 256)
            self.cache[self.path] = memFile
            print "Hitting cache!"
            memFile = self.cache[self.path]

def main():
    httpserverclass = HTTPServer
    if use_threaded_server:
        class ThreadedHTTPServer(ThreadingMixIn, HTTPServer):
        httpserverclass = ThreadedHTTPServer

        server = httpserverclass(('', 8080), MandServer)
        print 'started MandServer...'

    except KeyboardInterrupt:
        print '^C received, shutting down server'

if __name__ == '__main__':

If you run this, with mandelbrot.py from above in the same folder, it should start serving up the PNGs. You can test it (locally) by going to http://localhost:8080/-2/-2/2/2/16 and confirming you see an image similar to the one above (with a slightly different color scheme). The wbeserver runs threaded, so there's a new thread per request. Images are cached as they're created, so if you run this for a long time in can build up a big cache of viewed images.

Now we just need to get Google Maps to request images from this local address in the right format.

Custom Google Map Source

The first step to creating a custom Google Maps source is getting an API Key. You can do that here. Make sure that the 'Google Maps API v3' service is turned on in the 'Services' tab. Then copy your personal API key from the 'API Access' window.

Actually creating the custom map is relatively easy. We need to create a google.maps.ImageMapType that takes a structure containing the URL to request from and some other options, like the maximum zoom size (we use the highest, 19). I decided to automatically increase the iteration count as the zoom increases. The html is below, make sure to replace %Your-API-Key% with your API Key (surprise):

<!DOCTYPE html>
    <meta name="viewport" content="initial-scale=1.0, user-scalable=no" />
    <style type="text/css">
      html { height: 100% }
      body { height: 100%; margin: 0; padding: 0 }
      #map_canvas { height: 100% }
    <script type="text/javascript"
    <script type="text/javascript">

var mandelbrotTypeOptions = {
  getTileUrl: function(coord, zoom) {
      var bound = Math.pow(2, zoom);
 var left=(coord.y/bound - 0.5)
 var top= (coord.x/bound - 0.5)
      return "http://localhost:8080/" +  left +
      "/" + top +
      "/" + (left + 1.0/bound) +
      "/" + (top  + 1.0/bound) +
      "/" + (32*(zoom+1));
  tileSize: new google.maps.Size(256, 256),
  maxZoom: 19,
  minZoom: 0,
  radius: 2,
  name: "Mandelbrot"

var mandelbrotMapType = new google.maps.ImageMapType(mandelbrotTypeOptions);

function initialize() {
  var myLatlng = new google.maps.LatLng(0, 0);
  var mapOptions = {
    center: myLatlng,
    zoom: 1,
    streetViewControl: false,
    mapTypeControlOptions: {
      mapTypeIds: ["mandelbrot"]

  var map = new google.maps.Map(document.getElementById("map_canvas"),
  map.mapTypes.set('mandelbrot', mandelbrotMapType);

  <body onload="initialize()">
    <div id="map_canvas" style="width:100%; height:100%"></div>

And that's it. Just navigate to the webpage and you should see a fully functional Google Maps Mandelbrot set. As mentioned above, the results are cached, so that things should speed up if you look at areas you've previously been to.

You can find all the files above at github.

No comments:

Post a Comment