Skip to content

Drawing the maximum-area rectangle in a non-convex polygon

5 messages · Tiernan Martin, Barry Rowlingson

Tiernan Martin
# 
Does anyone know if there is an R package out there with an algorithm which
finds the maximum-area rectangle that can fit within a non-convex polygon?
I have Googled, searched the R Sig Geo archives, and created a post on the
GIS Stackexchange to no avail.

Here is an example of the type of output I am looking for:
http://d3plus.org/assets/posts/largestRect/img/solution.png

As you can probably infer from the image, the algorithm searches for the
rectangle with the largest area that will fit within the boundary of the
non-convex polygon. My project will be applying this analysis to a set of
parcels (aka plots, plats, or cadastres) in order to estimate the footprint
of a largest rectangular building that could be built on each parcel. The
image linked above comes from the following post which showcases the type
of algorithm that would be useful for my project:
http://d3plus.org/blog/behind-the-scenes/2014/07/08/largest-rect/

Is there an existing R package that I could use to conduct such an analysis
of several non-convex polygon? Or perhaps a set of functions from a
combination of packages?

Thank you in advance,

Tiernan

PS ? here's a link to my (very similarly worded) SO post:
http://gis.stackexchange.com/questions/186881/is-there-an-r-package-for-finding-the-largest-rectangle-in-a-non-convex-polygon
Barry Rowlingson
# 
Could you simply use the Javascript code in that web page via one of
the R-Javascript interface packages?
On Tue, Apr 12, 2016 at 8:42 PM, Tiernan Martin <tiernanmartin at gmail.com> wrote:
Tiernan Martin
# 
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.

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.

Thanks for your advice, Barry!



On Tue, Apr 12, 2016 at 1:57 PM Barry Rowlingson <
b.rowlingson at lancaster.ac.uk> wrote:

            

      
      
      
    

        

      
      
    

            

      
      
      
    

        

  
  


  


      

    

    

      
      

        


  

        

      Barry Rowlingson
    

    

      
      #
    

  


  

      
On Tue, Apr 12, 2016 at 10:48 PM, Tiernan Martin

        
<tiernanmartin at gmail.com> wrote:

            

      
      
      
    

        
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.

            

      
      
      
    

        
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

  
  


  


      

    

    
1 day later

    

      
      

        


  

        

      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: