gainesville-green

more heat-maps using vecto and ch-image

This is a follow-up to my post last year about simplistic heat-maps using Vecto. To recap, I’m trying to make heat maps for google maps overlays.

Here’s how it works in a nutshell:

  1. From javascript I pass to the server the lat/lng region currently shown on the google map, and what size heat map to generate, in pixels.
  2. lisp pulls weights from my database within the given lat/lng region
  3. lisp iterates over the db results, mapping lat/lng to x/y coordinates for the final heat map image
  4. lisp uses the list of mapped (x y weight) to draw the heat map in png
  5. javascript throws the png on top of the google map

I tried a few things based upon the comments I got back from the helpful lisp community.

  • used zpng to get direct pixel access, and calculated each pixel’s color using a weighted average of nearby points using distance.  This didn’t produce good images, and was pretty slow.
  • used zpng to get direct pixel access, and calculated each pixel’s color using the gravity formula against nearby points.  This didn’t produce good images, and was very slow.

I did some more research and learned about the Generic Mapping Tools and bicubic interpolation. The GMT is a set of C programs, similar to the Imagemagick suite.  GMT showed one way to draw heat maps in the Image Presentations tutorial.  It spoke of gridded data sets, and that gave me one more vecto-based idea: split the desired heat-map into a grid and color each square in the grid based upon an average of the weights mapped in that square.  This is a neat effect, but not what I was going for:

This is reasonably fast, taking about 1 second on my dev server.  To quickly find what weights belong in which grid square, I make a spatial index of all the weights, using an r-tree from the spatial-trees library.

The next method I tried was to use interpolation to get a smooth look.  I found Cyrus Harmon‘s ch-image library supports image interpolation, and got to it.  As Patrick Stein noted elsewhere, ch-image isn’t easy to install.  It’s not asdf-installable, and the project page doesn’t list all its dependencies.  For future reference, here’s what I think I needed to install it:

(asdf-install:install "http://cyrusharmon.org/static/releases/ch-asdf_0.2.14.tar.gz")
(asdf-install:install "http://cyrusharmon.org/static/releases/ch-util_0.3.10.tar.gz")
(asdf-install:install "http://cyrusharmon.org/static/releases/smarkup_0.4.2.tar.gz")
(asdf-install:install "http://mirror.its.uidaho.edu/pub/savannah/cl-bibtex/cl-bibtex-1.0.1.tar.gz")
(asdf-install:install "http://cyrusharmon.org/static/releases/clem_0.4.1.tar.gz")
(asdf-install:install "http://cyrusharmon.org/static/releases/ch-image_0.4.1.tar.gz")

Armed with ch-image, now the drawing process becomes:

  1. draw a small image, coloring pixels based upon weights
  2. enlarge the small image with interpolation

The first step is very similar to the code I wrote to make the grid version above.   Instead of drawing a rectangle, I draw a pixel using ch-image’s pixel access functions.  This was a little weird because ch-image’s coordinate system has 0,0 at the top left of the image.  I’m still not sure how to best choose the size of this smaller image, but ultimately it should depend on my data.  For now I just have it hard-coded be 20x smaller than the desired size:

Yep, that’s pretty small.  Applying a transform to scale it up to the desired size using bilinear interpolation yields:

It looks pretty good and takes about a half-second to draw.  If you click into the larger version, you can see some discontinuities in there, which is a well-known result of bilinear interpolation.  However, based upon other graphics I’ve seen, what I really want is bicubic interpolation.  Luckily, ch-image has this built in:

Oops, maybe not so luckily.  I can certainly see the kinds of look I’m wanting in all the garbled stuff, but ch-image is freaking out somewhere there.

Bilinear it is!  Here’s a screenshot of the overlay in place on the map:

It’s pretty fast, and looks pretty nice, and is fairly close to the look I wanted.  I probably still have some off-by-one errors somewhere, and need to check the git repos for the ch-* libs to see if there might be newer versions than the tarballs I installed.  I still count this as great progress for 5 hours of coding and research.  Huzzah for the much-maligned lisp libraries!

adw-charting
gainesville-green
lisp
vecto

Comments (1)

Permalink

simplistic heat-maps using Vecto

I stole some time from my increasing non-technical workload to play with generating heat-maps of residential energy consumption in my http://gainesville-green.com project.  The initial results are promising:

There are a few neat things going on here.  I’ve got a url handler in my lisp that looks to the query string for lat-lng bounds, image size, and some other variables to generate a PNG file.   I pass that URL to a Google Maps API GGroundOverlay to put the image onto the map.  Add some javascript event glue and I can do cool things like automatically regenerate the heat map overlay when you zoom/pan the map around, and display an animated heat map showing consumption over the course of the year.  There’s still a lot of UI interaction to sort out, but I think it’s a nice approach.

The heat map itself is generated using Vecto, and I think I’m doing it wrong.  I jump through some hoops to map lat-lng to image pixel coordinates, pull from the database, and end up with a list of (x y weight) tuples, with the weight being a number between 0.0 and 1.0 representing the relative consumption of the home that should be at pixel x,y in the result image.  Then I start painting, which is where I think I should be doing more math.  For each point, I pick a color between green and red based on the weight, using the handy cl-colors library to interpolate:

(defun find-color (percent)
  (if (> .5 percent)
      (cl-colors:rgb-combination cl-colors:+green+ cl-colors:+yellow+ (* 2 percent))
      (cl-colors:rgb-combination cl-colors:+yellow+ cl-colors:+red+ (* (- percent .5) 2))))

I actually have to go from green->yellow, then yellow->red, with some goofy adjustments to the percent to make the interpolation work out.  Once I have that, then I have my color, and my pixel, so I can start drawing.  To get a smoother look, for each point I draw concentric circles with different radius and opacity, so each individual data point is rendered like this:

This is enlarged to show some of the blockiness, it ends up looking pretty nice when they are small.  Here’s the actual function:

(defun draw-point (x y color max-radius)
  (iterate (for r from max-radius downto 1 by (max 2 (round (/ max-radius 6))))
	   (for alpha = (/ 1 r))
	   (vecto:set-rgba-fill (cl-colors:red color)
				(cl-colors:green color)
				(cl-colors:blue color)
				alpha)
	   (vecto:centered-circle-path x y r)
	   (vecto:fill-path)))

Max-radius determines how large the largest circle is, and is calculated based on how many points I’m drawing.

There are a few drawbacks to this approach.  First, it’s slow.  Drawing operations aren’t exactly cheap, especially when messing with alpha channels.  It takes me around 5s for 578 data points, which is fine for offline tasks, but on a web-app it needs to be super zippy or you fickle internet folk will close the tab. I also want it to be easy to show animations, so generating a bunch of them quickly would be nice.  The time spent increases fairly linearly with data points, and I’d like to be able to render heat maps for large areas with tens of thousands of data points.  Profiling shows practically all of my time and bytes consed are spent in the draw-point function. UPDATE: after more profiling, vecto:fill-path is most of my time, which makes sense.

Second, I have to be really careful to draw these points from lowest weight to highest weight, because I want red dots to be painted on top of green dots.  It seems like I should decide what color each pixel should be, then draw it once, rather then accumulating the right color in the image canvas.  Right now there’s also some bug with drawing lots of data points, I just get a big green image, when I would expect some reds or yellows.

Another issue is for apartments I have coordinates for the apartment complex, but not each individual unit.  This makes some funny results, like the big orange blob on the right side of the screenshot above where I’ve painted a few dozen points on top of each other.

I did some googling on heat-map algorithms, and found some actionscript and java code, but the actionscript was using a similar approach and the java was incomprehensible.  I think I’ll try making a big array for the result image, and calculating an average weight for each pixel, then loop through that and draw once.  I’m also going to try calculating the weights using magnetic field strength or gravity math.  I think that approach will end up faster, look nicer, and should be a fun problem.

gainesville-green
lisp
vecto

Comments (6)

Permalink

New term: Stealthy-patch

By now we’ve all heard of monkey-patching, and I propose a new variant: stealthy-patching.  This is the act of patching a currently running process with zero downtime.  This is similar to monkey patching, but doesn’t have the negative connotations.

I just connected to the Gainesville-Green app and evaluated a few forms to add intelligent handling of the enter button on search pages, along with some new parenscript for more IE compatibility.  All told I redefined 1 UCW component and 2 defmethods, all without any active users getting interrupted.

On the other side of the coin, I also compiled and uploaded a new SBCL core containing those fixes, so next time the application restarts (in a suprise reboot, for example), my patches will still be in place.

Ahhh… so much flexibility.  It’s like getting into a hot-tub after a long day of frigid C#.

gainesville-green
lisp

Comments (0)

Permalink

Prepping for Load

A week ago, our UCW-based website (Gainesville-Green) got some local news coverage (see “Gainesville-Green.com Segment Aired on WCJB TV20” on the project’s blog), and we spent the day trying to prep for an increased load.

Our setup is fairly straightforward:

  1. apache and mod_proxy to serve static content and get dynamic content from…
  2. a lisp (sbcl) http server listening on 127.0.0.1:3xxx talking via CL-SQL to…
  3. a postgresql database on a separate, more powerful server

When 5pm rolled around, we had:

  • long-lived caches of some expensive queries in lisp
  • lisp generating proper Cache-Control and Last-Modified headers to let our mostly static content be cached aggressively (using a new UCW dispatcher)
  • some visual / usability tweaks
  • cron job to automatically restart the lisp application server if it fails to respond

Over the next couple of days we added some more:

  • used mod_disk_cache on Apache’s end to put a cache server directly in front of our lisp server
  • reworked some entry points to work nicer with the cache
  • referenced our javascript libraries from Google’s AJAX Libraries API, which will serve the big js files off their content distribution network, gzipped and minified

So, not too much optimization was done inside lisp itself besides some basic memoization of database queries.  Hans Hübner made a post on Building Resilient Web Servers last week after our sprint, but our needs were much simpler.   We have basically static content that we want built on-demand.  From what I’ve read we could probably be faster by replacing Apache with nginx or some such, but for now it meets our needs nicely.

For a few days our cron job was reporting the site as regularly down and restarting it, and we finally tracked that down to a bug in the restarting script.  Turns out the HTTP “Not Modified” response code is 304, and we were looking for something in the 2xx range, so restarting needlessly.

The burst of traffic that Friday night was the most we’ve seen on any of our lisp projects, we got over 4000 hits that day on a weaker test server.  We’re serving 500-1000 pages per day now, and most of the bandwidth is coming from google’s CDN, so our load is nice and light, averaging around 15K per request.

I LOVE how straightforward and composable all these tools are.  Now that our “stay-alive” cron job isn’t randomly killing our lisp, we should have a nice long-lived process and better uptime.

gainesville-green
lisp

Comments (4)

Permalink