some comments

Month: October, 2012

Fast Mandelbrot set rendering

This demo is written for the Gameboy Advance. The GBA uses an ARM7 processor; the devkitpro toolchain can be used to compile Gameboy ROMs as described in the Tonc tutorials.

Plotting the Mandelbrot set isn’t particularly difficult. It does, however, plot very slowly (1 or 2 min for full resolution – 240×160 at 32 iterations per pixel ). It’s nicer if there’s something to look at while it’s rendering. In this example, the set is plotted at progressively higher resolution. Initially it’s plotted with 15×15 pixels and only samples the image once per 15×15 pixel block. The code avoids re-calculating pixels that have already been calculated by maintaining a list of the resolutions that have been plotted so far (implicitly tracking which pixels have been sampled). This reduces the computational requirements of this early/cheap plotting routine. The only real overhead is the extra time required to block blocks instead of pixels at the lower resolution.

Code based on Tonc’s m3_demo: http://asfarley.com/mandelbrot_demo.zip

Advertisements

Recursive search

Recursive search tree: topic ‘ruby’

Goal: construct a tree populated with topics related to a keyword of interest. Algorithm:

  1. Every day:
  2. Search Google for keyword.
  3. Follow the top 10 links. Get all HTML. Drop everything but text (javascript, formatting, other tags).
  4. Collate text documents & split into words.
  5. Remove “noise” words (discussed later) and occurrences of keyword
  6. Sort words by frequency of occurrence.
  7. Select the top n most frequency co-occurring terms and repeat.

Try it out here.

Undesired search results can be blocked in subsequent searches by clicking the red ‘x’ in each node. A JQuery event updates the noise list on the server end.

This was accomplished Rails, gems Nokogiriwheneversanitizeelif, open-uri, net/http, the Google Search API and JQuery.

The project’s code (also my homepage) is here on Github.

Noise is modelled by searching for 10 preselected, unrelated topics on Google. The algorithm described above is applied to the collated results (without the noise removal step) and the result is considered to be a general model of internet text background noise. The top most frequently occurring words are stored and blocked from appearing in recursive topic search trees.

Client-side state propagation with Backbone.js

I have an .xlsx file holding many vehicle trajectories (x,y pairs mapped to time). The goal is to render these trajectories for a browser.

To accomplish this, a Backbone.js collection fetches itself from a Rails server using JSON. Rails uses gem roo and a class variable to open and store the trajectories.xlsx file. The client iteratively request frames from the data set from a Rails controller action.

Backbone receives a list of vehicles for a given frame in JSON notation. The vehicle positions are overlaid on a static .png using HTML5 SVG. This makes the communication very lightweight – less than sending video, for example.

Between server updates with new sets of vehicles, the vehicle positions are locally propagated using velocity measurements and animated using a setInterval.

x(k) = x(k-1) + \dot{x}(k-1) \\ y(k) = y(k-1) + \dot{y}(k-1)

This smooths the vehicle’s apparent motion and further reduces bandwidth requirements.

Final result: Vehicle tracking

The source code is here on Github.

The application is running on a free Heroku node. I developed it locally on a Windows 7 computer with Rails Installer.