Joachim Breitner's Homepage
For an upcoming introductory Haskell talk of mine (next Tuesday in Karlsruhe – please come and join if you will) I was looking into data visualization as a example application. With libraries like gloss, getting some nice vector graphics up and running within one talk is quite possible.
For some reason, I want to arrange multiple circles of varying size so that they do not overlap and use as little space as possible. My first approach was to use general purpose optimizers such as cmaes, Numeric.GSL.Minimization from the hmatrix package and force-layout. I especially liked the interface of cmaes, which is able to minimize a function of, say, type
[(String, Double, Double)] -> Double by automatically finding the values of type
Double in the input, as described by Takayuki Muranushi. That would have looked great in the talk. Unfortunately, none of these libraries gave sufficient good results in a reasonable amount of time for this problem.
I then reviewed some of the academic literature on the circle packing problem and there were some algorithms proposed, but no simple one and none of the papers had a concise pseudo-code description that I could transfer to Haskell.
So eventually I set out to implement a relatively dump and slow greedy algorithm myself: I place one circle after another, starting with the largest, and among the valid positions where a new circle touches two already placed circles, I choose the positions closest to the center of mass. The result, available in the circle-packing package, looks surprisingly well, here visualized using the diagrams library (See the documentation of Optimisation.CirclePacking for the code used to generate that image):
Oh, and while I am talking about neat tricks: You can put vector graphics in your haddock documentation, as I have done for Optimisation.CirclePacking, using the syntax