Построение выпуклой оболочки

добавлено: 11 Jun 2008 10:30
редактировано: 22 Mar 2012 12:17

Содержание [скрыть][показать]

Построение выпуклой оболочки обходом Грэхэма

Даны N точек на плоскости. Построить их выпуклую оболочку, т.е. наименьший выпуклый многоугольник, содержащий все эти точки.

Мы рассмотрим метод Грэхэма (Graham) (предложен в 1972 г.) с улучшениями Эндрю (Andrew) (1979 г.). С его помощью можно построить выпуклую оболочку за время O (N log N) с использованием только операций сравнения, сложения и умножения. Алгоритм является асимптотически оптимальным (доказано, что не существует алгоритма с лучшей асимптотикой), хотя в некоторых задачах он неприемлем (в случае параллельной обработки или при online-обработке).

Описание

Алгоритм. Найдём самую левую и самую правую точки A и B (если таких точек несколько, то возьмём самую нижнюю среди левых, и самую верхнюю среди правых). Понятно, что и A, и B обязательно попадут в выпуклую оболочку. Далее, проведём через них прямую AB, разделив множество всех точек на верхнее и нижнее подмножества S1 и S2 (точки, лежащие на прямой, можно отнести к любому множеству — они всё равно не войдут в оболочку). Точки A и B отнесём к обоим множествам. Теперь построим для S1 верхнюю оболочку, а для S2 — нижнюю оболочку, и объединим их, получив ответ. Чтобы получить, скажем, верхнюю оболочку, нужно отсортировать все точки по абсциссе, затем пройтись по всем точкам, рассматривая на каждом шаге кроме самой точки две предыдущие точки, вошедшие в оболочку. Если текущая тройка точек образует не правый поворот (что легко проверить с помощью Ориентированной площади), то ближайшего соседа нужно удалить из оболочки. В конце концов, останутся только точки, входящие в выпуклую оболочку.

Итак, алгоритм заключается в сортировке всех точек по абсциссе и двух (в худшем случае) обходах всех точек, т.е. требуемая асимптотика O (N log N) достигнута.

Реализация

struct pt { double x, y; }; bool cmp (pt a, pt b) { return a.x < b.x || a.x == b.x && a.y < b.y; } bool cw (pt a, pt b, pt c) { return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0; } bool ccw (pt a, pt b, pt c) { return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0; } void convex_hull (vector<pt> & a) { if (a.size() == 1) return; sort (a.begin(), a.end(), &cmp); pt p1 = a[0], p2 = a.back(); vector<pt> up, down; up.push_back (p1); down.push_back (p1); for (size_t i=1; i<a.size(); ++i) { if (i==a.size()-1 || cw (p1, a[i], p2)) { while (up.size()>=2 && !cw (up[up.size()-2], up[up.size()-1], a[i])) up.pop_back(); up.push_back (a[i]); } if (i==a.size()-1 || ccw (p1, a[i], p2)) { while (down.size()>=2 && !ccw (down[down.size()-2], down[down.size()-1], a[i])) down.pop_back(); down.push_back (a[i]); } } a.clear(); for (size_t i=0; i<up.size(); ++i) a.push_back (up[i]); for (size_t i=down.size()-2; i>0; —i) a.push_back (down[i]); }

 

 

 

 


Урок из серии “Геометрические алгоритмы”

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

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

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

Задача. На плоскости задано множество S точек. Найти вершины выпуклой оболочки этого множества.

Будем перечислять вершины в порядке обхода против часовой стрелки.

Задача построения выпуклой оболочки

Для эффективного решения этой задачи существует несколько различных алгоритмов. Приведем наиболее простую реализацию одного из них – алгоритма Джарвиса. Этот алгоритм иногда называют «заворачиванием подарка».


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

Для кандидата на роль точки проверяем выполнение условия со всеми точками М. Если точек, удовлетворяющих этому условию несколько, то вершиной искомого многоугольника станет та из них, для которой длина вектора максимальна.

Будем поступать так и далее.

Допустим, уже найдена i-я вершина выпуклой оболочки.

Для следующей точки  косые произведения не отрицательны для всех точек М.

Если таких точек несколько, то выбираем ту, для которой вектор  имеет наибольшую длину.

Непосредственно поиск такой точки можно осуществить так. Сначала мы можем считать следующей (i+1)-й, любую точку.

Затем вычисляем значение , рассматривая в качестве М все остальные точки. Если для одной из них указанное выражение меньше нуля, то считаем следующей ее и продолжаем проверку остальных точек (аналогично алгоритму поиска минимального элемента в массиве).

Если же значение выражения равно нулю, то сравниваем квадраты длин векторов. Продолжая эту процедуру, мы рано или поздно вернемся к точке . Это будет означать, что выпуклая оболочка построена.

Приведем программу решения данной задачи для целочисленных координат.

Множество исходных точек находится в массиве a, а все точки, принадлежащие выпуклой оболочке, будем записывать в массив b.

 

program geom6; type vv = record x,y: longint; end; myArray = array[1..100] of vv; var a, b: myArray; min,m,i,j,k,n:integer; input:text; function vect(a1,a2,b1,b2:vv):longint; begin vect:=(a2.x — a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y) end; function dist2(a1,a2:vv):longint; {Квадрат длины вектора} begin dist2:=sqr(a2.x-a1.x)+sqr(a2.y-a1.y); end;{dist2} procedure Solve(a:myArray; var k: integer; var b:myArray); {Построение выпуклой оболочки} var i, j, m: integer; begin {ищем правую нижнюю точку} m:=1; for i:= 2 to n do if a[i].y < a[m].y then m := i else if (a[i].y = a[m].y) and (a[i].x > a[m].x) then m:=i; {запишем ее в массив b и переставим на первое место в массиве a} b[1] := a[m]; a[m]:= a[1]; a[1]:= b[1]; k:= 1; min:= 2; writeln(b[1].x, b[1].y); repeat {ищем очередную вершину оболочки} for j := 2 to n do if (Vect(b[k],a[min],b[k],a[j])< 0) or ((Vect(b[k],a[min],b[k],a[j])=0) and (dist2(b[k],a[min])< dist2(b[k],a[j]))) then min:=j; k:=k+1; {записана очередная вершина} b[k]:=a[min]; min:=1; until (b[k].x = b[1].x)and (b[k].y = b[1].y); {пока ломаная не замкнется} end; {Solve} begin{main} assign(input,’input.pas’); reset(input); readln(input,n); {количество точек} for i:= 1 to n do read(input,a[i].x, a[i].y); close(input); solve(a, k, b); for j := 1 to k-1 do writeln(b[j].x, ‘ ‘,b[j].y) end.

 

Входные данные: 9 1 1 4 3 2 0 2 2 4 1 3 2 3 4 1 3 2 3Выходные данные: 2 0 4 1 4 3 3 4 1 3 1 1

На этом мы с вами заканчиваем обзор решения элементарых задач вычислительной геометрии на плоскости.

На них опирается решение более сложных , в частности олимпиадных задач.

Надеюсь, что решение последних окажется теперь нам по силам.

С уважением, Вера Господарец.

 

Поделиться с друзьями

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

Простой многоугольник — замкнутая ломаная без самопересечений.

  • Gift wrapping
    Простой алгоритм, время работы:
    • Лучший случай, все точки внутри оболочки: O(n)
    • Худший случай, все точки на оболочке: O(n2)
    • Среднее время: nh
  • Graham’s scan
    Алгоритм состоит из двух частей: сначала точки сортируются по полярному углу — O(nlogn). Если взять точки в порядке возрастания полярного угла, то получается простой многоугольник. Выпуклую оболочку произвольного простого многоугольника за O(n) находит вторая часть алгоритма.

    Алгоритм быстрой оболочки

  • Алгоритм Мелькмана
    Находит выпуклую оболочку простого многоугольника за O(n) операций.
  • Quickhull
    Рекурсивный, простой алгоритм. Время работы:
    • Лучший случай, все точки внутри оболочки: O(n)
    • Худший случай, все точки на оболочке: O(n2)
    • Среднее время: O(nlogn)

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

  • Разделяй-и-властвуй
    Вообще говоря, этот алгоритм медленнее, чем Quickhull. Но у него есть два важных преимущества:
    • Время работы всегда O(nlogn)
    • Легко распараллеливается: множество точек делится на N частей, выпуклые оболочки которых вычисляются независимо, а затем быстро сливаются.

    Существует две вариации алгоритма:

    В одной исходное множества точек разделяется на N частей, отсортированных по координате X: все точки из (k-1)-ой части левее точек из частей k..N. Этого можно достичь в процессе предобработки за O(nlogN) операций(нахождение середины: O(n)). А уже потом каждая часть вычисляется независимо(возможно, на своей машине/процессоре) и результаты объединяются.

    В другой — и именно она описана в статье, точки делятся на N любых равных частей. Никаких ограничений на части нет.

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

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

Алгоритмы выше принимают на вход все множество точек сразу, обрабатывают его и возвращают результат. А что, если точки подаются одна за другой, а задача состоит в том, чтобы поддерживать выпуклую оболочку имеющихся точек? Самый простой выход — после каждой добавленной точки вызывать какой-нибудь из описанных выше алгоритмов. Он построит выпуклую оболочку за Omega(nlogn) операций. Это приведет к сложности Omega(n2logn). Если хочется сделать побыстрее и поизящнее, то можно применить модифицированный алгоритм, работающий за O(n2).

Метод Грэхема (Graham method) — разработанная профессором финансов Колумбийского университета Б. Грэхемом инвестиционная теория, утверждающая, что наиболее эффективной портфельной инвестиционной стратегией является формирование портфеля за счет таких фондовых инструментов, рыночные цены на которые ниже их внутренней стоимости (исчисленной на основе стоимости чистых активов компании).

Задача построения выпуклой оболочки

Метод Грэхема характеризуют как философию инвестирования, ориентированную на стоимость (value-oriented investing theory).

Грэхем предлагает весьма разумную вещь: покупать акции, которые на рынке оценены значительно дешевле активов, которые за этими акциями стоят, и наоборот – продавать акции, когда они оценены рынком значительно дороже активов, за ними стоящих. Подход требует усидчивости, внимания, выдержки и знания основ бухгалтерского учета. То есть компанию надо уметь оценить, дождаться ситуации, когда рынок предлагает эту компанию купить на 30-60% дешевле вашей оценки активов компании (30-60% – то что Грэхем называет «маржей безопасности»), снова суметь подождать, перетерпев любые возможные просадки цены, и продать компанию, когда либо рынок оценит ее по достоинству, либо оценит ее выше достоинства на те же 30-60%.

Одним из критериев Грэхемовской стратегии является выявление акций с заниженной стоимостью. К таким акциям, как правило, относятся:

  • акции небольших малоизвестных компаний;
  • упавшие в стоимости акции мощных фирм вследствие затруднений.

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

Принципы Грэхема:

  1. выбирайте не акции, а компанию;
  2. покупайте акций по гарантирующей отсутствие убытков цене;
  3. вам придется принимать обоснованные решения на хаотично колеблющемся рынке.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *