Implementation of CA-models of physical processes on triangulation grids

Authors

  • Domasevich M.A. Kuban State University, Krasnodar, Russian Federation
  • Rubtsov S.E. Kuban State University, Krasnodar, Russian Federation
  • Pavlova A.V. Kuban State University, Krasnodar, Russian Federation

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

Funding information

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

Author info

  • Mikhail A. Domasevich

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

  • Sergei E. Rubtsov

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

  • Alla V. Pavlova

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

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. P. 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. P. 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. P. 45–66.
  6. Евсеев А.А., Нечаева О.И. Клеточно-автоматное моделирование диффузионных процессов на триангуляционных сетках // Прикладная дискретная математика. 2009. № 4. С. 72–83. [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. Павлова А.В., Рубцов С.Е., Родионов П.Р. Использование клеточно-автоматных моделей в исследовании распространения пожара при разливе нефтепродуктов на поверхности почв // Защита окружающей среды в нефтегазовом комплексе. 2020. № 1. С. 54–59. [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. Матюшкин И.В., Заплетина М.А. Обзор по тематике клеточных автоматов на базе современных отечественных публикаций // Компьютерные исследования и моделирование. 2019. Т. 11, № 1. С. 9–57. [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. Балк Е.А., Ключкарев П.Г. Исследование характеристик лавинного эффекта обобщенных клеточных автоматов на основе графов малого размера // Наука и образование: научное издание МГТУ им. Н.Г. Баумана. 2016. № 4. С. 92–105. [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. Витвицкий А.А. Клеточные автоматы с динамической структурой для моделирования роста биологических тканей // Сибирский журнал вычислительной математики. 2014. Т. 17, № 4. С. 315–327. [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. Аристов А.О. Об элементах квазиклеточных сетей // Горный информационно-аналитический бюллетень. 2013. № 11. С. 322–331. [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. Скворцов А.В. Обзор алгоритмов построения триангуляции Делоне // Вычислительные методы и программирование. 2002. Т. 3. Вып. 1. С. 14–39. [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. P. 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. 258 p.
  16. Бандман О.Л. Инварианты клеточно-автоматных моделей реакционно-диффузионных процессов // Прикладная дискретная математика. 2012. № 3 (17). С. 108–120. [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

Downloads

Issue

Vol. 17 (2020) No. 3

Pages

13-21

Section

Mathematics

Dates

Submitted

September 16, 2020

Accepted

September 19, 2020

Published

September 28, 2020

How to Cite

[1]
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, т. 17, № 3, pp. 13–21. DOI: 10.31429/vestnik-17-3-13-21

License

Copyright (c) 2020 Домасевич М.А., Рубцов С.Е., Павлова А.В.

Creative Commons License

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

Similar Articles

1-10 of 209

You may also start an advanced similarity search for this article.

Most read articles by the same author(s)

1 2 3 4 5 > >>