【數學篇】08 # 如何利用三角剖分和向量操作描述并處理多邊形？

說明

【跟月影學可視化】學習筆記。

圖形學中的多邊形是什麼？

多邊形又可以分為簡單多邊形和複雜多邊形。

簡單多邊形：如果一個多邊形的每條邊除了相鄰的邊以外，不和其他邊相交。
凸多邊形：如果一個多邊形中的每個内角都不超過 180°。

不同的圖形系統如何填充多邊形？

1. Canvas2D 如何填充多邊形？

Canvas2D 的 fill 還支援兩種填充規則：

nonzero：不管有沒有相交的邊，隻要是由邊圍起來的區域都一律填充。
evenodd：根據重疊區域是奇數還是偶數來判斷是否填充的

<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Canvas2D 如何填充多邊形</title>
        <style>canvas {
                border: 1px dashed salmon;
            }</style>
    </head>
    <body>
        <canvas width="512" height="512"></canvas>
        <script type="module">import { Vector2D } from "./common/lib/vector2d.js";

            const canvas = document.querySelector("canvas");
            const ctx = canvas.getContext("2d");
            const { width, height } = canvas;
            const w = 0.5 * width,
                h = 0.5 * height;
            ctx.translate(w, h);
            ctx.scale(1, -1);

            // 繪制坐标軸
            function drawAxis() {
                ctx.save();
                ctx.strokeStyle = "#ccc";
                ctx.beginPath();
                ctx.moveTo(-w, 0);
                ctx.lineTo(w, 0);
                ctx.stroke();
                ctx.beginPath();
                ctx.moveTo(0, -h);
                ctx.lineTo(0, h);
                ctx.stroke();
                ctx.restore();
            }
            drawAxis();

            // nonzero：不管有沒有相交的邊，隻要是由邊圍起來的區域都一律填充。
            // evenodd：根據重疊區域是奇數還是偶數來判斷是否填充的
            function draw(
                context,
                points,
                { fillStyle = "salmon", close = false, rule = "nonzero" } = {}
            ) {
                context.beginPath();
                context.moveTo(...points[0]);
                for (let i = 1; i < points.length; i++) {
                    context.lineTo(...points[i]);
                }
                if (close) context.closePath();
                context.fillStyle = fillStyle;
                context.fill(rule);
            }

            // 建構多邊形的頂點,這裡來5個
            const points = [new Vector2D(0, 100)];
            for (let i = 1; i <= 4; i++) {
                const p = points[0].copy().rotate(i * Math.PI * 0.4);
                points.push(p);
            }

            // 繪制正五邊形
            const polygon = [...points]; // polygon 數組是正五邊形的頂點數組
            ctx.save();
            ctx.translate(-128, 0);
            draw(ctx, polygon);
            ctx.restore();

            console.log("polygon--->", polygon);

            // 繪制正五角星
            const stars = [
                points[0],
                points[2],
                points[4],
                points[1],
                points[3],
            ]; // stars 數組是把正五邊形的頂點順序交換之後，構成的五角星的頂點數組。
            ctx.save();
            ctx.translate(128, 0);
            draw(ctx, stars);
            // draw(ctx, stars, {rule: 'evenodd'});
            ctx.restore();</script>
    </body>
</html>

如果改成

rule: 'evenodd'

繪制五角星

draw(ctx, stars, {rule: 'evenodd'});

2. WebGL 如何填充多邊形？

将多邊形分割成若幹個三角形的操作，在圖形學中叫做三角剖分（Triangulation）。對 3D 模型，WebGL 在繪制的時候，也需要使用三角剖分，而 3D 的三角剖分又被稱為網格化（Meshing）。

推薦學習：Delaunay Triangulation In Two and Three Dimensions

可以使用下面庫來對多邊形進行三角剖分：

earcut
tess2.js
cdt2d

以最簡單的 Earcut 庫（代碼：https://github.com/mapbox/earcut/blob/master/src/earcut.js）為例，來了解 WebGL 填充多邊形的過程

以下面這個多邊形為例子，我們利用 Earcut 庫對其進行三角剖分

<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>WebGL 如何填充多邊形</title>
        <style>canvas {
                border: 1px dashed salmon;
            }</style>
    </head>
    <body>
        <canvas width="512" height="512"></canvas>
        <script type="module">const canvas = document.querySelector("canvas");
            const gl = canvas.getContext("webgl");
            const vertex = `
                attribute vec2 position;
                void main() {
                    gl_PointSize = 1.0;
                    gl_Position = vec4(position, 1.0, 1.0);
                }
            `;

            const fragment = `
                precision mediump float;
                void main() {
                    gl_FragColor = vec4(1.0, 0.0, 0.0, 1.0);
                }
            `;

            const vertexShader = gl.createShader(gl.VERTEX_SHADER);
            gl.shaderSource(vertexShader, vertex);
            gl.compileShader(vertexShader);

            const fragmentShader = gl.createShader(gl.FRAGMENT_SHADER);
            gl.shaderSource(fragmentShader, fragment);
            gl.compileShader(fragmentShader);

            const program = gl.createProgram();
            gl.attachShader(program, vertexShader);
            gl.attachShader(program, fragmentShader);
            gl.linkProgram(program);
            gl.useProgram(program);

            // 不規則多邊形的頂點
            const vertices = [
                [-0.7, 0.5],
                [-0.4, 0.3],
                [-0.25, 0.71],
                [-0.1, 0.56],
                [-0.1, 0.13],
                [0.4, 0.21],
                [0, -0.6],
                [-0.3, -0.3],
                [-0.6, -0.3],
                [-0.45, 0.0],
            ];

            // 使用 Earcut 庫進行三角剖分：Earcut 庫隻接受扁平化的定點資料
            import { earcut } from "./common/lib/earcut.js";
            // 使用數組的 flat 方法将頂點扁平化
            const points = vertices.flat();
            // 進行三角剖分
            const triangles = earcut(points);

            const position = new Float32Array(points);
            const cells = new Uint16Array(triangles);

            const pointBuffer = gl.createBuffer();
            gl.bindBuffer(gl.ARRAY_BUFFER, pointBuffer);
            gl.bufferData(gl.ARRAY_BUFFER, position, gl.STATIC_DRAW);

            const vPosition = gl.getAttribLocation(program, "position");
            gl.vertexAttribPointer(vPosition, 2, gl.FLOAT, false, 0, 0);
            gl.enableVertexAttribArray(vPosition);

            const cellsBuffer = gl.createBuffer();
            gl.bindBuffer(gl.ELEMENT_ARRAY_BUFFER, cellsBuffer);
            gl.bufferData(gl.ELEMENT_ARRAY_BUFFER, cells, gl.STATIC_DRAW);

            gl.clear(gl.COLOR_BUFFER_BIT);
            gl.drawElements(gl.TRIANGLES, cells.length, gl.UNSIGNED_SHORT, 0);
            // 用描邊 LINE_STRIP 代替填充 TRIANGLES
            // gl.drawElements(gl.LINE_STRIP, cells.length, gl.UNSIGNED_SHORT, 0);</script>
    </body>
</html>

可以通過用描邊 LINE_STRIP 代替填充 TRIANGLES 就可以清晰的看到這個多邊形被分割成了多個三角形

// 用描邊LINE_STRIP 代替填充 TRIANGLES
gl.drawElements(gl.LINE_STRIP, cells.length, gl.UNSIGNED_SHORT, 0);

注意：三角剖分後傳回的數組裡的值是頂點資料的 index。

如何判斷點在多邊形内部？

判斷一個點是否在多邊形内部時，需要先對多邊形進行三角剖分，然後判斷該點是否在其中一個三角形内部。

1. Canvas2D 如何判斷點在多邊形内部？

我們先使用 canvas2d 繪制出來上面的多邊形

<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Canvas2D 如何判斷點在多邊形内部</title>
        <style>canvas {
                border: 1px dashed salmon;
            }</style>
    </head>
    <body>
        <canvas width="512" height="512"></canvas>
        <script type="module">const vertices = [
                [-0.7, 0.5],
                [-0.4, 0.3],
                [-0.25, 0.71],
                [-0.1, 0.56],
                [-0.1, 0.13],
                [0.4, 0.21],
                [0, -0.6],
                [-0.3, -0.3],
                [-0.6, -0.3],
                [-0.45, 0.0],
            ];

            const canvas = document.querySelector("canvas");
            const ctx = canvas.getContext("2d");
            const { width, height } = canvas;
            ctx.translate(0.5 * width, 0.5 * height);
            ctx.scale(1, -1);

            const poitions = vertices.map(([x, y]) => [x * 256, y * 256]);

            function draw(
                ctx,
                points,
                strokeStyle = "salmon",
                fillStyle = null
            ) {
                ctx.strokeStyle = strokeStyle;
                ctx.beginPath();
                ctx.moveTo(...points[0]);
                for (let i = 1; i < points.length; i++) {
                    ctx.lineTo(...points[i]);
                }
                ctx.closePath();
                if (fillStyle) {
                    ctx.fillStyle = fillStyle;
                    ctx.fill();
                }
                ctx.stroke();
            }

            draw(ctx, poitions, "transparent", "salmon");
            // draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'salmon');

            const { left, top } = canvas.getBoundingClientRect();

            canvas.addEventListener("mousemove", (evt) => {
                const { x, y } = evt;
                // 坐标轉換
                const offsetX = x - left;
                const offsetY = y - top;

                ctx.clearRect(-256, -256, 512, 512);

                if (ctx.isPointInPath(offsetX, offsetY)) {
                    draw(ctx, poitions, "transparent", "green");
                    // draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'green');
                } else {
                    draw(ctx, poitions, "transparent", "salmon");
                    // draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'salmon');
                }
            });</script>
    </body>
</html>

滑鼠放上去也是可以變色的

我們放開那個小多邊形的注釋代碼

我們發現滑鼠隻有放在小三角形裡的時候才會變色

因為 isPointInPath 方法隻能對目前繪制的圖形生效。僅能判斷滑鼠是否在最後一次繪制的小三角形内，是以大多邊形就沒有被識别出來。

解決方法：在繪制的過程中擷取每個圖形的 isPointInPath 結果。

<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Canvas2D 如何判斷點在多邊形内部2</title>
        <style>canvas {
                border: 1px dashed salmon;
            }</style>
    </head>
    <body>
        <canvas width="512" height="512"></canvas>
        <script type="module">const vertices = [
                [-0.7, 0.5],
                [-0.4, 0.3],
                [-0.25, 0.71],
                [-0.1, 0.56],
                [-0.1, 0.13],
                [0.4, 0.21],
                [0, -0.6],
                [-0.3, -0.3],
                [-0.6, -0.3],
                [-0.45, 0.0],
            ];

            const canvas = document.querySelector("canvas");
            const ctx = canvas.getContext("2d");
            const { width, height } = canvas;
            ctx.translate(0.5 * width, 0.5 * height);
            ctx.scale(1, -1);

            const poitions = vertices.map(([x, y]) => [x * 256, y * 256]);

            function draw(
                ctx,
                points,
                strokeStyle = "salmon",
                fillStyle = null
            ) {
                ctx.strokeStyle = strokeStyle;
                ctx.beginPath();
                ctx.moveTo(...points[0]);
                for (let i = 1; i < points.length; i++) {
                    ctx.lineTo(...points[i]);
                }
                ctx.closePath();
                if (fillStyle) {
                    ctx.fillStyle = fillStyle;
                    ctx.fill();
                }
                ctx.stroke();
            }
            
            function isPointInPath(ctx, x,) {
                // 根據ctx重新clone一個新的canvas對象出來
                const cloned = ctx.canvas.cloneNode().getContext("2d");
                cloned.translate(0.5 * width, 0.5 * height);
                cloned.scale(1, -1);
                let ret = false;
                // 繪制多邊形，然後判斷點是否在圖形内部
                draw(cloned, poitions, "transparent", "salmon");
                ret |= cloned.isPointInPath(x, y);
                if (!ret) {
                    // 如果不在，在繪制小三角形，然後判斷點是否在圖形内部
                    draw(cloned, [[100, 100], [100, 200], [150, 200]], 'transparent', 'salmon');
                    ret |= cloned.isPointInPath(x, y);
                }
                return ret;
            }

            draw(ctx, poitions, "transparent", "salmon");
            draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'salmon');

            const { left, top } = canvas.getBoundingClientRect();

            canvas.addEventListener("mousemove", (evt) => {
                const { x, y } = evt;
                // 坐标轉換
                const offsetX = x - left;
                const offsetY = y - top;

                ctx.clearRect(-256, -256, 512, 512);

                if (isPointInPath(ctx, offsetX, offsetY)) {
                    draw(ctx, poitions, "transparent", "green");
                    draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'green');
                } else {
                    draw(ctx, poitions, "transparent", "salmon");
                    draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'salmon');
                }
            });</script>
    </body>
</html>

2. 實作通用的 isPointInPath 方法

三角形有一個非常簡單的方法可以判斷點是否在其中。

已知一個三角形的三條邊分别是向量 a、b、c，平面上一點 u 連接配接三角形三個頂點的向量分别為 u1、u2、u3，那麼 u 點在三角形内部的充分必要條件是：u1 X a、u2 X b、u3 X c 的符号相同。

當點 u 在三角形 a、b、c 内時，因為 u1到 a、u2到 b、u3到 c 的小角旋轉方向是相同的（這裡都為順時針），是以 u1 X a、u2 X b、u3 X c 要麼同正，要麼同負。當點 v 在三角形外時，v1到 a 方向是順時針，v2到 b 方向是逆時針，v3到 c 方向又是順時針，是以它們叉乘的結果符号并不相同。

左圖是點u和a不在一條直線上，右圖是點u和a在一條直線上

隻有當 u1 和 a 的比值在 0 到 1 之間時，才能說明點在三角形的邊上。

<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>實作通用的 isPointInPath 方法</title>
        <style>canvas {
                border: 1px dashed salmon;
            }</style>
    </head>
    <body>
        <canvas width="512" height="512"></canvas>
        <script type="module">import { Vector2D } from "./common/lib/vector2d.js";
            import { earcut } from "./common/lib/earcut.js";

            // 判斷點是否在三角形裡面
            function inTriangle(p1, p2, p3,) {
                const a = p2.copy().sub(p1);
                const b = p3.copy().sub(p2);
                const c = p1.copy().sub(p3);

                const u1 = point.copy().sub(p1);
                const u2 = point.copy().sub(p2);
                const u3 = point.copy().sub(p3);

                const s1 = Math.sign(a.cross(u1));
                let p = a.dot(u1) / a.length ** 2;
                if (s1 === 0 && p >= 0 && p <= 1) return true;

                const s2 = Math.sign(b.cross(u2));
                p = b.dot(u1) / b.length ** 2;
                if (s2 === 0 && p >= 0 && p <= 1) return true;

                const s3 = Math.sign(c.cross(u3));
                p = c.dot(u1) / c.length ** 2;
                if (s3 === 0 && p >= 0 && p <= 1) return true;

                return s1 === s2 && s2 === s3;
            }

            // 判斷點是否在多邊形裡面
            function isPointInPath({ vertices, cells },) {
                let ret = false;
                for (let i = 0; i < cells.length; i += 3) {
                    const p1 = new Vector2D(...vertices[cells[i]]);
                    const p2 = new Vector2D(...vertices[cells[i + 1]]);
                    const p3 = new Vector2D(...vertices[cells[i + 2]]);
                    if (inTriangle(p1, p2, p3, point)) {
                        ret = true;
                        break;
                    }
                }
                return ret;
            }

            const canvas = document.querySelector("canvas");
            const gl = canvas.getContext("webgl");

            const vertex = `
                attribute vec2 position;
                uniform vec4 u_color;

                varying vec4 vColor;

                void main() {
                    gl_PointSize = 1.0;
                    gl_Position = vec4(position, 1.0, 1.0);
                    vColor = u_color;
                }
            `;

            const fragment = `
                precision mediump float;
                varying vec4 vColor;

                void main() {
                    gl_FragColor = vColor;
                }    
            `;

            const vertexShader = gl.createShader(gl.VERTEX_SHADER);
            gl.shaderSource(vertexShader, vertex);
            gl.compileShader(vertexShader);

            const fragmentShader = gl.createShader(gl.FRAGMENT_SHADER);
            gl.shaderSource(fragmentShader, fragment);
            gl.compileShader(fragmentShader);

            const program = gl.createProgram();
            gl.attachShader(program, vertexShader);
            gl.attachShader(program, fragmentShader);
            gl.linkProgram(program);
            gl.useProgram(program);

            const vertices = [
                [-0.7, 0.5],
                [-0.4, 0.3],
                [-0.25, 0.71],
                [-0.1, 0.56],
                [-0.1, 0.13],
                [0.4, 0.21],
                [0, -0.6],
                [-0.3, -0.3],
                [-0.6, -0.3],
                [-0.45, 0.0],
            ];

            const points = vertices.flat();
            const triangles = earcut(points);
            
            console.log("triangles---->", triangles);

            const position = new Float32Array(points);
            const cells = new Uint16Array(triangles);

            const pointBuffer = gl.createBuffer();
            gl.bindBuffer(gl.ARRAY_BUFFER, pointBuffer);
            gl.bufferData(gl.ARRAY_BUFFER, position, gl.STATIC_DRAW);

            const vPosition = gl.getAttribLocation(program, "position");
            gl.vertexAttribPointer(vPosition, 2, gl.FLOAT, false, 0, 0);
            gl.enableVertexAttribArray(vPosition);

            const cellsBuffer = gl.createBuffer();
            gl.bindBuffer(gl.ELEMENT_ARRAY_BUFFER, cellsBuffer);
            gl.bufferData(gl.ELEMENT_ARRAY_BUFFER, cells, gl.STATIC_DRAW);

            const colorLoc = gl.getUniformLocation(program, "u_color");
            gl.uniform4fv(colorLoc, [1, 0, 0, 1]);

            gl.clear(gl.COLOR_BUFFER_BIT);
            gl.drawElements(gl.TRIANGLES, cells.length, gl.UNSIGNED_SHORT, 0);

            const { left, top } = canvas.getBoundingClientRect();
            canvas.addEventListener("mousemove", (evt) => {
                const { x, y } = evt;
                // 坐标轉換
                const offsetX = (2 * (x - left)) / canvas.width - 1.0;
                const offsetY = 1.0 - (2 * (y - top)) / canvas.height;

                gl.clear(gl.COLOR_BUFFER_BIT);

                const colorLoc = gl.getUniformLocation(program, "u_color");
                if (
                    isPointInPath(
                        { vertices, cells },
                        new Vector2D(offsetX, offsetY)
                    )
                ) {
                    gl.uniform4fv(colorLoc, [0, 0.5, 0, 1]);
                } else {
                    gl.uniform4fv(colorLoc, [1, 0, 0, 1]);
                }

                gl.drawElements(gl.TRIANGLES, cells.length, gl.UNSIGNED_SHORT, 0);
            });</script>
    </body>
</html>

【數學篇】08 # 如何利用三角剖分和向量操作描述并處理多邊形？

說明

圖形學中的多邊形是什麼？

不同的圖形系統如何填充多邊形？

1. Canvas2D 如何填充多邊形？

2. WebGL 如何填充多邊形？

如何判斷點在多邊形内部？

1. Canvas2D 如何判斷點在多邊形内部？

2. 實作通用的 isPointInPath 方法

繼續閱讀

Spring MVC 自學雜記（五） -- SpringMVC與前台的json資料互動

HTML addEventListener() 方法和attachEvent()差別分析

web前端布局練手項目

Django之驗證碼（十七）驗證碼

Vue項目 - 單檔案元件和Vue中的路由

龍珠訓練營task04

趕工心得（一）

一個小小的移動web版音樂播放器

Docker - Dockerfile之ADD、COPY、WORKDIR、USER、EXPOSE指令詳解

Compile workrave under windows &ndash; My exprience 在Windows上編譯Workrave

門戶通專訪草根站長九天狼：做站貴在堅持

tabpanel 使用問題

為什麼把CSS放頭部，script放下面

CSS之折疊菜單

web開發之前後端渲染

403 Forbidden，You don't have permission to access / on this server.Forbidden