ПРИМЕНЕНИЕ МЕТОДОВ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ

ДЛЯ АЛГОРИТМИЧЕСКОГО ОПИСАНИЯ ОБЛАСТЕЙ СО СЛОЖНОЙ ГЕОМЕТРИЕЙ

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

Таким образом возникает проблема эффективного алгоритмического описания сложного геометрического объекта: области или сетки. Для решения этих задач могут быть использованы методы вычислительной геометрии [1,2]. На их основе были созданы алгоритмы построения триангуляции для заданного множества точек, быстрого нахождения ячейки сетки, которой принадлежит заданная точка, геометрического поиска для сложной многосвязной области с кусочно-линейной границей. Эти алгоритмы используют разбиение оси Y, порождаемое множеством взаимопересечений проекций исходных отрезков (ребер сетки либо отрезков, из которых построена кусочно-линейная граница области) (рис. 1).

Алгоритм построения триангуляции множества N точек, параллельно строит и выпуклую оболочку этого множества. При этом его сложность эквивалентна сложности сортировки множества ординат и абсцисс этих точек, т.е. при вещественных координатах точек она равна O(N*LN(N)), а для целочисленных - линейна (рис. 2).

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

Алгоритмы поиска для геометрических объектов (треугольной сетки и области заданной кусочно-линейной границей) используют специальную поисковую структуру, которая рассчитывается для данного объекта только один раз и используется потом при всяком поиске. Время поиска в геометрическом объекте при наличии готовой поисковой структуры пропорционально LN(N), при этом используется метод "дихотомии" (рис. 3).

Особенностью вышеперечисленных алгоритмов является то, что они могут работать с достаточно большими массивами точек.

1. Ахо А. и др. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

Рис.2. Построение триангуляции с использованием выпуклой оболочки.

Рис.3. Определение ячейки для заданной точки.