Построение гибридных расчетных сеток Вороного. Алгоритмы и нерешенные проблемы

Рассмотрена задача построения расчетной сетки Вороного, в которой строится объединение ячеек Вороного, аппроксимирующее область с кусочно-гладкой границей. В двумерном случае гладкие участки границы приближаются ребрами Вороного, а в острые граничные вершины помещаются вершины Вороного. Для построения такой сетки предложен алгоритм самоорганизации, который покрывает границу области почти структурированной полосой многоугольных ячеек Делоне. Эта полоса состоит из четырехугольников Делоне на гладких участках и из выпуклых многоугольников вокруг вершин острых углов. В целом сетка Вороного является гибридной и состоит из достаточно округлых выпуклых многоугольников в ядре области и из ортогональных сеточных слоев вблизи границы. В работе предложены схемы доразбиения пристеночных слоев Вороного, в том числе около острых углов. В самом простом случае, когда граница области задается явно как набор параметризованных кривых, а не как изолиния неявной функции, предложен алгоритм построения сеток Вороного, основанный на покрытии границы области кругами. Рассматриваются проблемы, связанные с обобщением предложенного алгоритма на трехмерный случай. Идеи этого алгоритма и возникающие проблемы проиллюстрированы на примере простых трехмерных тестовых задач. Библ. 19. Фиг. 33.