Построение планарных триангуляций Делоне с ограничениями без применения флипа

Обложка

Аннотация


Построение диаграмм Вороного и триангуляций Делоне широко применяется во многих отраслях науки. Триангуляции Делоне за счет своих особых свойств более предпочтительны, чем другие триангуляции для одного и того же множества узлов. Триангуляция Делоне характеризуется круговым критерием. Методы деления и флипа, которые были разработаны для цифрового конструирования диаграмм Вороного и триангуляций Делоне, только косвенно используют этот критерий. Авторами предложен принципиально новый метод построения, который основан на прямом использовании кругового критерия триангуляции Делоне. Геометрия шагов алгоритма проста и интуитивно понятна. Метод может применяться для триангуляций с ограничениями, где заранее заданы область триангуляции и некоторые ребра. Представлена структура данных для невыпуклых и многосвязных множеств, которая позволяет удобно обуславливать ограничения и триангуляцию. Предлагаемый метод отличается простотой реализации, эффективностью работы и надежностью.

Вера Владимировна Галишникова

galishni@gmail.com
Российский университет дружбы народов 117198, Россия, Москва, ул. Миклухо-Маклая, 6

тор технических наук, директор департамента архитектуры и строительства инженерной академии, Российский университет дружбы народов. Область научных интересов: вычислительная строительная инженерия, информационное моделирование зданий, топологические компьютерные модели зданий, вычислительная механика сложных стержневых систем, нелинейные конечно-элементные модели и программные комплексы для расчета пространственных стержневых систем, нелинейная устойчивость конструкций

Петер Ян Паль

pahl@ifb.bv.tuberlin.de
Берлинский технический университет D-10623, Федеративная республика Германия, Берлин, ул. 17 июня, д. 135

доктор наук, профессор кафедры инженерно-строительных наук, Берлинский технический университет (ТУБ) (D-10623, Берлин, ул. 17 июня, д. 135, Федеративная республика Германия). Область научных интересов: математическое моделирование и оптимизация сложных конструктивных систем, вычислительная строительная инженерия, информационное моделирование зданий, топологические компьютерные модели зданий, вычислительная механика сложных стержневых систем, нелинейные конечно-элементные модели и программные комплексы для расчета пространственных стержневых систем, нелинейная устойчивость конструкций

  • 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.
  • Voronoi G. (1908). Nouvelles applications des paramètres continues à la théorie des forms quadratiques. J. Reine Angew. Math. 134, 198-287.
  • Delaunay B.N. (1932). Neue Darstellung der geometrischen Kristallographie. Z. Kristallographie, 84, 109-149.
  • Dirichlet G.L. (1850). Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen, J. Reine Angew. Math. 40, 209-227.
  • Aurenhammer F. (1987). Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16, 1, 78-96.
  • Galishnikova V., Pahl P.J. (2013). Computational Geometry. Lecture Notes.
  • 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.
  • Shamos M.I., Hoey D. (1975). Closest-point problems. In Proceedings of the 16th Annual IEEE Symposium on FOCS, 151-162.
  • Skvortsov A.V. (2002). Delaunay Triangulation and its applications. Tomsk State University, 128 p. (in Russ.).
  • Skvortsov A.V., Mirza N.S. (2006). Algorithms for construction and analysis of triangulation. Tomsk State University Publ., 168 p. (in Russ.).
  • Lawson C.L. (1972). Transforming triangulations, Discrete Math. 3, 365-372.
  • Joe B. (1991). Construction of three-dimensional Delaunay triangles using local transformations. Comput. Aided Geom. Design 8, 123-142.
  • de Loera J.A., Rambau J., Santos F. (2010). Triangulation: structures for triangulations and applications. Algorithms and Computation in Mathematics 25, Springer.
  • Edelsbrunner H., Shah N.R. (1996). Incremental topological flipping works regular triangulations. Algorithmica 15, 223-241.
  • Baudson C., Klein E. (2006). Berechnung und Visualisierung von Voronoi-Diagrammen in 3D. Diplomarbeit, p. 1-138. Rheinische Friedrich-Wilhelms-Universität Bonn
  • Pahl, P.J. (2011). Theory and Application of Polytopes. Lecture notes. Chair of Bauinformatik, Technische Universität Berlin, 107 p.
  • Mäntylä, M. (1988). Introduction to Solid Modeling. W.H. Freeman & Co. New York. ISBN: 0-88175-108-1.
  • 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.

Просмотры

Аннотация - 61

PDF (English) - 18


© Галишникова В.В., Паль П.Я., 2018

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.