Математическое моделирование на графах. Часть 1. Берцун В.Н. - 66 стр.

UptoLike

Составители:

Рубрика:

66 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1

Триангуляция набора из n точек на плоскости называется триан-

гуляцией Делоне, если окружность, описанная вокруг каждого из

треугольников, не будет содержать внутри себя точек набора n. В

этом случае достигается максимум минимального угла по всем тре-

угольникам, что повышает точность интерполяции.

Триангуляция, приведенная на рис. 2.23, a является триангуляци-

ей Делоне, а на рис. 2.23, б − нет, так как существует окружность,

содержащая внутри себя точку набора n.

аб

Рис. 2.23

Если набор n содержит не менее трех неколлинеарных точек и

никакие 4 точки из n не лежат на одной окружности, то такая триан-

гуляция единственна. Соответствующий ей граф назовем графом

Делоне (или сеткой Делоне в терминах теории интерполирования).

Отметим, что для квадрата, например, триангуляция Делоне неодно-

значна.

При интерполировании на нерегулярной сетке в выпуклом мно-

гоугольнике M

возникает задача определения треугольника, содер-

жащего заданную точку P(x, y) [50].

Условия принадлежности этой точки треугольнику, например, с

вершинами (p

, p

), если они пронумерованы против часовой

стрелки, имеют вид

23 1 3 12

(,,)0, (,,)0, (,,)0Pp p p Pp p p P∆>∆>∆>,

где (x

, y

) − координаты вершин выбранного треугольника; mod ∆ −

его удвоенная площадь