View in EDS HTML Full Text PDF Full Text

A method for finding a least-cost wide path in raster space.

Saved in:
Bibliographic Details
Title: A method for finding a least-cost wide path in raster space.
Authors: Shirabe, Takeshi1 (AUTHOR) shirabe@kth.se
Source: International Journal of Geographical Information Science. Aug2016, Vol. 30 Issue 8, p1469-1485. 17p.
Subjects: Bit-mapped graphics, Computer graphics research, Digital image processing, Data modeling, Computer simulation
Abstract: Given a grid of cells each having an associated cost value, a raster version of the least-cost path problem seeks a sequence of cells connecting two specified cells such that its total accumulated cost is minimized. Identifying least-cost paths is one of the most basic functions of raster-based geographic information systems. Existing algorithms are useful if the path width is assumed to be zero or negligible compared to the cell size. This assumption, however, may not be valid in many real-world applications ranging from wildlife corridor planning to highway alignment. This paper presents a method to solve a raster-based least-cost path problem whose solution is a path having a specified width in terms of Euclidean distance (rather than by number of cells). Assuming that all cell values are positive, it does so by transforming the given grid into a graph such that each node represents a neighborhood of a certain form determined by the specified path width, and each arc represents a possible transition from one neighborhood to another. An existing shortest path algorithm is then applied to the graph. This method is highly efficient, as the number of nodes in the transformed graph is not more than the number of cells in the given grid and decreases with the specified path width. However, a shortcoming of this method is the possibility of generating a self-intersecting path which occurs only when the given grid has an extremely skewed distribution of cost values. [ABSTRACT FROM PUBLISHER]
Copyright of International Journal of Geographical Information Science is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 114819637
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: A method for finding a least-cost wide path in raster space.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Shirabe%2C+Takeshi%22">Shirabe, Takeshi</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> shirabe@kth.se</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22International+Journal+of+Geographical+Information+Science%22">International Journal of Geographical Information Science</searchLink>. Aug2016, Vol. 30 Issue 8, p1469-1485. 17p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Bit-mapped+graphics%22">Bit-mapped graphics</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+graphics+research%22">Computer graphics research</searchLink><br /><searchLink fieldCode="DE" term="%22Digital+image+processing%22">Digital image processing</searchLink><br /><searchLink fieldCode="DE" term="%22Data+modeling%22">Data modeling</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+simulation%22">Computer simulation</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Given a grid of cells each having an associated cost value, a raster version of the least-cost path problem seeks a sequence of cells connecting two specified cells such that its total accumulated cost is minimized. Identifying least-cost paths is one of the most basic functions of raster-based geographic information systems. Existing algorithms are useful if the path width is assumed to be zero or negligible compared to the cell size. This assumption, however, may not be valid in many real-world applications ranging from wildlife corridor planning to highway alignment. This paper presents a method to solve a raster-based least-cost path problem whose solution is a path having a specified width in terms of Euclidean distance (rather than by number of cells). Assuming that all cell values are positive, it does so by transforming the given grid into a graph such that each node represents a neighborhood of a certain form determined by the specified path width, and each arc represents a possible transition from one neighborhood to another. An existing shortest path algorithm is then applied to the graph. This method is highly efficient, as the number of nodes in the transformed graph is not more than the number of cells in the given grid and decreases with the specified path width. However, a shortcoming of this method is the possibility of generating a self-intersecting path which occurs only when the given grid has an extremely skewed distribution of cost values. [ABSTRACT FROM PUBLISHER]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of International Journal of Geographical Information Science is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=114819637
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1080/13658816.2015.1124435
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 17
        StartPage: 1469
    Subjects:
      – SubjectFull: Bit-mapped graphics
        Type: general
      – SubjectFull: Computer graphics research
        Type: general
      – SubjectFull: Digital image processing
        Type: general
      – SubjectFull: Data modeling
        Type: general
      – SubjectFull: Computer simulation
        Type: general
    Titles:
      – TitleFull: A method for finding a least-cost wide path in raster space.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Shirabe, Takeshi
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 08
              Text: Aug2016
              Type: published
              Y: 2016
          Identifiers:
            – Type: issn-print
              Value: 13658816
          Numbering:
            – Type: volume
              Value: 30
            – Type: issue
              Value: 8
          Titles:
            – TitleFull: International Journal of Geographical Information Science
              Type: main
ResultId 1