Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Математика / Вычислительная геометрия /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


8  Gift wrapping
8  Алгоритм Грэхема
8  Алгоритм Мелькмана
8  Quickhull
8  Разделяй-и-властвуй
Построение выпуклой оболочки конечного множества точек - Программирование от RIN.RU
Построение выпуклой оболочки конечного множества точек

Пусть задано некоторое множество точек на плоскости. Выпуклая оболочка - наименьший выпуклый многоугольник, содержащий данные точки.


Вообразим, что плоскость - это деревянная доска, утыканная гвоздями в каждой точке из данного множества. Теперь натянем вокруг гвоздей резиновое кольцо. Оно стянется и образует выпуклую оболочку, как показано на рисунке выше.


Выпуклые оболочки очень важны в ряде геометрических положений не только сами по себе, но и как части других алгоритмов, использующих построение выпуклой оболочки в качестве элементарной операции.


Асимптотика числа вершин выпуклой оболочки для n точек,


  • равномерно распределенных внутри единичного круга - Theta(n1/3)


  • равномерно распределенных внутри фиксированного выпуклого многоугольника - Theta(log n)


  • подчиненных двумерному нормальному распределению - Theta((log n)1/2)





В оценках ниже n - количество точек, h - количество точек выпуклой оболочки.







SpeedSIP значительно снижает расходы на телефонную связь и сервисы:
  • бесплатные звонки внутри сети,
  • выгодные международные и междугородные звонки,
  • СМС по всему миру,
  • покупка прямого номер любой страны,
  • видеосвязь и видеоконференции.


  • В этом разделе :

    8  Gift wrapping
    Простой алгоритм, время работы:

    • Лучший случай, все точки внутри оболочки: O(n)

    • Худший случай, все точки на оболочке: On2)

    • Среднее время: nh



    8  Алгоритм Грэхема
    Алгоритм состоит из двух частей: сначала точки сортируются по полярному углу - O(nlogn). Если взять точки в порядке возрастания полярного угла, то получается простой многоугольник. Выпуклую оболочку произвольного простого многоугольника за O(n) находит вторая часть алгоритма.

    8  Алгоритм Мелькмана
    Находит выпуклую оболочку простого многоугольника за O(n) операций.

    8  Quickhull
    Рекурсивный, простой алгоритм. На случайном наборе точек этот алгоритм работает быстрее всех.

    8  Разделяй-и-властвуй


    8  Gift wrapping
    8  Алгоритм Грэхема
    8  Алгоритм Мелькмана
    8  Quickhull
    8  Разделяй-и-властвуй

     
      
      
        Copyright ©  RIN 2003 - 2004      * Обратная связь