[R-sig-Geo] Drawing the maximum-area rectangle in a non-convex polygon

[Barry Rowlingson]

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