Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

Добавление к программе строки glutReshapeFunc(changeSize); приводит к тому, что треугольник перестаёт совсем отрисовываться.
Выдаёт ошибку glut32.dll не найден! При том, что он лежит в System32! Всё решил) Нужно отправить не в System32, а в System.
Спасибо за статью. Я не Ваш студент. Но мне она помогла написать функцию для Канторова множества на Python для черепашки: import turtle def kanter(x, y, d):     if d > 1:         turtle...
Как реализовать в данном примере границы расчёта?

Счетчики и рейтинг

Рейтинг@Mail.ru Яндекс.Метрика

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


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

  1. Алгоритм обхода Джарвиса
  2. Алгоритм обхода Грэхема
  3. Алгоритм монотонных цепочек Эндрю
  4. Алгоритм типа «Разделяй и властвуй»
  5. Алгоритм «быстрого построения»
  6. Алгоритм Чана

Рассмотрим некоторые из них.

Алгоритм обхода Джарвиса

Пусть дан массив точек P.

  1. Необходимо найти точку, которая гарантировано будет входить в выпуклую оболочку; очевидно, что самая левая нижняя точка подходит под это условие.Находим точку с минимальной координатой x и y, и делаем ее текущей H[0].
  2. Перебираем все оставшиеся точки двойным циклом по i и j. В массив H записываем самую правую точку относительно вектора H[i]P[j]. Для этого находим векторное произведение, и если оно меньше 0, следовательно точка P[j] находится правее точки P[i] относительно H[i].
  3. Алгоритм завершается тогда, когда в H будет записана стартовая вершина и следовательно линия замкнется.

Псевдокод:

Jarvis(P)
    1) H[1] = самая левая нижняя точка массива P;
    2) i = 1;
    3) do {
         H[i+1] = любая точка из P (кроме уже попавших в выпуклую оболочку, но включая p[1]);
            for (для каждой точки j из P, кроме уже попавших в выпуклую оболочку, но включая p[1])
               if( векторное произведение(H[i], H[i+1], P[j]) < 0 ):
	          H[i+1] = P[j]            
                  i = i + 1;
         } while P[i] != P[1]
    4) return p;


Сложность обхода Джарвиса - O(hn), где n - количество всех вершин и h - количество вершин попавших в выпуклую оболочку.

Алгоритм обхода Грэхема
Сложность данного алгоритма O(nlgn) - следовательно он будет работать быстрее обхода Джарвиса.
1. Как и в предыдущем алгоритме находим самую нижнюю левую точку и делаем ее начальной.
2. Сортируем все оставшиеся точки в порядке их “левизны” относительно начальной точки, с помощью векторного произведения.


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

Код алгоритма на javascript:

function graham() {
    var minI = 0; //номер нижней левой точки
    var min = points[0].x;
    // ищем нижнюю левую точку
    for (var i = 1; i < points.length; i++) {
        if (points[i].x < min) {
            min = points[i].x;
            minI = i;
        }
    }
    // делаем нижнюю левую точку активной
    ch[0] = minI;
    ch[minI] = 0;
 
    // сортируем вершины в порядке "левизны"
    for (var i = 1; i < ch.length - 1; i++) {
        for (var j = i + 1; j < ch.length; j++) {
            var cl = classify({
                'x1': points[ ch[0] ].x,
                'y1': points[ ch[0] ].y,
                'x2': points[ ch[i] ].x,
                'y2': points[ ch[i] ].y
            }, points[ ch[j] ].x, points[ ch[j] ].y) // функция classify считает векторное произведение.            
 
            // если векторное произведение меньше 0, следовательно вершина j левее вершины i.Меняем их местами
            if (cl < 0) {
                temp = ch[i];
                ch[i] = ch[j];
                ch[j] = temp;
            }
        }
    }   
 
    //записываем в стек вершины, которые точно входят в оболочку
    h = [];
    h[0] = ch[0];
    h[1] = ch[1]; 
 
 
    for (var i = 2; i < ch.length; i++) {
        while (classify({
            'x1': points[ h[h.length - 2] ].x,
            'y1': points[ h[h.length - 2] ].y,
            'x2': points[ h[h.length - 1] ].x,
            'y2': points[ h[h.length - 1] ].y
        }, points[ ch[i] ].x, points[ ch[i] ].y) < 0) {            
            h.pop(); // пока встречается правый поворот, убираем точку из оболочки
        }
        h.push(ch[i]); // добавляем новую точку в оболочку
    }
}

Метод Эндрю.

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

Пусть задано конечное множество M точек плоскости, состоящее из m элементов. Сначала находятся его левая крайняя точка l и правая крайняя точка r этого множества. Для определенности среди точек с наименьшей абсциссой выбирается точка с наименьшей ординатой, а среди точек с наибольшей абсциссой — точка с наибольшей ординатой. Построим прямую, проходящую через точки l и r (см. рис. 1). Множество M разбивается на два подмножества, первое из которых состоит из точек, расположенных выше прямой, и называется верхним подмножеством, а второе состоит из остальных точек и называется нижним подмножеством.


Рис.1. Разбиение, определенное крайними точками

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

Выпуклая оболочка верхнего подмножества и точек l и r строится в два этапа:

Верхние точки вместе с точками l и r сортируются по возрастанию абсцисс. Среди точек с одинаковой абсциссой оставляется лишь верхняя.

Производится просмотр троек pipi+1pi+2 верхних точек. Если вектор pipi+1 расположен слева от pipi+2, то увеличивается i, в противном случае точка pi+1 удаляется из списка (или массива) верхних точек.

Есть еще более быстрый способ поиска - алгоритм Чана. Его идея заключается в том, чтобы разбить множество заданных точек на группы, по m точек в каждой. Для каждой из таких групп строится выпуклая оболочка обходом Грэхема. Затем находится самая нижняя левая точка, и методом Джарвиса строится общая оболочка для всех групп, при этом следующая точка находится быстрее, так как в каждой группе они отсортированы в нужном порядке после обхода Грэхема. Следовательно для нахождения следующей точки оболочки нужно проверить только одну точку из каждой группы.