Last Resort Software

The previous two posts showed examples of a simple circle packing algorithm using the packcircles package (available from CRAN and GitHub ). The algorithm involved iterative pair-repulsion to jiggle the circles until (hopefully) a non-overlapping arrangement emerged. In this post we'll look an alternative approach. An algorithm to find an arrangement of circles satisfying a prior specification of circle sizes and tangencies was described by Collins and Stephenson in their 2003 paper in Computation Geometry Theory and Applications. A version of their algorithm was implemented in Python by David Eppstein as part of his PADS library (see CirclePack.py ). I've now ported David's version to R/Rcpp and included it in the packcircles package. In the figure below, the graph on the left represents the desired pattern of circle tangencies: e.g. circle 7 should touch all of, and only, circles 1, 2, 6 and 8. Circles 5, 7, 8 and 9 are internal , while the remaining circles are exter...

After the previous post on the packcircles package for R someone suggested it would be useful to be able to fix the position of selected circles. As a first attempt, I've added an optional weights argument to the circleLayout function. Weights can be in the range 0-1 inclusive, where a weight of 0 prevents a circle from moving, while a weight of 1 allows full movement. The updated code is at GitHub . Here's an example where the largest of a set of initially overlapping circles is fixed in place: And here is the code for the example: library(packcircles) library(ggplot2) library(gridExtra) # Generate some random overlapping circles ncircles

Back in 2010 I posted some R code for circle packing . Now, just five years later, I've ported the code to Rcpp and created a little package which you can find at GitHub . The main function is circleLayout which takes a set of overlapping circles and tries to find a non-overlapping arrangement for them. Here's an example: And here's the code: # Create some random circles, positioned within the central portion # of a bounding square, with smaller circles being more common than # larger ones. ncircles

Some time ago I wrote an R function to fit an ellipse to point data, using an algorithm developed by Radim Halíř and Jan Flusser 1 in Matlab, and posted it to the r-help list . The implementation was a bit hacky, returning odd results for some data. A couple of days ago, an email arrived from John Minter asking for a pointer to the original code. I replied with a link and mentioned that I'd be interested to know if John made any improvements to the code. About ten minutes later, John emailed again with a much improved version ! Not only is it more reliable, but also more efficient. So with many thanks to John, here is the improved code: fit.ellipse 0)] f Next here is a utility function which takes a fitted ellipse and returns a matrix of vertices for plotting: get.ellipse And finally, some demo code from John: create.test.ellipse 1 Halíř R., Flusser J.: Numerically stable direct least squares fitting of ellipses. In: Proceedings of the 6th International Confere...

A recent upgrade of NetBeans from version 7.1 to 7.2 seemed to cause problems with Maven multi-module projects. Normally, a newly created class in one Maven project module will be instantly visible to other modules open in the IDE, at least for editing purposes. But after the upgrade I started to see "cannot find symbol" errors in the IDE for such new classes. Despite this, a full build of the project would succeed. Googling for an answer drew a blank. The usual kludge fixes such as deleting the NetBeans cache (for NetBeans 7.2 on OSX this seems to have moved from ~/.netbeans to ~/Library/Application Support/Netbeans) and re-indexing my local repo didn't make any difference. Despair loomed. Happily, I stumbled across the cause of the problem after only a moderate amount of pulling of hair and gnashing of teeth. My Maven settings.xml file included this section... <profiles> <profile> <id>netbeans-ide</id> <...

I've been working on a small Java application with a colleague to simulate animal movements and look at the efficiency of different survey methods. It uses the GeoTools library to support map projections and shapefile output. GeoTools is great but comes at a cost in terms of size: the jar for our little application alone is less than 50kb but bundling it with GeoTools and its dependencies blows that out to 20Mb. The application code has been changing on a daily basis as we explore ideas, add features and fix bugs. Working with my colleague at a distance, over a fairly feeble internet connection, I wanted to package the static libraries and the volatile application into separate jars so that he only needed to download the former once (another option would have been for my colleague to set up a local Maven repository but for various reasons this was impractical). A slight complication with bundling GeoTools modules into a single jar (aka uber-jar) is that individual modules make ext...

For a current project I needed a polygon smoothing algorithm in Java that: generated a curve passing through all polygon vertices had some way of controlling tightness of fit to the polygon fell within the domain of my very limited mathematical grasp Luckily for me, Maxim Shemanarev had not only worked out a Bezier curve algorithm that satisfied all of the above, but he also published a beautifully clear explanation of how it works note 1 . Maxim also provided some illustrative C code, but my Java implementation below is an independent effort (ie. all mistakes are my fault). It uses geometry objects from the JTS library . Below is an example of the algorithm in action. The original polygon is in black. The smoothed polygon composed of fitted cubic Bezier segments is in blue. The red points and lines indicate positions of the Bezier control points calculated with Maxim's algorithm. There are a pair of control points for each vertex of the input polygon. The tightness of fit of th...