ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Michael Sedov                        2:5015/185.2   04 Apr 2002  18:32:54
 To : All
 Subject : [3] 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. Как найти многоугольник являющийся пересечением двух выпуклых многоуголь-
 ников?
 В отличие от реализации, алгоритм очень даже простой. Hаходим вершины первого
 многоугольника лежащие во втором (точки группы 1). Добавляем к ним вершины
 второго многоугольника находящиеся в первом (группа 2). Hу и к получившемуся
 множеству добавляем точки пересечения сторон первого и второго многоугольника
 (группа 3). Теперь на получившемся множестве строим выпуклую оболочку и
 многоугольник готов.
 Сложность считается достаточно просто, m,n - количество вершин соответствующим
 многоугольников. O(mn) - нахождение точек первой группы, O(mn) - второй
 группы, O(mn) - третьей группы, O((m+n)*log(m+n)) - построение выпуклой 
 оболочки. O(mn)+O(mn)+O(mn)+O((m+n)*log(m+n)) = O(mn).
 Hу и еще один небольшой бонус, касающийся построения выпуклой оболочки. Так
 как все точки нашего множества войдут в выпуклую оболочку, то ее можно 
 строить в несколько упрощенном варианте. 
 1)      Просто отсортировать по полярному углу, относительно центра масс 
 множества. Что бы это работало быстро надо использовать в.п.
 2)      Можно отсортировать по какой-нибудь координате. Соединить первую и
 последнюю вершину прямой. Вершины лежащие с одной стороны от этой прямой войдут
 в
 многоугольник в том порядке в каком они оказались после сортировки, лежащие по
 другую сторону в обратном порядке.
 --- WP/95 Rel 1.78E (215.0) Reg.
  * Origin: [3] Faq по Геометрии. (2:5015/185.2)
 
 

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