×

Modeling wildfire propagation with Delaunay triangulation and shortest path algorithms. (English) Zbl 1244.90150

Summary: A methodology for modeling surface wildfire propagation through a complex landscape is presented. The methodology utilizes a Delaunay triangulation to represent surface fire spread within the landscape. A procedure to construct the graph and estimate the rate of spread along the edges of a network is discussed. After the Delaunay data structure is constructed, a two pass shortest path algorithm is incorporated to estimate the minimum travel time paths and fire arrival times. Experimental results are also included.

MSC:

90B90 Case-oriented studies in operations research
90C35 Programming involving graphs or networks
65D17 Computer-aided design (modeling of curves and surfaces)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R.; Magnanti, T.; Orlin, J., Network Flows: Theory, Algorithms, and Applications (1993), Prentice-Hall, Inc.: Prentice-Hall, Inc. Upper Saddle River, NJ, USA
[2] Albini, F.A., 1976. Estimating wildfire behavior and effectsn++. Technical Report, INT-30, USDA Forest Service General Technical Report.; Albini, F.A., 1976. Estimating wildfire behavior and effectsn++. Technical Report, INT-30, USDA Forest Service General Technical Report.
[3] Anderson, H.E., 1982. Aids to determine fuel models for estimating fire behavior. General Technical Report, INT-122, US Department of Agriculture, Forest Service, Intermountain Forest and Range Experiment Station.; Anderson, H.E., 1982. Aids to determine fuel models for estimating fire behavior. General Technical Report, INT-122, US Department of Agriculture, Forest Service, Intermountain Forest and Range Experiment Station.
[4] Bevins, C., 2004. fireLib: A C function library for predicting wildland fire behavior using the BEHAVE algorithms. URL http://www.fire.org; Bevins, C., 2004. fireLib: A C function library for predicting wildland fire behavior using the BEHAVE algorithms. URL http://www.fire.org
[5] Blanchette, J.; Summerfield, M., C++ GUI Programming with Qt 4 (2008), Prentice Hall Press: Prentice Hall Press Upper Saddle River, NJ, USA
[6] Bleiweiss, A., 2008. GPU accelerated pathfinding. In: Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware. Eurographics Association, pp. 65-74.; Bleiweiss, A., 2008. GPU accelerated pathfinding. In: Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware. Eurographics Association, pp. 65-74.
[7] Buluç, A.; Gilbert, J.; Budak, C., Solving path problems on the GPU, Parallel Computing, 36, 5-6, 241-253 (2010) · Zbl 1204.68043
[8] Burgan, R.E., Rothermel, R.C., 1984. BEHAVE: Fire behavior prediction and fuel modeling system – fuel subsystem. Technical Report INT-167, US Department of Agriculture, Forest Service, Intermountain Forest and Range Experiment Station.; Burgan, R.E., Rothermel, R.C., 1984. BEHAVE: Fire behavior prediction and fuel modeling system – fuel subsystem. Technical Report INT-167, US Department of Agriculture, Forest Service, Intermountain Forest and Range Experiment Station.
[9] Catchpole, E. A.; de Mestre, N. J.; Gill, A. M., Intensity of fire at its perimeter, Australian Forest Research, 12, 47-54 (1982)
[10] Catchpole, E. A.; Hatton, T. J.; Catchpole, W. R., Fire spread through nonhomogeneous fuel modelled as a markov process, Ecological Modelling, 48, 101-112 (1989)
[11] Clark, K.H., Patterson, W.A., 2003. Fire management plan for montague plain wildlife management area. Technical Report, Department of Natuaral Resources Conservation, University of Massachusetts, Amherst.; Clark, K.H., Patterson, W.A., 2003. Fire management plan for montague plain wildlife management area. Technical Report, Department of Natuaral Resources Conservation, University of Massachusetts, Amherst.
[12] Clarke, K.; Olsen, G., Refining a cellular automaton model of wildfire propagation and extinction, GIS and Environmental Modeling: Progress and Research Issues, 333-338 (1996)
[13] Coleman, J., Sullivan, A., 1995. SiroFire. the CSIRO Bushfire Spread Simulator. In: Proceedings of Inst Forest Aust 16th Biennial Conference Canberra.; Coleman, J., Sullivan, A., 1995. SiroFire. the CSIRO Bushfire Spread Simulator. In: Proceedings of Inst Forest Aust 16th Biennial Conference Canberra.
[14] Countryman, C.M., 1972. The fire environment concept. Pacific Southwest Forest and Range Experiment Station.; Countryman, C.M., 1972. The fire environment concept. Pacific Southwest Forest and Range Experiment Station.
[15] Cova, T. J.; Philip, E.; Dennison, T. H.K.; Moritz, M. A., Setting wildfire evacuation trigger points using fire spread modeling and GIS, Transactions in GIS, 9, 4, 603-617 (2005)
[16] Duveneck, M., 2005. Characterizing canopy fuels as they affect fire behavior in pitch pine (Pinus rigida) P. Mill. Master’s thesis, University of Massachusetts, Amherst, USA.; Duveneck, M., 2005. Characterizing canopy fuels as they affect fire behavior in pitch pine (Pinus rigida) P. Mill. Master’s thesis, University of Massachusetts, Amherst, USA.
[17] Fabri, A.; Pion, S., CGAL: The computational geometry algorithms library, (Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (2009), ACM), 538-539
[18] Finney, M., 2006. An overview of FlamMap fire modeling capabilities. In: Andrews, PL., Butler, BW., compilers. Fuels management-how to measure success: Conference Proceedings. USDA Forest Service, Rocky Mountain Research Station Proceedings. USDA Forest Service Proceedings RMRS-P-41. pp. 213-220.; Finney, M., 2006. An overview of FlamMap fire modeling capabilities. In: Andrews, PL., Butler, BW., compilers. Fuels management-how to measure success: Conference Proceedings. USDA Forest Service, Rocky Mountain Research Station Proceedings. USDA Forest Service Proceedings RMRS-P-41. pp. 213-220.
[19] Finney, M. A., Fire growth using minimum travel time methods, Canadian Journal of Forest Research, 32, 8, 1420 (2002)
[20] Fons, W. T., Analysis of fire spread in light forest fuels, Journal of Agricultural Research, 72, 3, 93-121 (1946)
[21] Fujioka, F. M., Estimating wildland fire rate of spread in a spatially nonuniform environment, Forest Science, 31, 1, 21-29 (1985)
[22] Garcia-Diaz, A.; MacGregor Smith, J., Facilities Planning and Design (2007), Prentice Hall
[23] Hargrove, W.; Gardner, R.; Turner, M.; Romme, W.; Despain, D., Simulating fire patterns in heterogeneous landscapes, Ecological Modelling, 135, 2-3, 243-263 (2000)
[24] Harish, P.; Narayanan, P., Accelerating large graph algorithms on the GPU using CUDA, High Performance Computing-HiPC, 2007, 197-208 (2007)
[25] Kourtz, P.H., Nozaki, S., O’Regan, W.G., 1977. Forest fires in a computer: A model to predict the perimeter location of a forest fire. Information Report FF-X-65, Fisheries and Environment Canada.; Kourtz, P.H., Nozaki, S., O’Regan, W.G., 1977. Forest fires in a computer: A model to predict the perimeter location of a forest fire. Information Report FF-X-65, Fisheries and Environment Canada.
[26] Mark, D., Computer analysis of topography: A comparison of terrain storage methods, Geografiska Annaler. Series A. Physical Geography, 57, 3, 179-188 (1975)
[27] McArthur, A., 1966. Weather and grassland fire behaviour. Forest Research Institute, Forestry and Timber Bureau of Australia.; McArthur, A., 1966. Weather and grassland fire behaviour. Forest Research Institute, Forestry and Timber Bureau of Australia.
[28] National Interagency Fire Center, 2006. Wildland Fire Statistics:Historically Significant Wildland Fires (1960-2006). URL http://www.nifc.gov/stats/historicalstats.html; National Interagency Fire Center, 2006. Wildland Fire Statistics:Historically Significant Wildland Fires (1960-2006). URL http://www.nifc.gov/stats/historicalstats.html
[29] National Interagency Fire Center, 2007. Wildland Fire Statistics 1960-2007. URL http://www.nifc.gov/stats/wildlandfirestats.html; National Interagency Fire Center, 2007. Wildland Fire Statistics 1960-2007. URL http://www.nifc.gov/stats/wildlandfirestats.html
[30] Noble, I.; Bary, G.; Gill, A., McArthur’s fire-danger meters expressed as equations, Australian Journal of Ecology, 5, 201-203 (1980)
[31] Okabe, A.; Boots, B.; Sugihara, K., Spatial tessellations: Concepts and applications of Voronoi diagrams (1992), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York, NY, USA · Zbl 0877.52010
[32] Pastor, E.; Zarate, L.; Planas, E.; Arnaldos, J., Mathematical models and calculation systems for the study of wildland fire behaviour, Progress in Energy and Combustion Science, 29, 2, 139-153 (2003)
[33] Perry, G. L., Current approaches to modelling the spread of wildland fire: A review, Progress in Physical Geography, 22, 2, 222-224 (1998)
[34] Richards, G. D., A general mathematical framework for modelling two-dimensional wildland fire spread, International Journal of Wildland Fire, 5, 2 (1995), pp. 63n++72
[35] Richards, G. D., The mathematical modelling and computer simulation of wildland fire perimeter growth over a 3-dimensional surface, International Journal of Wildland Fire, 9, 3, 213-221 (1999)
[36] Richards, G. D.; Bryce, R. W., A computer algorithm for simulating the spread of wildland fire perimeters for heterogeneous fuel and meteorological conditions, International Journal of Wildland Fire, 5, 2, 73-79 (1995)
[37] Rothermel, R.C., 1972. A Mathematical Model for Predicting Fire Spread in Wildland Fuels. Intermountain Forest & Range Experiment Station, Forest Service, US Department of Agriculture.; Rothermel, R.C., 1972. A Mathematical Model for Predicting Fire Spread in Wildland Fuels. Intermountain Forest & Range Experiment Station, Forest Service, US Department of Agriculture.
[38] Ruppert, J., A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation, Journal of Algorithms, 18, 3, 548-585 (1995) · Zbl 0828.68122
[39] Scott, J., Burgan, R., 2005. Standard fire behavior fuel models: A comprehensive set for use with Rothermeln++s surface fire spread model. Gen. Tech. Rep. RMRS-GTR-153. Fort Collins, CO: US Department of Agriculture, Forest Service, Rocky Mountain Research Station 72.; Scott, J., Burgan, R., 2005. Standard fire behavior fuel models: A comprehensive set for use with Rothermeln++s surface fire spread model. Gen. Tech. Rep. RMRS-GTR-153. Fort Collins, CO: US Department of Agriculture, Forest Service, Rocky Mountain Research Station 72.
[40] Shewchuk, J., Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, Applied Computational Geometry: Towards Geometric Engineering, 1148, 203-222 (1996)
[41] Shewchuk, J., Delaunay refinement algorithms for triangular mesh generation, Computational Geometry: Theory and Applications, 22, 1-3, 21-74 (2002) · Zbl 1016.68139
[42] Siek, J.; Lee, L.; Lumsdaine, A., The Boost Graph Library (2002), Addison-Wesley: Addison-Wesley Boston, MA
[43] Sud, A.; Andersen, E.; Curtis, S.; Lin, M.; Manocha, D., Real-time path planning for virtual agents in dynamic environments, (2007 IEEE Virtual Reality Conference (2007), IEEE), 91-98
[44] Tymstra, C., Bryce, R., Wotton, B., Armitage, O., 2009. Development and structure of Prometheus: The Canadian wildland fire growth simulation model. Northern Forestry Centre.; Tymstra, C., Bryce, R., Wotton, B., Armitage, O., 2009. Development and structure of Prometheus: The Canadian wildland fire growth simulation model. Northern Forestry Centre.
[45] Van Wagner, C. E., A simple fire growth-model, The Forestry chronicle, 45, 103-104 (1969)
[46] Vasconcelos, M.; Guertin, D., FIREMAP-simulation of fire growth with a geographic information system, International Journal of Wildland Fire, 2, 2, 87-96 (1992)
[47] Wallace, G., A numerical fire simulation model, International Journal of Wildland Fire, 3, 2, 111-116 (1993)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.