Moskva, Moscow, Russian Federation
In the framework of solving the problem of approximating free-form surfaces by polyhedra with groups of congruent faces, an idea was proposed to predefine one or more groups of congruent triangles for any triangulation without limiting the flexibility of subsequent optimization. This led to the creation of the concept of αβ-triangulation. The article reveals theoretical aspects of αβ-triangulation in two-dimensional Euclidean space E2 , based on the intersection of elements from set theory, graph theory, and combinatorial topology. The paper presents a detailed study of this new mathematical model. The author introduces a precise definition of the notion of αβ-triangulation, formulates its main properties, and establishes important operations such as cutting and sewing that allow efficient transformation of the triangulation structure. A detailed description is given of the algorithm for constructing an αβ-triangulation from an arbitrary strongly connected triangulation, providing a universal approach to forming optimal structures for specific tasks. Furthermore, proof of consistency and independence of the introduced system of axioms is provided, which significantly strengthens the theoretical foundations of the model. Theoretical development of αβ-triangulation opens up broad prospects for solving problems in computational geometry, offering an effective tool for representing and processing complex forms of spatial objects. However, before practical application of this model, additional experiments and analysis of its efficiency compared to existing analogs are necessary. Thus, further research will determine the role and significance of the proposed model within modern technologies and methods of geometric modeling.
Delaunay triangulation, optimal triangulation, αβ-triangulation, axiomatization of αβ-triangulation, properties of αβ-triangulation
1. Aleksandrov P.S. Kombinatornaya topologiya [Tekst] / P.S. Aleksandrov. — 2-e izd. — M. — L.: Lenand, 2020. 664 s.
2. Berzhe M. Geometriya. T. 1 [Tekst] / M. Berzhe. — M.:Mir, 1984. — 500 s.
3. Bikbulatov T.H. Ispol'zovanie chastichnoy parallelizacii dlya triangulyacii dvumernyh oblastey [Tekst] / T.H. Bikbulatov, D.N. Tumakov // Programmnye produkty i sistemy. — 2022. — № 3. — S. 293–304. — DOI:https://doi.org/10.15827/0236-235X.139.293-304 EDN: https://elibrary.ru/PESJZO
4. Galiulin R.V. Sistemy Delone kak osnova geometrii diskretnogo mira [Tekst] / R.V. Galiulin // Zhurnal vychislitel'noy matematiki i matematicheskoy fiziki. — 2003. — T. 43. — № 6. — S. 790–801. EDN: https://elibrary.ru/OOCQPN
5. Klyachin V.A. Algoritm triangulyacii, osnovannyy na uslovii pustogo vypuklogo mnozhestva [Tekst] / V.A. Klyachin // Vestnik Volgogradskogo gosudarstvennogo universiteta. Seriya 1. Matematika. Fizika. 2015. — T. 3. — S. 27–33 DOI: https://doi.org/10.15688/jvolsu1.2015.3.3; EDN: https://elibrary.ru/VATYGJ
6. Klyachin V.A. Ob odnom obobschenii usloviya Delone [Tekst] / V.A. Klyachin // Vestnik Tomskogo gosudarstvennogo universiteta. Matematika i mehanika 2008. — № 1. — C. 48–50. EDN: https://elibrary.ru/KHOGJX
7. Lebedinskaya N.A. Preobrazovanie triangulyaciy pri pomoschi elementarnyh operaciy [Tekst] / N.A. Lebedinskaya, D.M. Lebedinskiy // Vestnik Sankt-Peterburgskogo universiteta. Prikladnaya matematika. Informatika. Processy upravleniya. — 2009. — № 1. S. 84–86. EDN: https://elibrary.ru/KVNEAB
8. Rustamyan V.V. Analiz topologii poliedrov v zadache approksimacii zamknutyh poverhnostey poliedrami s gruppami kongruentnyh graney [Tekst] / V.V. Rustamyan // GraphiCon 2024: Materialy 34-y Mezhdunarodnoy konferencii po komp'yuternoy grafike i mashinnomu zreniyu, Omsk, 17–19 sentyabrya 2024 goda. — Omsk: Omskiy gosudarstvennyy tehnicheskiy universitet, 2024. — S. 827–836. — DOI:https://doi.org/10.25206/978-5-8149-38732-2024-827-836 DOI: https://doi.org/10.25206/978-5-8149-3873-2-2024-827-836; EDN: https://elibrary.ru/DLSJMT
9. Rustamyan V.V. Analiz osnovnyh parametrov geneticheskogo algoritma pri reshenii zadachi approksimacii zamknutyh poverhnostey svobodnoy formy poliedrami s gruppami kongruentnyh treugol'nikov [Tekst] / V.V. Rustamyan // Geometriya i grafika. — 2024. — T. 12. № 2. — S. 13–25. — DOI:https://doi.org/10.12737/2308-4898-2024-123-13-25 DOI: https://doi.org/10.12737/2308-4898-2024-12-3-13-25; EDN: https://elibrary.ru/ETWITX
10. Saleh M.S. Vnedrenie cifrovyh metodov na razlichnyh etapah arhitekturnogo proektirovaniya [Tekst] / M.S. Saleh // Arhitektura i sovremennye informacionnye tehnologii. — 2021. — № 1. — S. 268–278. DOI:https://doi.org/10.24412/1998-4839-2021-1-268-278 EDN: https://elibrary.ru/SKZHER
11. Saleh M.S. Metodika poiska arhitekturnoy formy putem primeneniya principov geneticheskogo algoritma s pomosch'yu cifrovyh tehnologiy na primere obschestvennogo centra v gorode Istre [Tekst] / M.S. Saleh // Nauka, obrazovanie i eksperimental'noe proektirovanie. Trudy MARHI: Materialy mezhdunarodnoy nauchno-prakticheskoy konferencii, Moskva, 08–12 aprelya 2019 goda. — M.: Izd-vo Moskovskogo arhitekturnogo instituta (gosudarstvennaya akademiya), 2019. — S. 433–436. EDN: https://elibrary.ru/TMGGIW
12. Saleh M.S. Osnovnye napravleniya razvitiya cifrovyh metodov proektirovaniya v noveyshey arhitekture [Tekst] / M.S. Saleh // Arhitektura i sovremennye informacionnye tehnologii. — 2020. — № 2. S. 351–361. — DOI:https://doi.org/10.24411/1998-4839-2020-15119 EDN: https://elibrary.ru/KBFSOP
13. Sal'kov N.A. Izuchenie geometrii kak vazhneyshiy sposob razvitiya evristicheskogo myshleniya [Tekst] / N.A. Sal'kov // Geometriya i grafika. — 2024. — T. 12. —№ 1. — S. 22–31. — DOI:https://doi.org/10.12737/2308-4898-2024-121-22-31 DOI: https://doi.org/10.12737/2308-4898-2024-12-1-22-31; EDN: https://elibrary.ru/RDLBIM
14. Sal'kov N.A. Opredelenie rasstoyaniy mezhdu geometricheskimi figurami interaktivnym metodom [Tekst] / N.A. Sal'kov // Geometriya i grafika. — 2024. T. 12. — № 4. — S. 3–14. — DOI:https://doi.org/10.12737/2308-48982024-12-4-3-14 DOI: https://doi.org/10.12737/2308-4898-2024-12-4-3-14; EDN: https://elibrary.ru/SDYIHZ
15. Skvorcov A.V. Triangulyaciya Delone i ee primenenie [Tekst] / A.V. Skvorcov. — Tomsk: Izd-vo Tom. un-ta, 2002. — 128 s. EDN: https://elibrary.ru/RZIMNT
16. Skvorcov A.V. Algoritmy postroeniya i analiza triangulyacii [Tekst] / A.V. Skvorcov, N.S. Mirza. — Tomsk: Izd-vo Tomskogo universiteta, 2006. — 168 s. EDN: https://elibrary.ru/SBVWBL
17. Solov'ev A.V. Primenenie triangulyacii Delone v zadache monitoringa dreyfa l'da [Tekst] / A.V. Solov'ev // Novye informacionnye tehnologii v nauchnyh issledovaniyah: Materialy XXIX Vserossiyskoy nauchno-tehnicheskoy konferencii studentov, molodyh uchenyh i specialistov, Ryazan', 27–29 noyabrya 2024 goda. — Ryazan': Ryazanskiy gosudarstvennyy radiotehnicheskiy universitet im. V.F. Utkina, 2024. S. 147–149. EDN: https://elibrary.ru/DGRJBR
18. Uspenskiy V.A. Chto takoe aksiomaticheskiy metod?[Tekst] / V.A. Uspenskiy. — Izhevsk: Regulyarnaya i haoticheskaya dinamika, 2001. — 96 s.
19. Chekmarev D.T. Gladkaya interpolyaciya triangulirovannoy poverhnosti [Tekst] / D.T. Chekmarev, M.H. Abuzyarov // Materialy XIII Mezhdunarodnoy konferencii po prikladnoy matematike i mehanike v aerokosmicheskoy otrasli (AMMAI'2020), Alushta, 06–13 sentyabrya 2020 goda. — M.: Izd-vo Moskovskogo aviacionnogo instituta (nacional'nyy issledovatel'skiy universitet), 2020. — S. 606–607. EDN: https://elibrary.ru/RZYVTO
20. Chekmarev D.T. O gladkoy interpolyacii triangulirovannoy poverhnosti [Tekst] / D.T. Chekmarev, M.H. Abuzyarov, W. Cheng // Problemy prochnosti i plastichnosti. — 2020. — T. 82. — № 2. — S. 147–155. — DOIhttps://doi.org/10.32326/1814-9146-2020-82-2-147-155 EDN: https://elibrary.ru/WBBOGD
21. Delaunay B.N. Sur la sphere vide. A la memoire de Georges Voronoi [Tekst] / B.N. Delaunay // Izvestiya AN SSSR. 1934. № 6, pp. 793–800.
22. Fáry I. On stright line representation of planar graph [Tekst] / I. Fáry // Acta Sci. Math (Szeged). 1948. V. 11, pp. 229–233.
23. Liu Y. Reducing the Number of Different Faces in FreeForm Surface Approximations Through Clustering and Optimization. [Tekst] / Y. Liu, T.-U. Lee, A. Rezaee Javan,N. Pietroni, Y. Xie // Computer-Aided Design. 2023.V. 166, p. 103633. DOI:https://doi.org/10.1016/j.cad.2023.103633 EDN: https://elibrary.ru/CLHJAM
24. Miky Yehia, Kamel Abdullah, Al Shouny Ahmed A combined contour lines iteration algorithm and Delaunay triangulation for terrain modeling enhancement [Tekst] / Yehia Miky, Abdullah Kamel, Ahmed Al Shouny // Geo-spatial Information Science. 2022. V. 26, p. 2070553. DOIhttps://doi.org/10.1080/10095020.2022.2070553
25. O'Rourke J. On Flat Polyhedra deriving from Alexandrov's Theorem, 2010, DOI: 10.48550.
26. Pellis D., Kilian M., Wang H., Jiang C., Müller C., Pottmann H. Architectural freeform surfaces designed for cost-effective paneling through mold re-use // Conference: Advances in Architectural Geometry. 2021.
27. Singh M., Schaefer S. Triangle Surfaces with Discrete Equivalence Classes // ACM Trans. Graph. 2010. V. 29. DOI:https://doi.org/10.1145/1833351.1778783
