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

Вход на сайт

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

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

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

У меня проблема вот с этим: gl.Clear(OpenGL.GL_COLOR_BUFFER_BIT | OpenGL.GL_DEPTH_BUFFER_BIT);. Вылезает ошибка: CS1061 "object" не содержит определения "GL_COLOR_BUFFER_BIT", и не удалось найти доступный метод расширения "GL_COLOR_BUFFER_BIT",...
Большое спасибо. Единственный код который прошел без каких либо ошибок. Ура!!!
Скажите пожалуйста, подскажите алгоритм по которому по заданным точкам можно определить тип многогранника, скажем это куб или прямоугольный параллелепипед. Нашел теорию по этим фигурам: https://www.mat... https://www.mat... Акцентировать внимание...
Всем у кого не работает. файл wizard.script Ещё одно упоминание Glut32 в строке "if (!VerifyLibFile(dir_nomacro_lib, _T("glut32"), _T("GLUT's"))) return false;" меняем на "if (!VerifyLibFile(dir_nomacro_lib, _T("freeglut"), _T("GLUT's"))) return...
Не получается, емаё

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

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