adw-charting

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

new adw-charting release (finally)

Version 0.8 is up on http://common-lisp.net/project/adw-charting/

In this release:

  1. docs that actually match the code – this was the vast majority of recent work
  2. the adw-charting gallery – I’ll be loading this up with more examples as time goes on
  3. separate google / vecto rendering backends
  4. tons of bug fixes
  5. code that sucks less – a lot of this code is from my earlier lisping days, and I’ve learned a lot since then.  Uses more loop / iterate / dolist and less mapcar.  There’s still a lot of spaghetti, but there’s less than before.

Latest tarball is http://common-lisp.net/project/adw-charting/adw-charting.tar.gz.

Have fun, kids!

adw-charting
lisp

Comments (1)

Permalink

adw-charting now has at least one other user

I’ve gotten some nice email from Erik Winkels giving feedback on adw-charting, and now today (which has had already it’s share of exe-related posts), I get one more email with a patch for supporting clisp executables.

I was loading a font file using a path relative to the (asdf:component-pathname …), and that was tripping up the exe.

Building standalone EXEs is still pretty low on my list, as I mostly make web apps and have servers available.  I think the growing desire good EXE support is a sign of lisp getting some more traction, as folks get past the “wanting to get their feet wet” stage and into the “wanting other people to use their software” stage.

Erik was kind enough to send a screenshot along with this amusing note:

I’ve attached a screenshot of the utility (it’s a trading tool for EVE-Online) and I’ve deleted the working title since it can be somewhat offense for some people.

The mind reels.  What was this name that was deemed too offensive?  It looks pretty nice, maybe he’s using ltk?

screenshot of Erik's app

screenshot of Erik's app

adw-charting
lisp

Comments (1)

Permalink

adw-charting progress and plans

It’s been awhile since I posted any updates on adw-charting, but some progress has been made.  After deciding to use google charts for rendering, a few months ago, I’m re-thinking the decision.  Google charts look very nice, but they weren’t as automatic as I’d hoped, and there was still a lot of processing needed before it could display a reasonable chart either.  Using google is certainly less CPU/memory intensive than using vecto, but there are a few problems:

  • charts are limited to 300,000 pixels, which is smaller than it sounds
  • because all the data needs to be passed on a URL, it chokes on large datasets.  This can be helped by using alternate encodings for values, but that looks like a pain in the ass (basically have to map the arbitrary lisp data evenly onto 0-64 or 0-4096, then encode as ASCII, I predict rounding troubles)
  • it doesn’t automatically scale to fit your size.  For example, a bar chart uses 20px wide bars by default.  If you have too many bars they just wander off the right of the canvas, and you need to manually adjust the bar width to get things to fit
  • some of the labels / titles get cut off

The google backend certainly has it’s uses, but I’m going to revive the vecto backend, which gives complete control.  As a start, I’ve split the project into a 3 asdf systems:

  • adw-charting: has some utils and common code, declares the :adw-charting package
  • adw-charting-vecto: adds/exports functions for making vecto charts in the :adw-charting package
  • adw-charting-google: adds/exports functions for making google chart URLs into in the :adw-charting package

In this setup, you’ll load adw-charting-google.asd or adw-charting-vecto.asd, and then all the dependancies will sort themselves out, and you don’t have anything loaded you don’t need.

I looked at asdf-system-connections but didn’t see how it would help, so copied cl-xmpp‘s multiple asd file scheme.  This is currently just in the darcs repo, and may have some bugs.

I’ve also started an actual adw-charting todo list, as part of a greater effort to be more organized in my life, comments welcome here.

adw-charting
lisp
vecto

Comments (0)

Permalink

adw-charting to get a lot prettier

I’ve recently come to an obvious conclusion: chart layout is really hard, and not in a fun way.

Luckily, Google has clarified the terms of use on their charting service, which is a RESTful API that returns png files based on some arc-ish querystring parameters. No google API key is required, the 300,000 pixel image size limit is reasonable, and they request to be notified if you need to make more than 250,000 charts in one day.

This afternoon I spent some a little time with DRAKMA, and ported my pie chart feature. I challenge you to guess which went through my layout code, and which came through google:

pie-gchart.png

pie-chart.png

Give up? Me too.

Here are the two functions used to generate those charts:

(defun pie-gchart ()
  (with-gchart (:pie 300 150)
    (add-slice "foo" 10d0)
    (add-slice "bar" 10d0)
    (add-slice "baz" 20d0)
    (save-file "pie-gchart.png")))

(defun pie-chart ()
  (with-pie-chart (300 150)
    (add-slice "foo" 10d0)
    (add-slice "bar" 10d0)
    (add-slice "baz" 20d0)
    (save-file "pie-chart.png")))

I was able to use generic methods to reuse all my existing code, but instead of performing VECTO operations, it builds up the proper parameter list and performs one http call.

I plan to make all of ADW-CHARTING use google to do the hard work. I’ve got some code in the darcs repo, and after I get my other chart types ported over I’ll update the website, examples, docs, etc.

I did decide to change my API approach for the google charts, making one with-gchart that takes the chart type as an argument, instead of have a with-pie-gchart, with-line-gchart, etc.

I was a little concerned about adding the dependency on google, but all of my usages so far are either for web apps that are already connected, or for generating static html, in which I’d be saving the chart locally anyway.

Some day I might revisit the chart layout problem, but for now the parameter building problem is a lot less daunting, and the API design problem is a lot more interesting. There are tons of options for google charts, and making lispy ways to specify all that should be fun.

adw-charting
lisp

Comments (1)

Permalink

adw-charting darcs repository moving

I apparently can’t follow instructions, and put my darcs repo in the wrong place on common-lisp.net, polluting their darcsweb. The new location is:

http://common-lisp.net/project/adw-charting/darcs/adw-charting

I’ll be deleting the old junk in a few days.

adw-charting
lisp

Comments (0)

Permalink

the beginnings of bar charts

Spent a ton of time today playing with adw-charting. I wanted to expand on the source contributor graphs from the other day, and ended up implementing some basic bar chart functionality.

I’ve read a lot of complaints about the lack of lisp libraries, so whenever I sit down to do some random task, I try to use libraries as much as I can to test the validity of those complaints. I also learn a lot by reading and experimenting with other people’s code, and slowly I can see my style getting more lispish, and less C#-ish. clbuild makes it trivial to get many libraries usable, and today I had good luck with everything just working.

I used darcs as my source of dataset, its xml changes output has a simply formatted time string. I told clbuild to install closure xml (cxml), and in fairly short order I had a 80 line program that:

  1. uses the cxml klacks system to pull the information I wanted out of the file in one pass
  2. uses cl-ppcre to parse the username out of the darcs author string, so authors “Ryan Davis <ryan@acc…” and “ryan@acce…” both get displayed as “ryan”.
  3. uses adw-charting to chart patches per day into a png

The result was less than spectacular:

darcs.png

The chart looks pretty nice, but its lying horribly. My data set didn’t have explicit zeros for days without activity, so the line goes from one active day to another, telling all kinds of lies. My favorite is the 2.5 patches it says I pushed on 1/11. The other fun one is that Russ shows up in the legend, but his one patch isn’t visible at all, because there was only one data point, and you need two points to make a line.

What is really appropriate here is a bar chart. Adding explicit zeros is a waste of time and RAM (among other things), so I opted for making a bar chart type. After many more hours of coding, I changed with-line-chart to with-bar-chart and re-ran my program:

darcs1.png

Much better. There’s a few rendering problems, but the data is shown alright.

Adding support for bar charts was actually really easy, it was going back and reworking my amatuerish code that took most of the time. My big accomplishments:

  • deleted a lot of code by using with-accessors
  • made all usage of x/y points go through 3 functions: make-point, x, and y, allowing for easily changing the internal representation of points in the future
  • removed some slots from an object, replacing it with a few functions to calculate the desired value
  • added a few more generic functions to support bar charts
  • reduced the size of the legend

After working on the line chart code for awhile, adding bar charts was trivial: one class that extends line-chart, one macro to mirror with-line-chart, one method to draw bars instead of lines, and a couple of helper functions. I was really pleased with how easy it was to add the different graphing mode.

Of course, giving another dataset exposes more problems:

darcs2.png

That’s for clbuild, and there are a few issues apparent here:

  • when more than one bar is shown for one day, it draws them next to each other, which makes it hard to tell where on the bar is on the x-axis
  • the legend wanders off the edge
  • the month/day labels aren’t very descriptive

I think I’m going to solve the first two issues by allowing a summarize mode, where less significant series can be aggregated into a single “other” series. This is how I see a lot of other programs solve it, so I’ll give that a shot. I don’t think that will completely solve the first issue, but should alleviate it a little bit.

The last issue I solved by making a function to show patches by month instead of by day:

darcs3.png

That shows the side-by-side bars problem pretty clearly, but what I find most interesting is the right side of the chart where we see more people starting to contribute. I think that’s indicative of the project gaining more users and activity.

Another interesting one, arnesi:

darcs4.png

Early on, Marco Baringer was the driving force, but somewhere around the middle of 2006 I guess he had finished scratching all his itches, and Atilla Lendvai became the prime mover.

Alright, I could seriously speculate about these things all night, so I’m gonna stop now.

I still need to fix the above-mentioned bar chart issues, so there’s no new release of adw-charting, but all the code mentioned here is in the public darcs repository (http://common-lisp.net/project/adw-charting/darcs/) for the curious.

See the examples folder for the darc-changes graphing program, you need to get the xml from darcs using: darcs changes –xml.

adw-charting
lisp
open source

Comments (0)

Permalink

sbcl contributors over time

I took a break from the day-to-day work (maybe giving Visual Studio’s a timeout will solve it’s “Generation of designer file failed: Unknown server tag…” problem), and noticed jsnell posted a list of SBCL contributors to #lisp, and decided to do some graphing:

yearly1.png

Of course, since I’ve never graphed this before, I found 2 bugs. I copied the text from jsnell paste and used cl-ppcre to split it up into data sets. I had to do a little math to get the months to line up nicely with the yearly sums, but it was all pretty straightforward.

Code, excluding the copied text from lisppaste:

(defun make-months ()
  (loop for month in '("Jan" "Feb" "Mar" "Apr" "May" "Jun"
		       "Jul" "Aug" "Sep" "Oct" "Nov" "Dec")
	counting T into val
	collect (list month (float (/ val 12)))))

(defun yearly-data ()
  (let (result)
	(cl-ppcre:do-register-groups (year contribs)
	    ("(\\d+):(\\d+)" +yearly-raw-data+)
	  ;;add 1 so the yearly totals line up with
	  ;;december monthly data
	  (push (list (+ 1 (parse-integer year))
		      (parse-integer contribs))
		result))
	result))

(defun monthly-data ()
  (let ((months (make-months))
	result)
	(cl-ppcre:do-register-groups (year monthname contribs)
	    ("(\\d+)-(\\w{3}):(\\d+)" +monthly-raw-data+)
	  (push (list
		 (+ (parse-integer year)
		    (second
		     (assoc monthname months
			    :test #'string=)))
		 (parse-integer contribs))
		result))
	result))

(defun yearly-graph ()
  (with-line-chart (600 400)
    (add-series "Yearly Contributors" (yearly-data))
    (add-series "Monthly Contributors" (monthly-data))
    ;;so the yearly totals line up, the data is offset by 1
    (set-axis :x nil :draw-gridlines-p nil :data-interval 1
	      :label-formatter #'(lambda (y)
				   (princ-to-string (1- y))))
    (set-axis :y nil)
    (save-file "yearly.png")))

adw-charting
lisp

Comments (5)

Permalink

more adw-charting paperwork complete

Made another release tonight, but there are no new features, this is just tying up some loose ends:

  • added a LICENSE file and license headers in each file.
  • removed cl-vector-chart.lisp, which I had looked at for inspiration, but ultimately decided not to use.
  • added a lisp file and shell script to automate making a release.

Thanks to Nikodemus Siivola for taking a look at the code and making some suggestions.

I’m still pretty new to the culture of open source, and it always amazes me when people spontaneously offer advice and help.  This sort of behavior helps restore my faith in humanity, which my national government seems to sap at every opportunity.  It’s very nice to see some upward spirals.

I’m also greatly amused by the stark contrast between the awesome lisp community that’s taking time to help me and the elitist-asshole lisp community I’ve read about off reddit.

Next time: some graphs to map performance differences as I evolve the adw-charting internals, and more Lisp.

adw-charting
lisp
open source

Comments (0)

Permalink

adw-charting 0.7

I finally got some time to employ the adw-charting library in my intranet app, and the increase in data sets revealed a lot of bugs.  Tonight I finally put together a release.

Some changes:

  • Pie chart slices are made much more intelligently, resolving some bad rendering with some datasets.
  • x-axis label locations are decided in a much more sane manner, and was reworked sans scotch.
  • if the x-axis label intervals are not sane, then you can specify what the interval should be with the new set-axis keyword argument, :data-interval.
  • the docs are updated to mention :data-interval and show an example usage.
  • Fixed a bug reported by Stuart Mackey with minimum x-values above 0.

So now I’m getting into several new territories:

  1. running an open source project
  2. coding lisp for performance

The first is pretty fun, really, everyone I’ve interacted with has been very helpful and reasonable.  There’s been a flurry of activity around lisp charting libraries, so I feel some sense of competition, but the big difference is I can incorporate someone else’s code to make my library better, which is pretty cool.  I’ve heard claims that open source is a way applying the scientific method to software, and (given the right licenses) that’s not too far off.  My next goal is to cannibalize cl-pdf‘s charting.  They have some niceness there that I might be able to toss in front of vecto and get a lot of nice features pretty quickly.

The second is a quite a bit more daunting.  Currently I cons an absurd amount to generate the example graphs (around 70MB for one graph), and I’d like to get that down a bit.  I’m going to setup some benchmarks and track some data on time spent and bytes consed, so I can tell if what I change is helpful.  I’ve been reading up on vectors and arrays, and will try to use those instead of lists where it seems easy.    The other thing I was thinking of was putting in some type declarations as a sacrifice to the compiler gods.

adw-charting
lisp

Comments (2)

Permalink