Implementation of CA-models of physical processes on triangulation grids

Authors

  • Domasevich M.A. Kuban State University, Krasnodar, Российская Федерация
  • Rubtsov S.E. Kuban State University, Krasnodar, Российская Федерация
  • Pavlova A.V. Kuban State University, Krasnodar, Российская Федерация

UDC

510.67:554

DOI:

https://doi.org/10.31429/vestnik-17-3-13-21

Abstract

The application of cellular automata (CA) on triangulation grids is a promising area of research in the world of CA, that can open new possibilities in the modeling of surface processes. In the paper we demonstrate an approach to the construction of triangulation grids that approximate real terrain fragments, presented in the form of a heightmap image in PNG format. The constructed grid can approximate the selected surface with the required accuracy, thereby making it possible to use the features of the modeled object geometry in a mathematical model, the implementation of which is a cellular automaton with given transition rules. For the constructed triangulation grid, it is possible to generate and attach various forms of metadata based on the corresponding maps that match in scale with the elevation map, or are related to it. For example, we can use rainfall maps, forest maps, or various temperature maps to provide the appropriate metadata needed to model the required process. The described approach is applicable for construction of Boolean, integer CA and also cellular automata using the real alphabet on triangulation grids. The paper presents the results of testing for the constructed spatial cellular automata that simulate naive diffusion and liquid spill on the presented model triangulation grid. The developed visualization mechanisms allow us to view the simulated objects from different angles.

Keywords:

triangulation grid, height map, cellular automata, cellular automata simulation, diffusion, fluid spill

Acknowledgement

Работа выполнена при поддержке РФФИ и администрации Краснодарского края (19-41-230005).

Author Infos

Mikhail A. Domasevich

студент магистратуры кафедры математического моделирования Кубанского государственного университета

e-mail: kmm@fpm.kubsu.ru

Sergei E. Rubtsov

канд. физ.-мат. наук, доцент кафедры математического моделирования Кубанского государственного университета

e-mail: rub_serg@mail.ru

Alla V. Pavlova

д-р физ.-мат. наук, профессор кафедры математического моделирования Кубанского государственного университета

e-mail: pavlova@math.kubsu.ru

References

  1. Alexandridis, A. et al. A cellular automata model for forest fire spread prediction: The case of the wildfire that swept through Spetses Island in 1990. Applied Mathematics and Computation, 2008, vol. 204, iss. 1, pp. 191–201.
  2. Von Neumann, J. Theory of self-reproducing automata. Urbana: University of Illinois Press, 1966. 302 p.
  3. Toffolli, T., Margolus, N. Cellular Automata Machines. USA: MIT Press, 1987. 279 p.
  4. Bandman, O. Comparative Study of Cellular automata Diffusion Models. Lecture Notes in Computer Science, 1999, vol. 1662, pp. 395–399.
  5. Bode, M. Interaction of Dissipative Solitons: Particle-Like Behavior of Localized structures in a Three-Component Reaction-Diffusion System. Physica D, 2002, vol. 161, pp. 45–66.
  6. Evseev, A.A., Nechaeva, O.I. Kletochno-avtomatnoe modelirovanie diffuzionnyh processov na triangulyacionnyh setkah [Cellular automaton modeling of diffusion processes on triangulation grids]. Prikladnaya diskretnaya matematika [Applied Discrete Mathematics], 2009, no. 4, pp. 72–83. (In Russian)
  7. Pavlova, A.V., Rubtsov, S.E., Rodionov, P.R. Ispol'zovanie kletochno-avtomatnyh modelej v issledovanii rasprostraneniya pozhara pri razlive nefteproduktov na poverhnosti pochv [Using of cellular automata models in the study of fire spread during the spill of oil products on the surface of soils]. Zashchita okruzhayushchej sredy v neftegazovom komplekse [Environmental Protection in the Oil and Gas Complex], 2020, no. 1, pp. 54–59. (In Russian)
  8. Vitvitsky, A.A. Kletochnye avtomaty s dinamicheskoj strukturoj dlya modelirovaniya rosta biologicheskih tkanej [Cellular automata with dynamic structure to simulate the growth of biological tissues]. Sibirskij zhurnal vychislitel'noj matematiki [Siberian Journal of Computational Mathematics], 2014, vol. 17, no. 4, pp. 315–327. (In Russian)
  9. Matyushkin, I.V., Zapletina, M.A. Obzor po tematike kletochnyh avtomatov na baze sovremennyh otechestvennyh publikacij [Cellular automata review based on modern domestic publication]. Komp'yuternye issledovaniya i modelirovanie [Computer research and modeling], 2019, vol. 11, no. 1, pp. 9–57. (In Russian)
  10. Balk, E.A., Klyuchkarev, P.G. Issledovanie harakteristik lavinnogo effekta obobshchennyh kletochnyh avtomatov na osnove grafom malogo razmera [Small diameter Graf-based Investigation of Avalanche Effect Characteristic of Generalized Cellular Automata]. Nauka i obrazovanie: nauchnoe izdanie MGTU im. N.G. Baumana [Science and Education of Bauman MGSU], 2016. no. 4, pp. 92–105. (In Russian)
  11. Aristov, A.O. Ob elementah kvazikletochnyh setej [About structural elements of quasi cellular nets]. Gornyj informacionno-analiticheskij byulleten' [Mining informational and analytical bulletin], 2013, no. 11, pp. 322–331. (In Russian)
  12. Skvortsov, A.V. Obzor algoritmov postroeniya triangulyacii Delone [A review of algorithms for constructing Delaunay triangulation]. Vychislitel'nye metody i programmirovanie [Computational methods and programming], 2002, vol. 3, no. 1, pp. 14–39. (In Russian)
  13. Joe, B. Construction of three-dimensional Delaunay triangulations using local transformations. Computer Aided Geometric Design, 1991, vol. 8, pp. 123–142.
  14. Lohner, R. Generation of three-dimensional unstructured grids by the advancing front method. In: Proc. of the 26th AIAA Aerospace Sciences Meeting. Nevada, 1988. 287 p.
  15. Dyn, N., Lyche, T., Schumaker, L.L. Optimizing 3d triangulations using discrete curvature analysis. Mathematical Methods in CAGD, Oslo, 2000. Nashville, TN, Vanderbilt University Press. 2001.
  16. Bandman, O.L. Invarianty kletochno-avtomatnyh modelej reakcionno-diffuzionnyh processov [Invariants Cellular Automata models of reaction-diffusion processes]. Prikladnaja diskretnaja matematika [Applied discrete mathematics], 2012, no. 3, pp. 108–120. (In Russian)

Downloads

Issue

2020. Vol. 17. No. 3

Section

Mathematics

Pages

13-21

Submitted

2020-09-16

Published

2020-09-28

How to Cite

Domasevich M.A., Rubtsov S.E., Pavlova A.V. Implementation of CA-models of physical processes on triangulation grids. Ecological Bulletin of Research Centers of the Black Sea Economic Cooperation, 2020, vol. 17, no. 3, pp. 13-21. DOI: https://doi.org/10.31429/vestnik-17-3-13-21 (In Russian)

Copyright (c) 2020 Domasevich M.A., Rubtsov S.E., Pavlova A.V.

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.