This might be done using GIS tools, where finding shortest paths between locations is a common task. But I can't help with details.
-Don -- Don MacQueen Lawrence Livermore National Laboratory 7000 East Ave., L-627 Livermore, CA 94550 925-423-1062 On 3/5/14 9:44 AM, "McCloskey, Bryan" <bmcclos...@usgs.gov> wrote: >Here is some example data (hopefully the monospace formatting is >preserved): > > a b c d e > - - - - - >1 | F | T | F | T | F | > - - - - - >2 | T | F | T | F | T | > - - - - - >3 | T | T | F | F | F | > - - - - - >4 | F | T | F | T | F | > - - - - - >5 | F | T | F | F | T | > - - - - - > >So, for cell b1, the shortest possible path to a true value in row 5 is >b1-a2-a3-b4-b5 (distance: sqrt(2) + 1 + sqrt(2) + 1). > >* Shortest paths are not necessarily unique, but I just need to find the >length. > >* If it's computationally hard to guarantee the absolute shortest path, I >can probably live with "nearly" shortest paths. > >* Paths can "backtrack", so the shortest path from cell e2 to row 4 is >e2-d1-c2-b3-b4-b5. > >I need to calculate the shortest path for all true cells to all rows >further down the matrix. I'm afraid I'm going to have to write some sort >of >recursive path-tracing algorithm, but I'm hoping there's a package already >in existence that accomplishes this already... > >-bryan > >On Tue, Mar 4, 2014 at 1:13 PM, McCloskey, Bryan ><bmcclos...@usgs.gov>wrote: > >> I have a binary rectangular T/F matrix; I need to be able to calculate >>the >> shortest path (i.e., Pythagorean distance) between a populated cell in >>row >> j and any populated cell in some row j+n. >> >> For instance, if I have a chessboard with random black/white square >> colors, I need the shortest distance (linear distance, not number of >>steps) >> for a king to get from a specified black space on the first row, to >>_any_ >> black space in a specified further row, traveling only on black spaces. >> >> Any idea? Thanks, >> >> -bryan >> > > [[alternative HTML version deleted]] > >______________________________________________ >R-help@r-project.org mailing list >https://stat.ethz.ch/mailman/listinfo/r-help >PLEASE do read the posting guide >http://www.R-project.org/posting-guide.html >and provide commented, minimal, self-contained, reproducible code. ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
