Structural Mechanics of Engineering Constructions and BuildingsStructural Mechanics of Engineering Constructions and BuildingsСтроительная механика инженерных конструкций и сооружений1815-52352587-8700Peoples’ Friendship University of Russia named after Patrice Lumumba (RUDN University)1865010.22363/1815-5235-2018-14-2-154-174Geometrical investigations of middle surfaces of shellsГеометрия срединных поверхностей оболочекResearch ArticleConstrained Construction of Planar Delaunay Triangulations without FlippingПостроение планарных триангуляций Делоне с ограничениями без применения флипаGalishnikovaVera VГалишниковаВера ВладимировнаAssociate Professor, Director of the Department of Architecture and civil engineering, Engineering Academy, RUDN University. Research Interests: Computational Civil Engineering, Building information modeling, Topological computer models of buildings, Computational geometry, Computational mechanics of complex steel structural systems - latticed plates and shells, thin-walled plate and plate-rod structures. Nonlinear finite element analysis of space frames. Nonlinear stability of structuresтор технических наук, директор департамента архитектуры и строительства инженерной академии, Российский университет дружбы народов. Область научных интересов: вычислительная строительная инженерия, информационное моделирование зданий, топологические компьютерные модели зданий, вычислительная механика сложных стержневых систем, нелинейные конечно-элементные модели и программные комплексы для расчета пространственных стержневых систем, нелинейная устойчивость конструкцийgalishni@gmail.comPahlPeter JanПальПетер ЯнProf. Dr. Dr. h. c. mult., Department of Civil Engineering, Technical University Berlin (TUB). Research Interests: Mathematical modeling and optimization of comple[ structural systems, Computational Civil Engineering, Building information modeling, Topological computer models of buildings, Computational geometry, Computational mechanics of complex steel structural systems - latticed plates and shells, thin-walled plate and plate-rod structures. Nonlinear finite element analysis of space frames. Nonlinear stability of structuresдоктор наук, профессор кафедры инженерно-строительных наук, Берлинский технический университет (ТУБ) (D-10623, Берлин, ул. 17 июня, д. 135, Федеративная республика Германия). Область научных интересов: математическое моделирование и оптимизация сложных конструктивных систем, вычислительная строительная инженерия, информационное моделирование зданий, топологические компьютерные модели зданий, вычислительная механика сложных стержневых систем, нелинейные конечно-элементные модели и программные комплексы для расчета пространственных стержневых систем, нелинейная устойчивость конструкцийpahl@ifb.bv.tuberlin.dePeoples’ Friendship University of Russia (RUDN University)Российский университет дружбы народовTechnische Universität BerlinБерлинский технический университет15122018142VOL 14, NO2 (2018)ТОМ 14, №2 (2018)15417406062018Copyright ©; 2018, Galishnikova V.V., Pahl P.J.Copyright ©; 2018, Галишникова В.В., Паль П.Я.2018Galishnikova V.V., Pahl P.J.Галишникова В.В., Паль П.Я.http://creativecommons.org/licenses/by/4.0https://journals.rudn.ru/structural-mechanics/article/view/18650The construction of Voronoi diagrams and Delaunay triangulations finds wide application in many branches of science. Delaunay triangulations have properties which make them more desirable than other triangulations for the same node set. Delaunay has characterized his triangulations by the empty circle property. The partitioning and flipping methods which have been developed for digital construction of Voronoi diagrams and Delaunay triangulations only make indirect use of this property. A novel method of construction is proposed, which is based directly on the empty circle property of Delaunay. The geometry of the steps of the algorithm is simple and can be grasped intuitively. The method can be applied to constrained triangulations, in which a triangulation domain and some of the edges are prescribed. A data structure for triangulations of concave and multiply-connected domains is presented which permits convenient specification of the constraints and the triangulation. The method is readily implemented, efficient and robust.Построение диаграмм Вороного и триангуляций Делоне широко применяется во многих отраслях науки. Триангуляции Делоне за счет своих особых свойств более предпочтительны, чем другие триангуляции для одного и того же множества узлов. Триангуляция Делоне характеризуется круговым критерием. Методы деления и флипа, которые были разработаны для цифрового конструирования диаграмм Вороного и триангуляций Делоне, только косвенно используют этот критерий. Авторами предложен принципиально новый метод построения, который основан на прямом использовании кругового критерия триангуляции Делоне. Геометрия шагов алгоритма проста и интуитивно понятна. Метод может применяться для триангуляций с ограничениями, где заранее заданы область триангуляции и некоторые ребра. Представлена структура данных для невыпуклых и многосвязных множеств, которая позволяет удобно обуславливать ограничения и триангуляцию. Предлагаемый метод отличается простотой реализации, эффективностью работы и надежностью.DelaunayVoronoiempty circleshortest diagonaltriangulation theorempartitioningflippingconstrainedhalf edgedihedral cycleДелонеВоронойкруговой критерийнаименьшая диагональтеорема триангуляцииразбиениефлипограничениеполуреберныйдиэдральный цикл1.Liebling T.M., Pournin L. (2010). Voronoi Diagrams and Delaunay Triangulations: Ubiquitous Siamese Twins. Documenta Mathematica. Mathematics Subject Classification: 01A65, 4903, 52C99, 68R99, 70-08, 92-08.2.Voronoi G. (1908). Nouvelles applications des paramètres continues à la théorie des forms quadratiques. J. Reine Angew. Math. 134, 198-287.3.Delaunay B.N. (1932). Neue Darstellung der geometrischen Kristallographie. Z. Kristallographie, 84, 109-149.4.Dirichlet G.L. (1850). Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen, J. Reine Angew. Math. 40, 209-227.5.Aurenhammer F. (1987). Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16, 1, 78-96.6.Galishnikova V., Pahl P.J. (2013). Computational Geometry. Lecture Notes.7.Guibas L., Stolfi J. (1985). Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Regions. ACM Trans. on Graphics. V4, No. 2, April 1985.8.Shamos M.I., Hoey D. (1975). Closest-point problems. In Proceedings of the 16th Annual IEEE Symposium on FOCS, 151-162.9.Skvortsov A.V. (2002). Delaunay Triangulation and its applications. Tomsk State University, 128 p. (in Russ.).10.Skvortsov A.V., Mirza N.S. (2006). Algorithms for construction and analysis of triangulation. Tomsk State University Publ., 168 p. (in Russ.).11.Lawson C.L. (1972). Transforming triangulations, Discrete Math. 3, 365-372.12.Joe B. (1991). Construction of three-dimensional Delaunay triangles using local transformations. Comput. Aided Geom. Design 8, 123-142.13.de Loera J.A., Rambau J., Santos F. (2010). Triangulation: structures for triangulations and applications. Algorithms and Computation in Mathematics 25, Springer.14.Edelsbrunner H., Shah N.R. (1996). Incremental topological flipping works regular triangulations. Algorithmica 15, 223-241.15.Baudson C., Klein E. (2006). Berechnung und Visualisierung von Voronoi-Diagrammen in 3D. Diplomarbeit, p. 1-138. Rheinische Friedrich-Wilhelms-Universität Bonn16.Pahl, P.J. (2011). Theory and Application of Polytopes. Lecture notes. Chair of Bauinformatik, Technische Universität Berlin, 107 p.17.Mäntylä, M. (1988). Introduction to Solid Modeling. W.H. Freeman & Co. New York. ISBN: 0-88175-108-1.18.de Berg M., van Krefeld M., Overmars M., Schwarzkopf O. (1997). Computational Geometry: Algorithms and Applications. Chapter 14. Springer. ISBN 3-540-61270-X. 363 p.