ВУЗ:
Составители:
Рубрика:
Глава 2. Плоские и планарные графы 65
Пусть на плоскости задано множество S точек P
i
, i = 1, …, n, в ко-
торых известны значения некоторой функции f
i
, i = 1 …, n.
Многоугольник M
k
с упорядоченным набором вершин P
i
, i=1,...,k,
называется простым, если никакая пара его несмежных ребер не
имеет общих точек.
Простой многоугольник M
k
называется выпуклым, если для лю-
бых двух точек g и q из M
k
соединяющий их отрезок целиком при-
надлежит M
k
.
Для нахождения выпуклого многоугольника по n точкам на плос-
кости можно использовать, например, метод Джарвиса (метод «за-
ворачивания подарка») или метод обхода Грэхема [46].
Построим выпуклый многоугольник так, чтобы его вершины
принадлежали множеству заданных точек, а все точки, не попавшие
в вершины, лежали внутри него.
Триангуляция полученного много-
угольника дает треугольную сетку с
вершинами, P
i
, i = 1, …, n, изобра-
жённую на рис. 2.22 для n = 8. Лю-
бые два треугольника в этом случае
либо не имеют общих точек, либо
имеют одну общую вершину или
одну общую сторону. Очевидно, что
такая триангуляция может быть вы-
полнена не единственным образом.
Пусть среди n точек плоскости
(n > 2) не все из них коллинеарные, а
k − число внутренних точек соответ-
ствующего многоугольника. Тогда
при любом способе триангуляции число треугольников Q = n – k + 2,
а число ребер такого графа m ≤ 3n – 6.
Если необходимо осуществить триангуляцию не на заданных
точках, а для выпуклой односвязной области D, то можно начать с
задания трех упорядоченных точек на границе области. Одним из
способов оптимизации этого процесса является триангуляция Дело-
не [46 – 49] .
Р
1
Р
2
Р
3
Р
4
Р
5
Р
6
Р
7
Р
8
0
х
у
Рис. 2.22
Страницы
- « первая
- ‹ предыдущая
- …
- 63
- 64
- 65
- 66
- 67
- …
- следующая ›
- последняя »
