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

Вход на сайт

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

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

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

dobryj den, popytalas otkryt prikreplionnyj fail ctoby posmotret kak rabotaet, no mne ego ne pokazyvaet vydajet osibku. Pochemu?
Очень интересно! ии сайт крутой жалко что умирает(
У Вас число превысит максимальное число int. Можно использовать в Вашем случае uint, но лучше все переписать на double.
Добавление к программе строки glutReshapeFunc(changeSize); приводит к тому, что треугольник перестаёт совсем отрисовываться.
Выдаёт ошибку glut32.dll не найден! При том, что он лежит в System32! Всё решил) Нужно отправить не в System32, а в System.

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

Рейтинг@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 кб