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

latest postgres docs bookmarklet

When using google to find things in the excellent Postgresql documentation, I often end up on pages showing old postgres versions.  For example, googling for “postgresql create index”, the first hit is for the postgresql 8.2 docs, and I’m running 8.4 now.  My co-workers made a greasemonkey script to automatically redirect to the current version, and I adapted that into a bookmarklet.

Drag this link into your address bar to to use it in your browser:

pg-docs

When you find yourself on a old postgres docs page, click the bookmarklet to redirect to the latest version of that page.   This should work as long as the postgres folks keep their URL naming scheme.

javascript
postgresql

Comments (0)

Permalink

git-like line counts in svn using bash

I really like how git tells me how many lines inserted/removed when I commit, and wanted to get something similar from Subversion.  I’m working on a refactoring of an older system, and I wanted to know how my refactorings were effecting the code.  I think I’m going to remove a lot more code than I add, but why wonder when svn has all this info?

Using my horrible bash skills and this post on SVN Line Output Totals, I came up with an inefficient bash program to do what I want:

Example:

 > svn_line_changes -r 264:265
Scanning -r 264:265
Removed: 287
Added: 141
Difference: -146

bash
open source
subversion

Comments (2)

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

Brian’s functional brain in lisp

Last week I saw a breathless headline on proggit about clojure and Brian’s functional brain: http://blog.bestinclass.dk/index.php/2009/10/brians-functional-brain/, written by Lau.

As a Common Lisp programmer, Clojure irritates me for various irrational reasons.  As an exercise in breaking those down, I ported Lau’s 67 line program (which had no comments) to CL running on SBCL using asdf-installable libraries.  I used lispbuilders-sdl for display and pcall for concurrency.  I ended up with 115 lines, including comments and some significant differences in the program.

I went through a few revisions, initially trying to transliterate the code, looking at the fine clojure API docs to figure out what different things did.  Then I gave up on that wrote more idiomatic (at least for me) lisp, but still resisted the urge to use iterate of alexandria.  I wanted to have code that was as close to the bare language as possible, so I could make an apples-to-apples comparison.  Now that the exercise is done, I think that goal was unattainable.  It’s close, but the differences in the languages are significant, so it’s not an great comparison.

After the first round, I started diverging more from the Lau’s version, looking for higher FPS and nicer lisp.  I ended up with a few major differences:

  1. I used a 2D array to represent the world, the Lau used a single long vector and I didn’t quite understand how it was determining adjacency
  2. I had a lot more functions to abstract out that data structure choice (ie: instead of calling aref everywhere, I made a get-cell function)
  3. Lau called pmap function to calculate each cell’s next value in parallel, and I used pcall to calculate the next whole world state while the main thread rendered.
  4. Lau drew boxes for each rendering loop, I made two SDL surfaces up front and blitted them in at the right spots

I spent a little under 4 hours playing with it, and a lot of that was reading documentation.  I don’t think any conclusions can be made from this for a “common lisp vs clojure” flame war, these are both fairly throw-away pieces of code.  I have no doubt that any experiences lisper or clojurer would find a lot of obvious improvements.

Some of my observations along the way:

  1. getting the lisp libraries to work (which I’ve done in the past) is probably harder than getting clojure working and using java libs.
  2. java libs look like a pain in the ass.  This softens the “and you can use java libs!” selling point of clojure for me.  They’re still java libs.
  3. The places where clojure calls java are kinda ugly, it’s a square peg in a round hole.
  4. clojure has a ton of lazy-evaluation semantics built into the language.  In this case, that seemed to be a bad thing, and most of Lau’s code was calling some wrapper function to say “no really, I want you to actually do this”.
  5. Clojure has more syntax than I thought, using # % [ ] _ to mean different things (maybe in different contexts?).
  6. I’m not sure how the STM features I’ve heard a lot about come into play here, if at all.
  7. I should be asdf loading my libs in a nicer way, right now you need to evaluate those first lines, and then compile the file.  I didn’t have the motivation to create an .asd file or finally learn how to use eval-when properly.
  8. I like long, descriptive function names.  Some of the ones from clojure irriated me: doall, doto.  It reminds me of arc a little.
  9. I was confused by the per-cell parallelism in the clojure version (I think clojure uses native threads in a threadpool).  Pcall does the same thing, but I figured I’d be spending more time context switching than calculating, and it was getting late.

Anyhoo, a fun sunday evening.

Code is on github: http://github.com/ryepup/sandbox/blob/master/brain.lisp

cellular automata
clojure
lisp

Comments (4)

Permalink

talking usb-serial to my arduino from lisp (sbcl) on linux

I got an arduino microcontroller a little while ago, and have played with it a little but found it’s C/C++ development environment annoying.  I wanted to control it from lisp, and that meant serial IO.  Many other languages have special serial libraries you can use, where you instatiate a Serial object with configuration like baud, parity, etc.  John Wiseman wrote arduino_serial.py that shows this pattern.

I searched around for lisp options, and came up with a few options:

  1. open /dev/ttyUSB0 directly (from a comp.lang.lisp thread)
  2. use a FFI wrapper around libusb (from a comp.lang.lisp thread)
  3. use sb-ext:run-program to call out to python/C/whatever to deal with the serial port (we do something similar at work to render trac wiki markup to HTML in lisp)
  4. write a small C program and FFI to that (was tempting for the experience)

After much trial and error and some advice from the helpful folks on #lisp, I got method #1 working tonight.  I was able to read from arduino pretty easily, but I needed to issue this magic stty command before I could write:

stty -F /dev/ttyUSB0 9600 raw -parenb -parodd cs8 -hupcl -cstopb clocal

I had been curious how lisp (or my underlying linux) would know what baud, parity, etc to use, and it makes perfect sense that I need to set these first.  After that, the lisp side ends up pretty simple.  It took a little tweaking to find the right :direction, :if-exists, and :external-format arguments.

(with-open-file (stream "/dev/ttyUSB0"
			:direction :io
			:if-exists :overwrite
			:external-format :ascii)
  (format stream "hello")
  (read-line stream))

Disorganized source is available at http://github.com/ryepup/arduino-experiments.  I have a few servos laying around, maybe this weekend I’ll have time to get lisp moving around the real world.

My dream goal is to have lisp controlling motors that are spinning mirrors to reflect a laser in very particular patterns.  I’d use this on halloween decorations for starters, combining with fog machine/dry ice to create nifty patterns and make people wonder how the hell I did it.  Maybe, if I have the willpower to see that through, then I’ll also hook up a USB camera (using cl-v4l2) and get lisp to track and hightlight objects, augmented-reality style.  That’d be great for table-top games, being able to overlay terrain or effects on a grid mat.

arduino
fun
lisp

Comments (18)

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

HOWTO: start using lisp in your work environment (part 1)

Getting started with lisp is no easy task. Tools like clbuild and Lispbox make it easier than a few years ago, but there are still obstacles (some quite reasonable) to using lisp in your work environment. After conversing about the subject a little with Alberto Riva (another local lisper!) and seeing trichey mention it, I figured I’d write up the successful approach I employed.  Everyone’s workplace is different, and these may not work for you. YMMV.

First off, here are some questions any manager worth their salt will have, that you will need to address:

  1. How much is supporting another language going to cost me? (buying the software, upgrading the software, running and updating servers, training staff, etc)
  2. Will our customers be OK with using this esoteric language?
  3. How will I hire anyone who knows lisp?

In my workplace, we’re a small consulting shop, and I am both programmer and manager.  People come to us asking for a website that does X.  We then figure out they want X to solve problem P, and suggest a website Y to solve P.  These are mostly simple CRUD applications.   There’s a bunch of data and a handful of things they want done with it, but mostly they just want to look at it. We used ASP.NET with C#, and were having a hell of a time abstracting common functionality between projects.   After writing the same code over and over, we knew there had to be a better way, which brings us to the manager’s first concern: cost.

The pro-lisp argument boils down to: we can save money by adding lisp to our toolbox and using it where appropriate.

1) Establish and demonstrate inefficiencies with the current toolset

In our case, we were dealing with ASP.NET version 1, C# version 1, and .NET Framework 1.1.  This combination was vastly superior to the vbscript ASP we had been running before, but there were still things we simply couldn’t abstract.  We used code generators (provided by Microsoft and written in-house) to write tons of boilerplate C# code, and spent a lot of time frustrated.  To be fair, Microsoft tried to help by releasing more versions of ASP.NET, C#, and the .NET Framework, and it was possible to generate our C# at runtime using C#, but the syntax is ridiculous (see listing 6 on Late Binding and On-the-Fly Code Generation Using Reflection in C#).  On the flip side, all those new versions of ASP.NET, C#, and the .NET Framework require a lot of work to keep up with, and it is difficult to explain to non-technical customers why they need to spend money to get something totally invisible to them.  Another big factor in our displeasure with ASP.NET was how hard it was to have a shared user control library.

The goal of this step is to convince the manager that your current toolset is not a silver bullet, and he could be saving money by introducing other tools.  Of course, be honest.  If the current toolset is really well suited for the work, then you have no reason to switch.

2) Use open source development tools

If your workplace doesn’t already, start.  Some managers might be accustomed to paying costly fees for everything under the sun, and is rightfully skeptical about increasing his tool costs.  Some managers might be confused about the maturity and quality of open-source offerings, and applying the “you get what you pay for” adage.  Either way, the cost argument can largely disappear when using open-source lisp tools and implementations.  Ideally get emacs into your workplace.  I’d say a good 10% of my costs with running lisp working were spent learning how to use emacs effectively.  In our MS environment, we started with NAnt, Subversion, and TortoiseSVN.  Those projects convinced me that open source is inevitably going to corner the developer tools market.

The goal of this step is to convince the manager that there is no great risk to trying out new open-source projects, and OSS can be cost-saving measures.

3) Find a small project you where you can use lisp as a infrequent manual step in an existing project

By limiting the scope (particularly by excluding a runtime component), you minimize the manager’s risk if lisp isn’t up to the job, and side-step any costs with running lisp as a server, or keeping your lisp implementation updated.  In our case, we were writing a XUL application, and needed to generate tons of XML.  XUL is a neat environment, but verbose as all hell and the standard abstraction mechanisms (XSLT, XBL) left us wanting.  We introduced lisp to generate this XML, and found all the abstraction we were looking for.  Lisp was natural fit for XML generation, as the tree of code tended to mirror the resulting XML tree.  This step will take time because you’ll need to get slime/emacs/lisp configured.  This may test your manager’s patience if you’re inexperienced with lisp.

The goal of this step is to demonstrate to the manager the efficacy of lisp without requiring a major investment, and show how lisp can quickly add value to existing projects.

4) More manual lisp processes, more people

Here you apply lisp to more one-off problems, or expand on the previous project.  In our case, we started generating javascript with our XUL, wrote a pricing calculator for an existing product, and a script to check the status of many internal subdomains.  This will involve getting more people involved with lisp.  Pair program a lot here on people who don’t know lisp.  Watch SICP lectures.  In my case, my co-workers were all excited about lisp, and picked it up very easily.  We weren’t doing anything advanced, and the context of XML generation made it all pretty easy to think about.  If your co-workers do not take to lisp, then you’re probably SOL.

The goal of this step is to demonstrate to the manager that the whole team can benefit from lisp, and get them thinking about what else lisp can offer.

5) Pick a medium-sized internal project and run lisp in production environment, in cooperation with an existing project

This is where the manager needs to stick their neck out a bit and convince his powers-that-be to try something new and different.  This might involve working with your systems department to setup a new server, and will likely have pretty high visibility even if the project itself is low priority.  This project should be something used internally so we don’t have to tackle the “what would our clients think of lisp” question yet.  Here is where you really need to deliver for your manager.  In our case, we had a 10 year old C++ app running some core invoicing logic.  The thing was riddled with bugs, and the source wasn’t even in version control.  The staff had just figured out how to work around it.  This was ripe for the pickings, and we made a website that talked to the same database, so they could be used in tandem.  In our case, just about anything was better than the C++, and lisp brought a new era of flexibility.  To ease deployment, we generated lisp executables (using sb-ext:save-lisp-and-die) on the dev machines, copied them to the production server, and run them behind proxy servers.  This eliminates the costs associated with updating  lisp implementations on production servers.

The goal of this step is demonstrate lisp’s stability and effectiveness in a production environment.  If you’ve achieved this, you have demonstrated the cost-effectiveness of lisp, and can use it on any internal projects.

Gosh, that ended up a bit more verbose than I intended, I’ll try to make the next one more concise.

lisp

Comments (17)

Permalink

shibboleth attribute “scope () not accepted” and “value () could not be validated by policy, rejecting it”

I have a client who acts as a Shibboleth Service Provider (SP), and the corresponding Identity Provider (IdP) needed to update some of their information, so I had to spend a few hours debugging shibboleth again this morning.

The punchline: in the metadata for an IdP, there are TWO places you need to specify the scope of the IdP, once in the <IDPSSODescriptor> to cover authentication, and once later in the <AttributeAuthorityDescriptor> to cover any attributes.

Shibboleth is all about trust, and the lack thereof. The SP and IdP share a few keys, and then each maintain their own configuration files specifying how much information to trust. When a user logs in, they get bounced from SP->IdP to authenticate, then again from IdP -> SP with an auth token. From there, the SP can assume an authenticated user. If the SP wants any more information about the user (say, a username), it can make SOAP calls to the IdP requesting more attributes. The IdP checks it’s config files to see how many attributes to release to that particular SP, and sends back the attributes. The SP doesn’t trust the IdP on it’s word, so the SP checks it’s config files to validate that it can accept these attributes from this IdP. This is where I ran into a problem, getting an error like:

attribute (username) scope (foo.bar.edu) not accepted

This brings up another aspected of attributes, the scope.  An attribute’s scope seems somewhat akin to a namespace to me, it’s a way of grouping related attributes and prevent name conflicts between attributes.  In my case, my IdP was “bar.edu”, and my SP was configured to accept the username attribute from any site with any value (in my AAP.xml).  However, the IdP was returning the username scoped under a different domain, so the SP, being a paranoid creature, assumes the IdP is trying to falsify information and refused the attribute.  To convince the SP to accept the different scope, you have to change the metadata for the IdP, and specify that it is allowed to provide attributes in the new scope.  Unfortunately for me, there are 2 kinds of scopes you can change:

  1. Scope of the initial authentication
  2. Scope of the attributes

There are both children of <EntityDescriptor>.  This led to a frustrating morning of restarting IIS (because you need to restart everything under the sun for the configuration to get reloaded), and not seeing any change.  There are many ways to alter your attribute policy, and along to way to discovering the second place to specify scope I ran across another error message:

attribute (username) value (my-user) could not be validated by policy, rejecting it

This seemed to happen when my SP config tried to treat the username as an unscoped attribute.  You can’t just ignore the scope of an attribute if the IdP is sending one.

The end solution is to add another <shibmeta:Scope> specification to the attributes configuration section in the IdP’s metadata:

  <AttributeAuthorityDescriptor protocolSupportEnumeration="urn:oasis:names:tc:SAML:1.1:protocol">
    <Extensions>
      <shibmeta:Scope xmlns:shibmeta="urn:mace:shibboleth:metadata:1.0" 
                      regexp="false">bar.edu</shibmeta:Scope>
      <shibmeta:Scope xmlns:shibmeta="urn:mace:shibboleth:metadata:1.0" 
                      regexp="false">foo.bar.edu</shibmeta:Scope>
    </Extensions>
    ...

annoying
shibboleth
windows

Comments (33)

Permalink

simple job scheduling with a threaded lisp

Yesterday I had a need to do some batch processing, making many HTTP calls to crawl a government website to pull down some public data.  I didn’t want to run this during normal hours, because I didn’t want to put a strain on their server.  I had the web crawling sorted out as a function using drakma and cl-ppcre to get the data I wanted.

I wasn’t sure how best to schedule this function to run later that night, and was about to dig into anacron and figure out the right command-line flags to sbcl, when Nathan suggested the obvious:  why not have lisp schedule it?  It was very easy to throw something together using sleep and get-universal-time.  This morning I abstracted that into a helper function using SBCL Threading:

(defun run-later (utime-to-run function)
  (sb-thread:make-thread
   #'(lambda ()
       (sleep (- utime-to-run (get-universal-time)))
       (funcall function))))

Very handy, doesn’t lock my repl, scratches my itch, and easy to write.

code snippet
lisp

Comments (1)

Permalink