[R-sig-Geo] determining suitable lakes for landing

[Barry Rowlingson]

On Mon, Jul 30, 2012 at 1:11 PM,
Bastien.Ferland-Raymond at mrnf.gouv.qc.ca
<Bastien.Ferland-Raymond at mrnf.gouv.qc.ca> wrote:
> Dear R gurus,
>
> I'm facing a challenge that I have a good feeling you could help me with.  So far I'm stuck right at the beginning so I don't have any example to show you.  Here is what I'm trying to do:
>
> I have a polygon shape of lakes for which I have to be able to automatically determine if they are suitable (large enough) for a plane to land.  To be suitable, we must be able to fit a rectangle of dimension 50m x 1500m in the lake without it touching any lake contour.  Of course, the rectangle can be in any orientation in the lake, which makes the test a little harder.
>
> I can easily eliminate all the small lakes by using the extent and Pythagorean.  For exemple:
>
>     1500 > sqrt(sum((bbox(lake)[,2] - bbox(lake)[,1])^2))  # measure the diagonal of the bbox of the lake (mtm projection)
>
> All those lake are definitely too small for a plane to land, however not all the lakes that are bigger than that will be large enough.
>
> Anybody have an idea how to place the rectangle and discriminate those lakes?
>
> Thanks for your help!

 Fun problem...

 It seems there are algorithms for finding the maximum area rectangle
[http://www.sciencedirect.com/science/article/pii/S0096300312003207]
but in your case the max area rectangle could be 49m x 10000m, and the
lake could have a 50mx1500m finger poking out of it. The max area
rectangle would then not be good enough to land in, but the lake would
actually be okay.

 But if the max area rectangle is > 50m x > 1500m then you've got one
you can land in, but its not a necessary condition....

 Some kind of heuristic approach of dropping 50mx1500m rectangles on
the lake area and testing might work - you'd have to randomise the
location and orientation and vary the randomness by how much the
rectangle overlaps, some kind of simulated annealing approach perhaps.
Again, its not guaranteed to work due to its heuristic approach -
eventually your simulated annealing has to stop and it might not have
found a solution... In the pathological case I mentioned above it
might have trouble...

 I think that if a polygon contains an NxM rectangle then that
rectangle can be shifted to touch two points of the polygon, so maybe
you can reduce the problem to rectangles that touch at two points -
that might help any heuristic algorithms...

 I wonder if everyone on R-sig-geo is now sliding bus tickets around
on pieces of paper like me...

Barry