ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : FAQ Robot                            2:5015/185     13 May 2002  21:05:36
 To : All
 Subject : [3/4] FAQ по геометрии.
 -------------------------------------------------------------------------------- 
 

     3.1. Как простроить триангуляцию произвольного многоугольника?
     3.2. Как простроить выпуклую оболочку?
 
 3.1. Как простроить триангуляцию произвольного многоугольника?
 Дан произвольный многоугольник. Hеобходимо найти разбиение этого многоугольника
 на треугольники, вершины которых являются вершинами данного многоугольника.
 Сложность O(n^2).
 Алгоритм.  Пусть многоугольник задан координатами своих вершин в порядке обхода
 по или против часовой стрелки. При чем порядок обхода является циклическим,
 т.е.
 после последней вершины идет первая, а перед первой последняя.
 1)      Пусть текущей является первая вершина.
 2)      Проверяем можно ли добавить треугольник, образованный текущей вершиной 
 и смежными ей, к триангуляции. Текущую вершину будем называть основной вершиной
 многоугольника.
 3)      Если да, то добавляем его к триангуляции, и удаляем из многоугольника.
 Просто удаляем текущую вершину из многоугольника, и соединяем смежные ей
 ребром. 
 Текущей вершиной становится вершина, которая шла перед удаленной. Если же доба-
 вить нельзя, то переходим к следующей вершине.
 4)      Повторяем пункты 2-4, пока количество вершин в многоугольнике не станет
 равным трем.
 Возникает логичный вопрос: <Как проверить, что треугольник можно добавить к
 триангуляции?>. Отвечаю. Во-первых, угол, заключенный между сторонами треуголь-
 ника являющимися сторонами многоугольника, должен быть меньше пи. Пусть треуго-
 льник ABC, и AB,AC являются сторонами многоугольника, тогда для того, что бы 
 угол BAC, был меньше пи необходимо и достаточно что бы знак в.п. *BA,BC* , со-
 впадал со знаком обхода многоугольника. Во-вторых, треугольник не должен соде-
 ржать других вершин многоугольника, кроме тех на которых построен. Доказатель-
 ство правильности алгоритма и его сложности.
 1)      Докажем, что алгоритм работает верно.  Т.к. все треугольники получен-
 ные в результате выполнения алгоритма не пересекаются, имеют своими вершинами 
 только вершины исходного многоугольника и покрывают весь многоугольник можно 
 сделать вывод что алгоритм работает правильно.
 2)      Докажем что сложность алгоритма не превосходит O(n^3). Очевидно, что за
 один проход многоугольника мы гарантированно найдем, по крайней мере, один
 треугольник удовлетворяющий нашим условиям. Т.е. всего проходов будет не более
 чем n-2, количество вершин просмотренных за каждый проход n, так же на для
 проверки вершины на возможность удаления сложность составляет O(n), в
 результате получается сложность O((n-2)*n*(n-3)), или O(n^3).
 3)      Докажем что сложность алгоритма не превосходит O(n^2). Для этого 
 достаточно доказать, что триангуляция будет найдена за один проход. Дей-
 ствительно, новый <правильный> треугольник, может получиться только в 
 результате удаления вершины, которая являлась смежной основной вершине этого 
 треугольника, а т.к. при удалении вершины происходит <откат назад>, то все 
 треугольники будут найдены за один проход.
 
 3.2. Как простроить выпуклую оболочку?
 (Списано из Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest:
 "Introduction to Algorithms").
   Выпуклой оболочкой (convex hull) конечного множества точек Q называется
 наименьший выпуклый многоугольник, содержащий все точки из Q (некоторые из
 точек могут быть внутри многоугольника, некоторые - на его сторонах, а
 некоторые будут его вершинами). Выпуклую оболочку множества Q мы будем
 обозначать CH(Q). Hаглядно можно представлять себе дело так: в точках Q вбиты
 гвозди, на которые натянута резинка, охватывающая из все - эта резинка и будет
 выпуклой оболочной множества гвоздей.
   Описание просмотра Грэхема.
   Просмотр Грэхема использует стек S, в котором хранятся точки, являющиеся
 кандидатами в выпуклую оболочку. Каждая точка исходного множества Q в некоторый
 момент помещается в стек; если она не является вершиной выпуклой оболочки
 CH(Q), то через некоторое время точка будет удалена из стека, а если является -
 останется. В момент окончания работы алгоритма в стеке S находятся в точности
 все вершины выпуклой оболочки CH(Q) в порядке обхода против часовой стрелки.
   Исходными данными для Graham-Scan является множество Q из (не менее чем трех)
 точек. Процедура использует функцию Top(S), которая возвращает точку,
 находящуюся в вершине стека S (не меняя содержимого стека), а также функцию
 NextToTop(S), которая возвращает следующий за вершиной элемент стека, так же не
 меняя содержимого.
 
 GrahamScan(Q)
 1)  пусть p0 - точка из множества Q с наименьшей ординатой (если таковых
 несколько - самая левая)
 2)  пусть <p1,p2,:,pm> - остальные точки множества Q, отсортированные в порядке
 возрастания полярного угла (против часовой стрелки) относительно точки p0. Если
 есть несколько точек с одинаковым полярным углом, то оставляем самую удаленную
 от p0.
 3)  top[S]<-0
 4)  Push(S,p0)
 5)  Push(S,p1)
 6)  Push(S,p2)
 7)  for i<=3 to m
 8)  do while при движении по ломаной 
                 NextToTop(S)->Top(S)-pi
                 мы двигаемся прямо или направо
 9)           do Pop(S)
 10) Push(S,pi)
 11) return S
 
 --- FIDOGATE 4.4.3-snp19beta4
  * Origin: The Age of Love (2:5015/185)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор