Efficient Calculation of Distance Transform on Discrete Global Grid Systems
Geospatial data analysis often requires the computing of a distance transform for a given vector feature. For instance, in wildfire management, it is helpful to find the distance of all points in an area from the wildfire’s boundary. Computing a distance transform on traditional Geographic Informati...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-05-01
|
| Series: | ISPRS International Journal of Geo-Information |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2220-9964/11/6/322 |
| _version_ | 1827660113132912640 |
|---|---|
| author | Meysam Kazemi Lakin Wecker Faramarz Samavati |
| author_facet | Meysam Kazemi Lakin Wecker Faramarz Samavati |
| author_sort | Meysam Kazemi |
| collection | DOAJ |
| description | Geospatial data analysis often requires the computing of a distance transform for a given vector feature. For instance, in wildfire management, it is helpful to find the distance of all points in an area from the wildfire’s boundary. Computing a distance transform on traditional Geographic Information Systems (GIS) is usually adopted from image processing methods, albeit prone to distortion resulting from flat maps. Discrete Global Grid Systems (DGGS) are relatively new low-distortion globe-based GIS that discretize the Earth into highly regular cells using multiresolution grids. In this paper, we introduce an efficient distance transform algorithm for DGGS. Our novel algorithm heavily exploits the hierarchy of a DGGS and its mathematical properties and applies to many different DGGSs. We evaluate our method by comparing its speed and distortion with the distance transform methods used in traditional GIS and general 3D meshes. We demonstrate that our method is efficient and has minimal distortion. |
| first_indexed | 2024-03-09T23:37:30Z |
| format | Article |
| id | doaj.art-e5417b010769402c9fd95f094d29ef52 |
| institution | Directory Open Access Journal |
| issn | 2220-9964 |
| language | English |
| last_indexed | 2024-03-09T23:37:30Z |
| publishDate | 2022-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | ISPRS International Journal of Geo-Information |
| spelling | doaj.art-e5417b010769402c9fd95f094d29ef522023-11-23T16:58:46ZengMDPI AGISPRS International Journal of Geo-Information2220-99642022-05-0111632210.3390/ijgi11060322Efficient Calculation of Distance Transform on Discrete Global Grid SystemsMeysam Kazemi0Lakin Wecker1Faramarz Samavati2Department of Computer Science, University of Calgary, Calgary, AB T2N 1N4, CanadaDepartment of Computer Science, University of Calgary, Calgary, AB T2N 1N4, CanadaDepartment of Computer Science, University of Calgary, Calgary, AB T2N 1N4, CanadaGeospatial data analysis often requires the computing of a distance transform for a given vector feature. For instance, in wildfire management, it is helpful to find the distance of all points in an area from the wildfire’s boundary. Computing a distance transform on traditional Geographic Information Systems (GIS) is usually adopted from image processing methods, albeit prone to distortion resulting from flat maps. Discrete Global Grid Systems (DGGS) are relatively new low-distortion globe-based GIS that discretize the Earth into highly regular cells using multiresolution grids. In this paper, we introduce an efficient distance transform algorithm for DGGS. Our novel algorithm heavily exploits the hierarchy of a DGGS and its mathematical properties and applies to many different DGGSs. We evaluate our method by comparing its speed and distortion with the distance transform methods used in traditional GIS and general 3D meshes. We demonstrate that our method is efficient and has minimal distortion.https://www.mdpi.com/2220-9964/11/6/322distance transformDiscrete Global Grid SystemsGeographical Information Systems |
| spellingShingle | Meysam Kazemi Lakin Wecker Faramarz Samavati Efficient Calculation of Distance Transform on Discrete Global Grid Systems ISPRS International Journal of Geo-Information distance transform Discrete Global Grid Systems Geographical Information Systems |
| title | Efficient Calculation of Distance Transform on Discrete Global Grid Systems |
| title_full | Efficient Calculation of Distance Transform on Discrete Global Grid Systems |
| title_fullStr | Efficient Calculation of Distance Transform on Discrete Global Grid Systems |
| title_full_unstemmed | Efficient Calculation of Distance Transform on Discrete Global Grid Systems |
| title_short | Efficient Calculation of Distance Transform on Discrete Global Grid Systems |
| title_sort | efficient calculation of distance transform on discrete global grid systems |
| topic | distance transform Discrete Global Grid Systems Geographical Information Systems |
| url | https://www.mdpi.com/2220-9964/11/6/322 |
| work_keys_str_mv | AT meysamkazemi efficientcalculationofdistancetransformondiscreteglobalgridsystems AT lakinwecker efficientcalculationofdistancetransformondiscreteglobalgridsystems AT faramarzsamavati efficientcalculationofdistancetransformondiscreteglobalgridsystems |