Drawing the maximum-area rectangle in a non-convex polygon
I've implemented this as a package now. Its on my gitlab account: https://gitlab.com/b-rowlingson/maxrectangle and you can install it with devtools. And here's the example Create a new JS context: ##' ctx = initjs() Make a polygon: ##' th = seq(0,2*pi,len=11)[-11] ##' r = runif(10) ##' xy = cbind(r*cos(th), r*sin(th)) ##' xy = rbind(xy, xy[1,]) Plot it: ##' plot(xy, type="l") Call the JS: ##' lr = find_lr(ctx, xy) Convert the return value and plot: ##' pp = plotrect(lr[[1]]) ##' lines(pp) At the moment the options to the JS, which sets things like number of iterations and thresholds for deciding its found the biggest rectangle, are ignored. So often you'll get a rectangle and go "Hey, it could be a bit bigger!" which you might not get if you could tweak the options a bit. If anyone wants to write code to pass the options into the JS, pull requests are welcome. I'm not sure what the license on the coffee script code is, I think its BSD, which means its okay to use this like this. Will investigate. Incidentally, the V8 package is a very slick interface to JS from R. Impressed. Barry On Wed, Apr 13, 2016 at 12:51 PM, Barry Rowlingson
<b.rowlingson at lancaster.ac.uk> wrote:
On Tue, Apr 12, 2016 at 10:48 PM, Tiernan Martin <tiernanmartin at gmail.com> wrote:
Hi Barry ? Are you referring to the javascript code detailed here: http://d3plus.org/assets/posts/largestRect/src/largestRect.coffee ? I don't know much about running javascript in R, but I would be willing to give it a shot for this project. However, since this would be my first time trying to run JS code in R (and given that the algorithm itself isn't exactly a simple one) I thought I would start by querying the R user community to see if there's already an R implementation of something similar. It had also occurred to me that I could attempt to reimplement the JS code using R functions, but that project quickly took me beyond my R skill set.
Check out the V8 and js packages. That script you linked to is actually CoffeeScript, but that's a thin shell around Javscript and "transpiling" to JS is covered in the vignettes of the V8 and js packages somewhere. Then all you need to do (hah!) is load the d3 javascript library into a V8 context, pass some parameters, and run... Simple... ummm... maybe.
It certainly seems to be the sort of spatial analysis problem that could be applicable to lots of different projects, so I'm hoping to get some feedback from folks with deeper understanding of programming and R ? or simply to have someone point out a nicely packaged set of functions that could do this analysis.
I've had a quick look at the CoffeeScript and while it could be converted to R there's a lot of looping and I suspect it might be painfully slow unless you spend lots of time to consider the algorithm so you can write it in properly idiomatic R. It might even benefit you to rewrite it in C or C++.... Barry