BACKGROUND GRID METHOD FOR PLANE SHAPES TRIANGULATION IN FUNCTIONAL APPROACH

Authors

  • S. V. Choporov Zaporizhzhya National University, Zaporizhzhya, Ukraine

DOI:

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

Keywords:

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

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.

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.

Downloads

Published

2015-05-19

How to Cite

Choporov, S. V. (2015). BACKGROUND GRID METHOD FOR PLANE SHAPES TRIANGULATION IN FUNCTIONAL APPROACH. Radio Electronics, Computer Science, Control, (4). https://doi.org/10.15588/1607-3274-2015-4-5

Issue

No. 4 (2015): Radio Electronics, Computer Science, Control

Section

Mathematical and computer modelling

License

Copyright (c) 2016 S. V. Choporov

Creative Commons License

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

Creative Commons Licensing Notifications in the Copyright Notices

The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.

The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.

The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.