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

Вход на сайт

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

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

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

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

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

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

Задача: построить триангуляцию Делоне для множества точек.
Описание работы программы:
С помощью нормального распределения генерируется 100 точек, принадлежащих области канваса.
Затем находится треугольник, содержащий все точки этого множества.
После чего каждая точка последовательно добавляется в триангуляцию с необходимыми перестроениями триангуляции.

Код программы: 

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
</head>
<body>
    <canvas width="1000" height="600"></canvas>
    <script>
        'use strict';
        let EPS = 1e-7; // эпсилон для работы с вещественными числами
 
        // подключение canvas
        let canvas = document.querySelector("canvas");
        let ctx = canvas.getContext("2d");
 
        // генерация точек множества при помощи нормального распределения
        const size = 100;
        let pts = [];
        for (let i = 0; i < size; i++) {
            let x = Math.random() * canvas.width, y = Math.random() * canvas.height;
            pts.push([Math.round(x), Math.round(y)]);
        }
 
        // функция, находящая треугольник, содержащий все точки множества
        function big_triangle(points) {
            let minx = 1000000, maxx = -1000000, miny = 1000000, maxy = -1000000;
            for (let i = 0; i < points.length; i++) {
                minx = Math.min(minx, points[i][0]);
                miny = Math.min(miny, points[i][1]);
                maxx = Math.max(maxx, points[i][0]);
                maxy = Math.max(maxy, points[i][1]);
            }
            let dx = maxx - minx, dy = maxy - miny;
            let dxy = Math.max(dx, dy);
            let midx = dx * 0.5 + minx, midy = dy * 0.5 + miny;
            return [
                [midx - 10 * dxy, midy - 10 * dxy],
                [midx, midy + 10 * dxy],
                [midx + 10 * dxy, midy - 10 * dxy]
            ]
        }
 
        // вычисление центра и радиуса описанной окружности вокруг треугольника
        function circumcircle_of_triangle(points, v1, v2, v3) {
            //console.log(v1, v2, v3);
            let x1 = points[v1][0], y1 = points[v1][1];
            let x2 = points[v2][0], y2 = points[v2][1];
            let x3 = points[v3][0], y3 = points[v3][1];
            let dy12 = Math.abs(y1 - y2), dy23 = Math.abs(y2 - y3);
            let xc, yc;
            if (dy12 < EPS) {
                let m2  = -((x3 - x2) / (y3 - y2));
                let mx2 = (x2 + x3) / 2, my2 = (y2 + y3) / 2;
                xc  = (x1 + x2) / 2, yc  = m2 * (xc - mx2) + my2;
            }
            else if (dy23 < EPS) {
                let m1  = -((x2 - x1) / (y2 - y1));
                let mx1 = (x1 + x2) / 2, my1 = (y1 + y2) / 2;
                xc  = (x2 + x3) / 2, yc  = m1 * (xc - mx1) + my1;
            }
            else {
                let m1  = -((x2 - x1) / (y2 - y1)), m2  = -((x3 - x2) / (y3 - y2));
                let mx1 = (x1 + x2) / 2, my1 = (y1 + y2) / 2;
                let mx2 = (x2 + x3) / 2, my2 = (y2 + y3) / 2;
                xc  = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
                if (dy12 > dy23) yc =  m1 * (xc - mx1) + my1;
                else yc = m2 * (xc - mx2) + my2;
            }
            let dx = x2 - xc, dy = y2 - yc;
            return {'a': v1, 'b': v2, 'c': v3, 'x': xc, 'y': yc, 'r': dx*dx + dy*dy};
        }
 
        // функция, удаляющая кратные ребра
        function delete_multiples_edges(edges) {
            for (let j = edges.length - 1; j >= 0;) {
                let b = edges[j]; j--;
                let a = edges[j]; j--;
                let n, m;
                for (let i = j; i >= 0;) {
                    n = edges[i]; i--;
                    m = edges[i]; i--;
                    if (a === m && b === n) {
                        edges.splice(j + 1, 2);
                        edges.splice(i + 1, 2);
                        break;
                    }
                    if (a === n && b === m) {
                        edges.splice(j + 1, 2);
                        edges.splice(i + 1, 2);
                        break;
                    }
                }
            }
        }
 
        // функция, находящая триангуляцию
        function triangulate(points) {
            let n = points.length;
            if (n < 3) return []; // треугольников нет
            points = points.slice(0); // копия массива
 
            // массив индексов, отсортированных по координате икс
            let ind = [];
            for (let i = 0; i < n; i++) ind.push(i);
            ind.sort(function(l, r) {
                return points[r][0] - points[l][0];
            })
 
            // находим треугольник, содержащий все точки, и вставлем его в конец массива с вершинами
            let big = big_triangle(points);
            points.push(big[0]);
            points.push(big[1]);
            points.push(big[2]);
 
            let cur_points = [circumcircle_of_triangle(points, n, n + 1, n + 2)];
            let ans = [];
            let edges = [];
 
            // перебираем все точки
            for (let i = ind.length - 1; i >= 0; i--) {
                // перебираем все треугольники
                // если точка находится внутри треугольника, то нужно его удалить
                for (let j = cur_points.length - 1; j >= 0; j--) {
                    // если точка справа от описанной окружности, то треугольник проверять больше не нужно
                    // точки отсортированы и поэтому тоже будут справа
                    let dx = points[ind[i]][0] - cur_points[j].x;
                    if (dx > 0 && dx * dx > cur_points[j].r) {
                        ans.push(cur_points[j]);
                        cur_points.splice(j, 1);
                        continue;
                    }
 
                    // если точка вне окружности, то треугольник изменять не нужно
                    let dy = points[ind[i]][1] - cur_points[j].y;
                    if (dx * dx + dy * dy - cur_points[j].r > EPS) {
                        continue;
                    }
                    // удаляем треугольник и добавляем его стороны в список ребер
                    edges.push(
                        cur_points[j].a, cur_points[j].b,
                        cur_points[j].b, cur_points[j].c,
                        cur_points[j].c, cur_points[j].a
                    );
                    cur_points.splice(j, 1);
                }
                // удаляем кратные ребра
                delete_multiples_edges(edges);
                // создаем новые треугольники последовательно по списку ребер
                for (let j = edges.length - 1; j >= 0;) {
                    let b = edges[j]; j--;
                    if (j < 0) break;
                    let a = edges[j]; j--;
                    cur_points.push(circumcircle_of_triangle(points, a, b, ind[i]));
                } 
                edges = [];
            }
            // формируем массив с триангуляцией
            for (let i = cur_points.length - 1; i >= 0; i--) {
                ans.push(cur_points[i]);
            }
            let tr = []
            for (let i = 0; i < ans.length; i++) {
                if (ans[i].a < n && ans[i].b < n && ans[i].c < n) {
                    tr.push(ans[i].a, ans[i].b, ans[i].c);
                }
            }
            console.log(tr);
            return tr;
        }
 
        // отрисовка триангуляции
        console.log(pts);
        ctx.strokeStyle = "black";
        let triangles = triangulate(pts);
        // отрисовка сгенерированных точек
        for (let i = 0; i < pts.length; i++) {
            ctx.beginPath();
            ctx.arc(pts[i][0], pts[i][1], 5, 0, 2 * Math.PI);
            ctx.closePath();
            ctx.fill();
        }
        // отрисовка треугольников
        for (let i = 0; i < triangles.length;) {
            ctx.beginPath();
            ctx.moveTo(pts[triangles[i]][0], pts[triangles[i]][1]); i++;
            ctx.lineTo(pts[triangles[i]][0], pts[triangles[i]][1]); i++;
            ctx.lineTo(pts[triangles[i]][0], pts[triangles[i]][1]); i++;
            ctx.closePath();
            ctx.stroke();
        }
    </script>
</body>
</html>

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