Триангуляция различных многоугольников

<canvas id = "canvas" width = "500" height = "500"></canvas><br>
 
<div>
    <select id = "select">
        <option value = "0"> Heart 1 </option>
        <option value = "1"> Heart 2 </option>
        <option value = "2"> Star    </option>
        <option value = "3"> Square  </option>
        <option value = "4"> Arrow   </option>
    </select>
    <button onclick = "init()"> Select </button>
</div>
 
<script>
    /***** Canvas *****/
    let canvas = document.querySelector("canvas");
    let ctx = canvas.getContext("2d");
    let canvasWidth = canvas.width;
    let canvasHeight = canvas.height;
    let canvasData = ctx.getImageData(0, 0, canvasWidth, canvasHeight);
 
    // Обновляем canvas
    function updateCanvas() {
        ctx.putImageData(canvasData, 0, 0);
    }
 
    /***** Графическая библиотека *****/
    // Рисуем пиксель
    function drawPixel(x, y, color = {r: 255, g: 0, b: 0, a: 255}) {
        const index = (x + y * canvasWidth) * 4;
        canvasData.data[index + 0] = color.r;
        canvasData.data[index + 1] = color.g;
        canvasData.data[index + 2] = color.b;
        canvasData.data[index + 3] = color.a;
        return color;
    }
 
    // Рисуем отрезок по алгоритму Брезенхема
    function drawLine(x1, y1, x2, y2, color = {r: 255, g: 0, b: 0, a: 255}) {
        const deltaX = Math.abs(x2 - x1);
        const deltaY = Math.abs(y2 - y1);
 
        const signX = x1 < x2 ? 1 : -1;
        const signY = y1 < y2 ? 1 : -1;
 
        let error = deltaX - deltaY;
        drawPixel(x2, y2, color);
 
        while (x1 !== x2 || y1 !== y2) {
            drawPixel(x1, y1, color);
            let error2 = error * 2;
 
            if (error2 > -deltaY) {
                error -= deltaY;
                x1 += signX;
            }
            if (error2 < deltaX) {
                error += deltaX;
                y1 += signY;
            }
        }
    }
 
    // Рисуем треугольник
    function drawTriangle(x1, y1, x2, y2, x3, y3, color = {r: 255, g: 0, b: 0, a: 255}) {
        drawLine(x1, y1, x2, y2, color);
        drawLine(x2, y2, x3, y3, color);
        drawLine(x3, y3, x1, y1, color);
    }
 
    // Рисуем многоугольник
    function drawPolygon(color =  {r: 0, g: 0, b: 0, a: 255}) {
        for (let i = 0; i < polygon.length; i++) {
            const newI = (i + 1 === polygon.length ? 0 : i + 1);
            drawLine(polygon[i].x, polygon[i].y, polygon[newI].x, polygon[newI].y, color);
        }
    }
 
    // Получаем цвет пикселя
    function getColor(x, y) {
        const index = (x + y * canvasWidth) * 4;
        const r = canvasData.data[index + 0];
        const g = canvasData.data[index + 1];
        const b = canvasData.data[index + 2];
        const a = canvasData.data[index + 3];
        return {r: r, g: g, b: b, a: a};
    }
 
    // Заливка 4-х связным алгоритмом
    function fill(x, y, color = {r: 255, g: 0, b: 0, a: 255}) {
        let startColor = getColor(x, y);
 
        if (startColor.r === color.r &&
            startColor.g === color.g &&
            startColor.b === color.b &&
            startColor.a === color.a) {
            return;
        }
 
        let q = [{x: x, y: y}];
        for (let i = 0; i !== q.length; i++) {
            let x = q[i].x, y = q[i].y;
 
            let newColor = getColor(x, y);
            if (x >= 0 && y >= 0 && x < canvasWidth && y < canvasHeight && newColor.r === startColor.r
                && newColor.g === startColor.g && newColor.b === startColor.b && newColor.a === startColor.a) {
                newColor = drawPixel(x, y, color);
 
                let length = q.length;
                q[length + 0] = {x: x + 1, y: y};
                q[length + 1] = {x: x - 1, y: y};
                q[length + 2] = {x: x, y: y + 1};
                q[length + 3] = {x: x, y: y - 1};
            }
        }
    }
 
    // Заливка прямоугольника
    function fillRectangle(x1, y1, width, height, color = {r: 255, g: 0, b: 0, a: 255}) {
        for (let i = y1; i <= y1 + height; i++) {
            drawLine(x1, i, x1 + width, i, color);
        }
    }
 
    /***** Создаем многоулогьник *****/
    // Описываем точку
    class Point {
        constructor(x, y) {
            this.x = x;
            this.y = y;
        }
    }
 
    // Многоугольник
    let polygon = [];
 
    // Заполняем массив polygon
    function createPolygon() {
        polygon = [];
        fillRectangle(0, 0, canvasWidth, canvasHeight, {r: 142, g: 67, b: 231, a: 255});
 
        const selectValue = parseInt(document.getElementById("select").value);
 
        let xC = Math.floor(canvasWidth / 2), yC =  Math.floor(canvas.height / 2);
        switch (selectValue) {
            case 0:
                // Polygon 1
                polygon.push(new Point(xC +  0, yC - 40 -  0));
 
                // left
                polygon.push(new Point(xC - 20, yC - 40 - 20));
                polygon.push(new Point(xC - 40, yC - 40 - 30));
                polygon.push(new Point(xC - 60, yC - 40 - 30));
                polygon.push(new Point(xC - 80, yC - 40 - 20));
                polygon.push(new Point(xC - 90, yC - 40 -  0));
                polygon.push(new Point(xC - 90, yC - 40 + 20));
                polygon.push(new Point(xC - 80, yC - 40 + 50));
 
                polygon.push(new Point(xC -  0, yC - 40 + 140));
 
                // right
                polygon.push(new Point(xC + 80, yC - 40 + 50));
                polygon.push(new Point(xC + 90, yC - 40 + 20));
                polygon.push(new Point(xC + 90, yC - 40 -  0));
                polygon.push(new Point(xC + 80, yC - 40 - 20));
                polygon.push(new Point(xC + 60, yC - 40 - 30));
                polygon.push(new Point(xC + 40, yC - 40 - 30));
                polygon.push(new Point(xC + 20, yC - 40 - 20));
                break;
            case 1:
                // Polygon 2
                polygon.push(new Point(xC -  0, yC - 40 + 140));
 
                // right
                polygon.push(new Point(xC + 80, yC - 40 + 50));
                polygon.push(new Point(xC + 90, yC - 40 + 20));
                polygon.push(new Point(xC + 90, yC - 40 -  0));
                polygon.push(new Point(xC + 80, yC - 40 - 20));
                polygon.push(new Point(xC + 60, yC - 40 - 30));
                polygon.push(new Point(xC + 40, yC - 40 - 30));
                polygon.push(new Point(xC + 20, yC - 40 - 20));
 
                polygon.push(new Point(xC +  0, yC - 40 -  0));
 
                // left
                polygon.push(new Point(xC - 20, yC - 40 - 20));
                polygon.push(new Point(xC - 40, yC - 40 - 30));
                polygon.push(new Point(xC - 60, yC - 40 - 30));
                polygon.push(new Point(xC - 80, yC - 40 - 20));
                polygon.push(new Point(xC - 90, yC - 40 -  0));
                polygon.push(new Point(xC - 90, yC - 40 + 20));
                polygon.push(new Point(xC - 80, yC - 40 + 50));
                break;
            case 2:
                // Polygon 3
                let x, y, radius = 200;
                for (let angle = 18; angle <= 360; angle += 72) {
                    x = Math.floor(xC + radius * Math.cos(angle * Math.PI / 180));
                    y = Math.floor(yC - radius * Math.sin(angle * Math.PI / 180));
                    polygon.push(new Point(x, y));
                    x = Math.floor(xC + radius * 2 / 5 * Math.cos((angle + 36) * Math.PI / 180));
                    y = Math.floor(yC - radius * 2 / 5 * Math.sin((angle + 36) * Math.PI / 180));
                    polygon.push(new Point(x, y));
                }
                break;
            case 3:
                // Polygon 4
                polygon.push(new Point(xC + 80, yC - 80));
                polygon.push(new Point(xC - 80, yC - 80));
                polygon.push(new Point(xC - 80, yC + 80));
                polygon.push(new Point(xC + 80, yC + 80));
                break;
            case 4:
                // Polygon 5
                polygon.push(new Point(xC +  0, yC - 60));
                polygon.push(new Point(xC - 60, yC + 60));
                polygon.push(new Point(xC +  0, yC +  0));
                polygon.push(new Point(xC + 60, yC + 60));
                break;
            default:
                console.log("default", selectValue);
                break;
        }
    }
 
    /***** Триангуляция *****/
    // Считает площадь треугольника
    function calculateSquare(A, B, C) {
        return 1 / 2 * Math.abs((B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y));
    }
 
    // Принадлежит ли точка треугольнику?
    function inTriangle(A, B, C, D) {
        return calculateSquare(A, B, C) === calculateSquare(A, B, D) + calculateSquare(A, C, D) + calculateSquare(B, D, C);
    }
 
    // Левая тройка векторов?
    function isLeft(A, B, C) {
        const AB = {
                x: B.x - A.x,
                y: B.y - A.y
            },
            AC = {
                x: C.x - A.x,
                y: C.y - A.y
            };
 
        return AB.x * AC.y - AC.x * AB.y < 0;
    }
 
    // Есть ли другие точки внутри рассматриваемого треугольника?
    function hasPointOfPolygon(points) {
        const A = points[0],
              B = points[1],
              C = points[2];
 
        for (let p = 3; p < points.length; p++) {
            if (inTriangle(A, B, C, points[p])) return true;
        }
 
        return false;
    }
 
    // Триангуляция
    function triangulate(point = new Point(260, 250), color = {r: 255, g: 255, b: 255, a: 255}) {
        while (polygon.length >= 3) {
            if (isLeft(polygon[0], polygon[1], polygon[2]) && !hasPointOfPolygon(polygon)) {
 
                const x1 = polygon[0].x,
                    y1 = polygon[0].y;
                const x2 = polygon[1].x,
                    y2 = polygon[1].y;
                const x3 = polygon[2].x,
                    y3 = polygon[2].y;
                drawTriangle(x1, y1, x2, y2, x3, y3, color);
 
                if (inTriangle(polygon[0], polygon[1], polygon[2], point)) {
                    let cx = Math.floor((x1 + x2 + x3) / 3);
                    let cy = Math.floor((y1 + y2 + y3) / 3);
                    fill(cx, cy);
                }
 
                polygon.splice(1, 1);
            } else {
                const tmp = polygon[0];
                polygon.shift();
                polygon.push(tmp);
            }
        }
    }
 
    /***** Старт *****/
    // Функция с которой программа начинает работу
    function init() {
        createPolygon();
        drawPolygon();
        triangulate();
        updateCanvas();
    }
</script>