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

Вход на сайт

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

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

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

КРУГОВОЙ ФРАКТАЛ -ОШИБОЧНАЯ ПРОГРАММА! ПАПА ЗибЕрт
Можешь обяснить подробно что как работает, и почему массу не задаем
Здравствуйте, Ильгиз. Математика - царица наук (Карл Гаусс). Изучение математики начинается с детского сада, когда нас учат считать и выполнять простые арифметические операции. Любой, даже самый простейший алгоритм будет связан с арифметическими...
Я хотел узнать математика это обязательно в программирование. Пять лет назад просто из любопытства я увлекся HTML потом изучил CSS и JvaScript потом изучил PHP и Java. Как то не задумывался и начал смотреть форумы и узнал что без математики не...
Все верно, но так же необходимо зайти в: Компоновщик -> Ввод -> Дополнительные зависимости Здесь необходимо нажать изменить и в Дополнительные зависимости прописать это: SDL2.lib SDL2main.lib SDL2test.lib Без этого не заработает. (MVS 2015)

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

Яндекс.Метрика Рейтинг@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 точек в каждой. Для каждой из таких групп строится выпуклая оболочка обходом Грэхема. Затем находится самая нижняя левая точка, и методом Джарвиса строится общая оболочка для всех групп, при этом следующая точка находится быстрее, так как в каждой группе они остортированы в нужном порядке после обхода Грэхема. Следовательно для нахождения следующей точки оболочки нужно проверить только одну точку из каждой группы.