ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Ilia Kantor                          2:5020/1815.6  01 Oct 2001  01:01:18
 To : Ihor Bobak
 Subject : Опуклая оболочка
 -------------------------------------------------------------------------------- 
 

  Здра.. жела.. това.. Ihor Bobak !
 
  IB> Для большого количества точек (N=1000) на плоскости требуется
  IB> найти их опуклую оболочку.
 
  IB> Тупой способ состоит в том, чтобы найти сначала
  IB> одно ребро A[1]->A[2] оболочки, а потом искать остальные ребра
  IB> одно за другим таким образом:
  IB>   допустим, уже нашли  A[1]->A[2], ... A[k-1]->A[k],
  IB>   тогда из оставшихся вершин выбираем вершину A[k+1] так, чтобы
  IB>   все вершины лежали относительно ребра A[k]->A[k+1] по одну (ту же)
  IB>   сторону.
 
  IB> Hе подскажете ли вы более интеллектуальные алгоритмы отыскания опуклой
  IB> оболочки?
 
    Что такое опуклая оболочка не знаем, но догадываемся...
 
   Можно, напpимеp, делать так:
 
 ======  algolist/math/geom/obol/gift.html ==========
 Математика:
 Вычислительная геометрия:
 Построение выпуклой оболочки.
 
 Алгоритм Грэхема.
 Автор: Unknown.
 Перевод: Кантор И.
 
      Первым шагом определяем самую нижнюю-правую точку, пусть это - точка 0. Она
 наверняка лежит на оболочке ( Шаг А ). Следующая стадия - сортировка всех точек 
 по углу между осью Х и линией ( 0 , эта точка ). Точка с самым большим углом
 отправляется в стек за точкой 0 ( Шаг B ).
 
      Дальше все точки обрабатываются по очереди, начиная от самого меньшего угла
 ( точка 1 ) и до тех пор, пока не достигнута точка 9. Процесс состоит из теста, 
 является ли строго левым поворот к новой точке на пути: верхняя-1 точка стека - 
 верхняя точка стека - тестируемая точка. Если это так, тогда она идет в стек и
 переходим к следующей точке. Если нет - то убираем вершину стека и повторяем
 проверку с той же точкой. Это проиллюстрировано в шагах C-L. Иногда из стека
 приходтся убирать несколько точек подряд, так как они последовательно не
 проходят проверки: обнаруживается правый поворот. Вообще говоря, в алгоритме еще
 нужна проверка на то, нет ли поворота _обратно_, и в этом случае точку следует
 оставить: мы имеем прямую. о это уже мелочи.
 Тут pисунки были, иллюстpиpующие шаги
 
 Псевдокод.
 айти нижнюю ( правую ) точку.
 Пометить ее p(0)
 Отсортировать все остальные точки по углу относительно p(0)
     Если одинаковый угол - по расстоянию.
     помечаем их p(1),...,p(n-1)
     Стек S=(p(n-1),p(0))=(p(t-1),p(i)); t - индекс вершины
     i = 1
     while i < n do
         if p(i) строго слева от ( p(t-1),p(t) )
         then Push(S,i) and i = i + 1
         else Pop(S)
 
 ==========================
 
      lWl   lWl    Пожелай мне удачи в бою, Ihor!    lWl    lWl
 --- GoldEd 3.00.Alpha4+
  * Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
 
 

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

Тема:    Автор:    Дата:    Опуклая оболочка   Ihor Bobak   26 Sep 2001 18:35:05   Опуклая оболочка   Egorov Pavel   30 Sep 2001 20:08:38   Опуклая оболочка   Ilia Kantor   01 Oct 2001 01:01:18