DOI: https://doi.org/10.15588/1607-3274-2015-4-5

### BACKGROUND GRID METHOD FOR PLANE SHAPES TRIANGULATION IN FUNCTIONAL APPROACH

S. V. Choporov

#### Abstract

In herein paper is described the problem of triangular mesh generation for complex geometrical domain. Functional approach is used for a geometrical object representation. Vladimir Rvachev’s R functions are used also. Functional approach is based on implicit functions and logical operations (negation, conjunction and disjunction) over these functions. Logical operation is a special real-value function that at inner point is greater than zero and at outer point is less than zero. Thus standard triangulations techniques, which based on predefined boundary discreet model, is less efficient. During background grid method for triangulation, triangles are built in domain directly. Presented method starts with a mesh that can be relatively easy generated (e.g. uniform mesh). Next, initial mesh is defined as a set of all inner elements. The last one generates a layer of elements near boundary (adaptation step). Adaptive method generates meshes that are close to uniform for structured background grids.

#### Keywords

discreet model, mesh, triangle, R-function, background grid.

PDF (Українська)

#### References

Скворцов А. В. Обзор алгоритмов построения триангуляции Делоне / А. В. Скворцов // Вычислительные методы и программирование. – 2002. – № 3. – С. 14–39. 2. Скворцов А. В. Триангуляция Делоне и ее применение / А. В. Скворцов. – Томск : Издательство Томского университета, 2002. – 128 с. 3. Bern M. Mesh generation and optimal triangulation / M. Bern, D. Eppstein // Computing in Euclidean Geometry. – 1992. – No. 1. – P. 23–90. 4. Bern M. Triangulating polygons without large angles / M. Bern, D. Dobkin, D. Eppstein // International Journal of Computational Geometry & Applications. – 1995. – Vol. 5. – P. 171–192. DOI: 10.1142/S0218195995000106 5. Ruppert J. A Delaunay refinement algorithm for quality 2-dimensional mesh generation / J. Ruppert // Journal of Algorithms. – 1995. – Vol. 18, Issue 3. – P. 548–585. DOI:10.1006/jagm.1995.1021 6. Tournois J. Interleaving Delaunay Refinement and Optimization for 2D Triangle Mesh Generation / J. Tournois, P. Alliez, O. Devillers // The 16th International Meshing Roundtable : International Conference, Washington, 14–17 October 2007 : proceedings. – Washington : Springer, 2008. – P. 83–101. DOI: 10.1.1.94.6288 7. Mavriplis D. J. An advancing front Delaunay triangulation algorithm designed for robustness / D. J. Mavriplis // Journal of Computational Physics. – 1995. – Vol. 117, Issue 1. – P. 90–101. DOI: 10.1.1.136.8268 8. Silva C. T. Greedy Cuts: An Advancing Front Terrain Triangulation Algorithm / C. T. Silva, J. S. B. Mitchell // The 6th ACM International Symposium on Advances in Geographic Information Systems : International Conference, Washington, 2–7 November 1998 : proceedings. – Washington : ACM, 1998. – P. 137–144. DOI: 10.1145/288692.288717 9. Галанин М. П. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространственных областей : итерационные методы / М. П. Галанин, И. А. Щеглов. – М. : ИПМ им М. В. Келдыша РАН, 2006. – № 9. – 32 с. – (Препринт / РАН, ИПМ им. М. В. Келдыша ; 06-01-00421). 10. Naumann U. Combinatorial Scientific Computing / [edited by] U. Naumann, O. Schenk. – Boca Raton, Florida : CRC Press, 2012. – 600 p. 11. Cheng S.-W. Delaunay Mesh Generation / S.-W. Cheng, T. K. Dey, J. R. Shewchuk. – Boca Raton, Florida : CRC Press, 2012. – 387 p. ISBN: 9781584887300 12. Samet H. The Quadtree and Related Hierarchical Data Structures / H. Samet // ACM Computing Surveys. – 1984. – Vol. 16, Issue 2. – P. 187–260. DOI: 10.1145/356924.356930 13. Рвачев В. Л. Введение в теорию R-функций / В. Л. Рвачев, Т. И. Шейко // Проблемы машиностроения. – 2001. – Т. 4, № 1–2. – С. 46–58. 14. R-функции и обратная задача аналитической геометрии в трехмерном пространстве / [К. В. Максименко-Шейко, А. М. Мацевитый, А. В. Толок, Т. И. Шейко] // Информационные тех- нологии. – 2007. – № 10. – С. 23–32.

#### GOST Style Citations

Copyright (c) 2016 S. V. Choporov