Об одном способе компьютерного определения местоположения точек относительно трехмерных областей

Изучение многих физических процессов в природе приводит к решению различных уравнений в абстрактных ограниченных областях с некоторыми краевыми условиями [1]. Решение таких задач аналитическими способами не всегда является возможным. В таких случаях к решению применяются численные (приближенные) методы вычислительной математики. Суть приближенных методов заключается в том, что сначала задача решается в дискретном образе непрерывной области, а затем доказывается сходимость дискретного решения к аналитическому решению при бесконечном увеличении количестве точек, составляющих дискретную область. Дискретизацию области можно осуществлять многими способами. Наиболее известными из них являются построения конечно-разностной сетки [2], конечно-элементной сетки [3], конечно-объёмной сетки [4,5] и сетки, состоящей из стохастического набора точек [6]. При машинной реализации таких приближенных методов определение местонахождения (локализация) точек относительно расчётной области является объёмной работой по количеству требуемых операций.

В современной литературе опубликованы некоторые алгоритмы локализации точек относительно областей со сложной границей (например,[7]), но в многомерном случае задача изучена недостаточно.

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

• 1.    Алгоритм локализации точек.1.1.    Описание трехмерной области.

Пусть Ω - трехмерная ограниченная замкнутая область, граница которой состоит из кусков поверхностей Pi заданных своими общими уравнениями

Ft(x,y,z) = 0, где i = 1,2,3,…,I – номер поверхности по некоторой нумерации, I – общее количество поверхностей, составляющих границу области.

Введем следующие понятия для заданного малого положительного числа ε .

Определение 1. Внутренностью поверхности Р(х,у,г~) = О с заданной точностью до ε называется множество

Vin = {(x^z^eR³-. F(x,y,z) < -f}.

Определение 2. Внешностью поверхности F(x,y, z) = 0 с заданной точностью до ε называется множество

Vout = {{x,y,z}eR3\F{x,y,z}> s}.

Определение 3. Граничностью поверхности F(x,y,z) = О с заданной точностью до ε называется множество

V_b = {(x,y,z)e/?³: \F(x,y,z)\ < s]

Известно из теории множеств, что любую область с кусочно-гладкой границей можно образовать из множеств Vin , Vout и ^b с помощью операций пересечения и дополнения. Следовательно, область Ω можно описать в виде упорядоченного множества D, элементами которого являются номера поверхностей (соответствуют внутренности поверхностей вместе с границей), номера поверхностей со знаком минус (соответствуют внешности поверхностей без границы) и специальных знаков, которые определяют границы различных подобластей и играют роль скобок в описании.

• 1.2.    Алгоритм локализации.

Пусть теперь задана произвольная точка с координатами Ь,Уо/о)-Подставляя эти координаты в левые части уравнения поверхностей, определим множество

^0 ⁼ [^al,^a2,^a3, ■■■>^aI, элементы которого определяются по формуле ( 0 если (х_о,Уо/о) ^V_b, a_t = <1 если (x₀ уоЛо) ⁶ V_in, (2 если (х_о,Уо/о) ^{e v}out.

Пусть далее, ^1 – местоположение точки (^о,Уо/о) относительно одной поверхности, ^2 – относительно другой. Положение точки (*о,Уо/о) относительно областей, полученных в результате выполнения операций дополнения (обозначим их через и ) и пересечения (обозначим через ij A ij) определим с помощью следующей таблицы (см. табл.1).

Таблица 1.

В результате последовательного образования области Ω согласно с элементами упорядоченного множества D с помощью приведенной таблицы получается однозначная локализация точки (^хо,Уо/о) относительно области Ω . Как отмечалось выше в определении, принадлежность точек к границе расчетной области определяется с точностью до ε .

В заключении отметим, что вводя понятие фигуры (отдельный участок границы, состоящий только из части одной поверхности, заданной своим общим уравнением [7]) можно значительно сократить количество операций при машинной реализации данного алгоритма.