Глобальная балансировка триангуляционной сети

  • Денис Дмитриевич Васильков Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

Аннотация

Предложен новый алгоритм балансировки триангуляционной сети, содержащей точки Штейнера, основанный на методе наименьших квадратов. Он минимизирует среднеквадратичное отклонение косинусов углов триангуляции от оптимального значения 0,5. Алгоритм не имеет ограничений, поэтому может быть применен к любым триангуляциям, полученным алгоритмами сгущения триангуляционной сети, например алгоритмами Рупперта или Эртена и Унгора, при этом он не увеличивает число точек, а также не нарушает реберных связей. Проведенные эксперименты показали, что предлагаемый алгоритм существенно повышает число углов в диапазоне от 50 до 70° и не приводит к появлению треугольников с существенно меньшими минимальными углами. Алгоритм может быть эффективно реализован с использованием специализированных программных пакетов, предназначенных для быстрого решения разреженных систем линейных уравнений методом наименьших квадратов, например SuiteSparse. Благодаря этому алгоритм является простым в реализации.

Биография автора

Денис Дмитриевич Васильков, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

ассистент кафедры дискретной математики и алгоритмики факультета прикладной математики и информатики

Литература

  1. Farin G. Curves and surfaces for CAGD. 4th ed. San Diego : Acad. Press, 1997.
  2. Shewchuk J. R. What is a good linear finite element? In: 11th International Meshing Roundtable (New York, 15–18 Sept., 2002). New York : Ithaca, 2002. P. 115–126.
  3. Paul Chew L. Guaranteed-quality mesh generation for curved surfaces. In: Proceedings of the Ninth Annual Symposium on Computational Geometry (San Diego, 18–21 May, 1993). New York : ACM, 1993. P. 274 –280.
  4. Ruppert J. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. J. Algorithms. 1995. Vol. 18, issue 3. P. 548–585. DOI: 10.1006/jagm.1995.1021.
  5. Erten H., Üngör A. Triangulations with locally optimal steiner points. In: Eurographics Symposium on Geometry Processing (Barcelona, 4 – 6 July, 2007). Barcelona, 2007. P. 1–10.
  6. Paige C. C., Saunders M. A. LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Soft. 1982. Vol. 8, issue 1. P. 43–71. DOI: 10.1145/355984.355989.
  7. Rennich S., Stosic D., Davis T. A. Accelerating sparse cholesky factorization on GPUs. Architectures and Algorithms : IA3 Seventh Workshop on Irregul. Appl. (Denver, 13 Novemb., 2017). New Orleans, 2014.
Опубликован
2018-05-05
Ключевые слова: триангуляция, генерация сети, точки Штейнера, топология триангуляционной сети, метод наименьших квадратов, погрешность интерполяции, балансировка триангуляции
Как цитировать
Васильков, Д. Д. (2018). Глобальная балансировка триангуляционной сети. Журнал Белорусского государственного университета. Математика. Информатика, 1, 88-94. Доступно по https://journals.bsu.by/index.php/mathematics/article/view/889
Выпуск
№ 1 (2018): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Дискретная математика и математическая кибернетика

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).