ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : FAQ Robot                            2:5015/185     21 Oct 2002  04:41:00
 To : All
 Subject : [3] FAQ по геометрии.
 -------------------------------------------------------------------------------- 
 

   3.1. Как построить триангуляцию произвольного многоугольника?
   3.2. Как построить выпуклую оболочку?
   3.3  Как построить окружность, проходящую через три точки?
 
         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
         3.3.  Построение окружности, проходящей через три точки.
     
         A = b_x - a_x;
         B = b_y - a_y;
         C = c_x - a_y;
         D = c_y - a_y;
 
         E = A*(a_x + b_x) + B*(a_y + b_y);
         F = C*(a_x + c_x) + D*(a_y + c_y);
 
         G = 2.0*(A*(c_y - b_y)-B*(c_x - b_x));
 
         p_x = (D*E - B*F) / G;
         p_y = (A*F - C*E) / G;
 
     Если G равно нулю, это значит, что три точки дежат на одной прямой
     и не существует окружности конечного радиуса, проходящей через них. 
     Иначе радиус равен:
 
             r^2 = (a_x - p_x)^2 + (a_y - p_y)^2
 --- FIDOGATE 4.4.3-snp19beta4
  * Origin: Un Dia Sin Ti (2:5015/185)
 
 

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