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

Вход на сайт

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

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

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

torrvic, возможно, Вам нужно добавить -lGLU
Извините за тупой вопрос. У меня при сборке Вашего примера выходит ошибка: "undefined reference to gluLookAt". Не могу найти в какой библиотеке находится эта функция. У меня задано: -lGL -lglut ... Искал в /usr/lib таким образом: nm lib*so* | grep...
Здравствуйте. Спасибо за проект. У меня вопрос, по какой причине определение принадлежности точки многоугольнику работает некорректно, если координаты из больших чисел состоят, например: int[] vertex = new int[] {...
Сейчас проверила нашла причину не запускания // Создание контекста воспроизведения OpenGL и привязка его к панели на форме OpenGLControl1:=TOpenGLControl.Create(Self); with OpenGLControl1 do begin Name:='OpenGLControl1'; //вот тут...
Ну..кажется что то пошло не так http://pp.usera...

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

Рейтинг@Mail.ru
Скриншот к примеру
Среда программирования: 
HTML 5 + JavaScript

Задача - построить минимальную выпуклую оболочку для множества точек на плоскости.

1. Создадим файл index.html, в котором подключим файл main.js и создадим форму с одним полем ввода - координаты точек (x, y) через запятую. По клику на кнопку будет вызываться функция getPoints().

<html>
    <head>
        <title>Graham Scan</title>
        <meta charset="utf-8"/>
        <script src="main.js"></script>
    </head>
    <body>  
        <form>
          <label>Задайте точки (через запятую):</label>
          <input id="points" value="10, 20, 60, 160, 110, 20, -60, 80, 70, 140" size="150" type="text" /> 
          <input type="button" onclick="getPoints()" value="Построить оболочку" /><br />
        </form>
    </body>    
</html>

2. Файл main.js:

  1. create_canvas() - создаем канвас и получает 2d контекст.
  2. drawCoordLines() - рисует координатные оси, с центром в точке (300, 220)
  3. drawPoints() и drawHull() - рисуют соответственно заданные точки, и выпуклую оболочку.
  4. update() - обновляет и перерисовывает канвас.
  5. getPoints() - считывает точки из формы и вызывает graham()
  6. graham() - собственно выполняет поиск выпуклой оболочки и заполняет массив h в котором будут перечислены точки, входящие в оболочку
Код программы: 

/**
 * создает канвас
 */
function create_canvas() {
    var canvas_html = document.createElement('canvas');
    canvas_html.id = "canvas";
    canvas_html.width = 1500;
    canvas_html.height = 800;
 
    document.body.appendChild(canvas_html);
 
    return canvas_html.getContext('2d');
}
 
/**
 * рисует координатные оси  
 */
function drawCoordLines() {
    canvas.beginPath();
    canvas.moveTo(300, 10);
    canvas.lineTo(300, 400);
    canvas.moveTo(10, 220);
    canvas.lineTo(600, 220);
    canvas.stroke();
    canvas.closePath();
}
 
/**
 * рисует оболочку
 */
function drawHull() {
    canvas.beginPath();
    canvas.moveTo(300 + points[ h[0] ].x, 220 - points[ h[0] ].y);
    for(var i=1; i<h.length; i++){
        canvas.lineTo(300 + points[ h[i] ].x, 220 - points[ h[i] ].y);
    }
 
    canvas.closePath();    
    canvas.stroke();    
}
 
/**
 * рисует точки
 */
function drawPoints() {
 
    canvas.fillStyle = '#00f';
    for(var i=0; i<points.length; i++){
        canvas.beginPath();
        canvas.arc(300 + points[i].x, 220 - points[i].y, 3, 0, Math.PI * 2); // рисует точку
        canvas.closePath();
        canvas.fill(); 
    }    
 
 
}
 
/**
 * обновляет и перерисовывает канвас
 */
function update() {
    canvas.clearRect(0, 0, 1500, 800); // очищаем канвас
    drawCoordLines();    
    draw();
    drawPoints();
}
 
/**
 * считывает точки из формы
 */
function getPoints() {
    // получаем строку введенную в форму, и записываем в массив, разбив ее по запятой
    var coords = pointsV.value.split(", ");
    var i = 0;
    var j = 0;
    points = [];
    ch = [];
    while (i < coords.length) {
        points[j++] = {
            'x': parseInt(coords[i++]),
            'y': parseInt(coords[i++])
        }
        ch.push(j-1);
    }    
    graham();
}
 
/**
 * возращает векторное произведение
 */
function classify(vector, x1, y1) {
    return pr = (vector.x2 - vector.x1) * (y1 - vector.y1) - (vector.y2 - vector.y1) * (x1 - vector.x1);
}
 
/**
 * Выполняет поиск Грэхема и заполняет массив h, в котором будут перечислены точки, входящие в оболочку
 */
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]); // добавляем новую точку в оболочку
    }
 
    // обновляем канвас
    update();
}
 
/**
 * выполняется когда страница будет полностью загружена в браузер
 */
window.onload = function() {
    canvas = create_canvas();
 
    // массив точек, из которых строим выпуклую оболочку
    points = [{
            'x': 10,
            'y': 20
        }, {
            'x': 60,
            'y': 160
        }, {
            'x': 110,
            'y': 20
        }, {
            'x': -60,
            'y': 80
        },
        {
            'x': 70,
            'y': 140
        }];
 
    // массив номеров точек, потребуется для алгоритма Грэхема   
    ch = [0, 1, 2, 3, 4];
 
    // искомая оболочка, будет заполнена функцией graham
    h = []
 
    // получаем форму ввода
    pointsV = document.getElementById('points');
    graham();
}

Прикрепленный файлРазмер
graham.zip2.36 кб