第九章：多边形与几何处理

欢迎回来！这一章我们要聊的是渲染管线中一个非常基础但极其重要的主题——多边形与几何处理。如果说之前的章节让你学会了"怎么画"，那么这一章就是教你"画什么"以及"怎么把任意形状变成 GPU 能画的东西"。

我们会从最简单的多边形填充规则讲起，一路深入到三角剖分、点在多边形内的检测，最后还会聊线条的渲染——没错，GPU 其实根本不会画"线"，它画的都是三角形！

准备好了吗？让我们开始吧！

多边形填充规则：nonzero 与 evenodd
环绕数（Winding Number）的概念
多边形三角剖分：为什么 GPU 只画三角形
Earcut 算法基础
点在多边形内的检测
线条渲染：端帽、连接与斜接限制
通过几何挤压实现粗线条渲染
将折线转换为三角形带
常见问题 Q&A

1. 多边形填充规则：nonzero 与 evenodd

1.1 生活类比：油漆桶和迷宫

想象一下你手里有一张纸，上面画了一个五角星。现在你要用油漆桶给这个五角星"填充颜色"。

但是等等——五角星的中间有一个五边形的小区域。这个区域到底要不要涂色呢？

这就取决于你的"填充规则"了：

nonzero（非零规则）：只要这个区域被"包围"了，就涂色
evenodd（奇偶规则）：只涂被奇数条边"穿过"的区域

听起来有点抽象？没关系，我们用代码说话。

1.2 本质是什么

这两个规则本质上回答的是同一个问题：给定一个点，它在多边形"内部"还是"外部"？

evenodd（奇偶规则）——"数篱笆"

想象你站在一片草地上，面前有一道篱笆（多边形的边）。你朝任意方向画一条射线，然后数这条射线穿过了多少道篱笆：

穿过奇数道篱笆 → 你在"里面"
穿过偶数道篱笆 → 你在"外面"

这就是 evenodd 的核心思想。它不关心边的方向，只关心"穿过了几次"。

nonzero（非零规则）——"看方向"

nonzero 更聪明一点。它不仅数穿过了多少次，还看每次穿过时边的"方向"。

想象每条边都有一个"方向箭头"（从起点指向终点）。当你的射线穿过一条边时：

如果这条边是"从左到右"穿过你的射线 → 记 +1
如果这条边是"从右到左"穿过你的射线 → 记 -1

最后把所有分数加起来：

总和 不等于 0 → 你在"里面"
总和 等于 0 → 你在"外面"

1.3 代码示例

我们来看看 akira-graphics 中的 polygon-fill 示例：

// c:/Users/10603/Desktop/otherLearn2/akira-graphics/polygon-fill/app.js
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);     // Y轴翻转，让Y向上

// 通用的多边形绘制函数
function draw(context, points, {
  fillStyle = 'black',
  close = false,
  rule = 'nonzero',  // 默认使用 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);  // 传入填充规则
}

// 创建一个正五边形的顶点
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);
}

// 左侧：用 nonzero 规则绘制（默认）
ctx.save();
ctx.translate(-128, 0);
draw(ctx, points);  // nonzero 规则，五角星中间会被填充
ctx.restore();

// 右侧：用 evenodd 规则绘制
// 注意：这里我们按 0->2->4->1->3 的顺序连接顶点，形成一个"自相交"的五角星
const stars = [
  points[0],
  points[2],
  points[4],
  points[1],
  points[3],
];

ctx.save();
ctx.translate(128, 0);
draw(ctx, stars, {rule: 'evenodd'});  // evenodd 规则，中间区域不会被填充
ctx.restore();

运行效果：

左侧（nonzero）：五角星被完整填充，包括中间的五边形区域
右侧（evenodd）：五角星的五个"角"被填充，但中间的五边形区域是"空心"的

1.4 常见误区

误区	真相
"nonzero 和 evenodd 效果总是一样的"	只有在不自相交的多边形上才一样。自相交时（如五角星），结果可能完全不同
"evenodd 更简单，所以更好"	取决于场景。SVG 默认 evenodd，Canvas2D 默认 nonzero。字体渲染通常用 nonzero
"填充规则只影响视觉效果"	错误！它还影响点击检测、碰撞检测等所有"点在内部"的判断

1.5 动手试一试

练习 1.1：修改上面的代码，尝试以下操作：

将左侧的 rule 改为 'evenodd'，观察五角星中间区域的变化

创建一个"8字形"的自相交多边形，分别用两种规则填充，观察差异

思考：在什么场景下 evenodd 更合适？什么场景下 nonzero 更合适？

2. 环绕数（Winding Number）的概念

2.1 生活类比：绕树跑步

想象你在一棵大树周围跑步。如果你绕着树跑了一圈，我们说你的"环绕数"是 1（或 -1，取决于方向）。跑了两圈就是 2。

现在，如果另一个人也在跑，但他跑的方向和你相反。你们相遇时，从某个固定点看，一个人是顺时针绕树，另一个是逆时针。

环绕数就是描述"一个点被多边形边界绕了多少圈"的数字。

2.2 本质是什么

环绕数是一个整数，表示：从被测试点出发，多边形边界围绕它旋转的净圈数。

数学上，对于点 P 和多边形顶点 V0, V1, ..., Vn-1，环绕数可以通过累加每条边对 P 的"角度贡献"来计算：

winding_number = Σ angle(Vi → P → V(i+1)) / (2π)

更简单的方法（射线法）：

从点 P 向右发射一条水平射线，对每条与射线相交的边：

如果边从"下方"穿到"上方"（边的 Y 坐标从小于 Py 变到大于 Py），且交点在 P 的右侧 → 环绕数 +1
如果边从"上方"穿到"下方"，且交点在 P 的右侧 → 环绕数 -1

2.3 nonzero 与环绕数的关系

现在你可以理解 nonzero 规则了：

nonzero 规则：winding_number ≠ 0 → 点在内部
evenodd 规则：|winding_number| % 2 === 1 → 点在内部

也就是说：

nonzero：只要被"包围"了（不管绕了多少圈），就算内部
evenodd：只关心绕了奇数圈还是偶数圈

2.4 代码示例：计算环绕数

/**
 * 计算点 (x, y) 相对于多边形的环绕数
 * @param {Array} polygon - 多边形顶点数组，每个元素为 [x, y]
 * @param {number} x - 测试点的 x 坐标
 * @param {number} y - 测试点的 y 坐标
 * @returns {number} 环绕数
 */
function windingNumber(polygon, x, y) {
  let wn = 0;  // 环绕数
  const n = polygon.length;

  for (let i = 0; i < n; i++) {
    const [x1, y1] = polygon[i];
    const [x2, y2] = polygon[(i + 1) % n];  // 下一条边，最后一个点连回第一个点

    // 检查边是否跨越了水平线 y
    if (y1 <= y) {
      // 边的起点在射线下方或射线上
      if (y2 > y) {
        // 边的终点在射线上方 → 向上穿过射线
        // 计算交点的 x 坐标
        const intersectX = x1 + (y - y1) * (x2 - x1) / (y2 - y1);
        if (intersectX > x) {
          wn++;  // 向上穿过，环绕数 +1
        }
      }
    } else {
      // 边的起点在射线上方
      if (y2 <= y) {
        // 边的终点在射线下方或射线上 → 向下穿过射线
        const intersectX = x1 + (y - y1) * (x2 - x1) / (y2 - y1);
        if (intersectX > x) {
          wn--;  // 向下穿过，环绕数 -1
        }
      }
    }
  }

  return wn;
}

// 使用示例
const pentagon = [
  [0, 100],
  [95, 31],
  [59, -81],
  [-59, -81],
  [-95, 31],
];

console.log(windingNumber(pentagon, 0, 0));    // 输出 1（中心点在内部）
console.log(windingNumber(pentagon, 200, 0));  // 输出 0（外部点）

2.5 常见误区

误区	真相
"环绕数只能是 0 或 1"	自相交多边形可以有任意整数环绕数（如 2, -1, 3 等）
"环绕数和 evenodd 是一回事"	evenodd 只取环绕数的奇偶性，nonzero 才直接使用环绕数
"计算环绕数很复杂"	射线法实现很简单，而且比纯角度计算法高效得多

2.6 动手试一试

练习 2.1：创建一个"双环"多边形（两个嵌套的同心正方形，顶点顺序相反），计算中心点的环绕数。分别用 nonzero 和 evenodd 规则判断中心点是否在内部，观察结果差异。

3. 多边形三角剖分：为什么 GPU 只画三角形

3.1 生活类比：乐高积木

想象你要用乐高积木搭一座城堡。乐高提供各种形状的积木块，但最基础、最通用的是那种 2x4 的标准砖块。

为什么？因为：

简单：标准砖块只有一种形状，生产线最简单
可靠：标准砖块永远不会"搭不稳"
通用：任何复杂的形状都能用标准砖块拼出来

GPU 就是"只提供三角形砖块"的乐高系统。

3.2 本质是什么

GPU 的硬件管线被设计为只处理三角形，原因非常扎实：

原因 1：三角形永远是平的（Planar）

三个点确定一个平面。无论这三个点在三维空间中的什么位置，它们总是共面的。

但四个点呢？四个点不一定共面！在三维空间中，四个点可能形成一个"扭曲"的四边形，渲染时会产生歧义。

原因 2：三角形的内部插值是线性的

三角形内部的任意属性（颜色、纹理坐标、法线等）都可以通过三个顶点的属性进行线性插值（重心坐标插值）。

对于更复杂的多边形，插值会变得非常复杂且可能产生错误。

原因 3：三角形的凹凸性保证

三角形一定是凸的（Convex）。凸多边形的渲染非常简单——内部任意两点的连线都在多边形内。

但凹多边形呢？凹多边形内部可能存在"洞"，渲染时需要特殊处理。

原因 4：硬件简化

如果 GPU 要支持任意多边形，硬件设计会复杂得多：

需要处理凹多边形
需要处理自相交多边形
需要处理非平面的多边形
插值逻辑更复杂

只支持三角形，硬件可以高度优化，速度更快。

3.3 从多边形到三角形

既然 GPU 只画三角形，那任意多边形怎么办？

答案：三角剖分（Triangulation）

将一个 n 边形分解成 (n-2) 个三角形。

例如，一个四边形可以分成 2 个三角形：

四边形顶点：A, B, C, D

三角剖分结果：
  三角形 1：A, B, C
  三角形 2：A, C, D

一个五边形可以分成 3 个三角形，六边形可以分成 4 个……

3.4 代码示例

// 一个简单的三角剖分示例：将凸多边形进行扇形剖分
function fanTriangulation(polygon) {
  const triangles = [];
  // 以第一个顶点为扇心，依次连接后续顶点
  for (let i = 1; i < polygon.length - 1; i++) {
    triangles.push([
      polygon[0],      // 扇心
      polygon[i],      // 当前顶点
      polygon[i + 1],  // 下一个顶点
    ]);
  }
  return triangles;
}

// 示例：五边形的扇形剖分
const pentagon = [
  [0, 100],    // A - 扇心
  [95, 31],    // B
  [59, -81],   // C
  [-59, -81],  // D
  [-95, 31],   // E
];

const triangles = fanTriangulation(pentagon);
console.log(`五边形被分成 ${triangles.length} 个三角形`);
// 输出：五边形被分成 3 个三角形
// triangles[0] = [A, B, C]
// triangles[1] = [A, C, D]
// triangles[2] = [A, D, E]

注意：扇形剖分只适用于凸多边形！凹多边形使用扇形剖分可能会产生"错误"的三角形（三角形的一部分在多边形外部）。

3.5 常见误区

误区	真相
"GPU 可以画四边形"	GPU 的 API（如 `gl.drawArrays`）没有"四边形模式"。你看到的四边形其实是两个三角形拼的
"三角剖分只用于渲染"	三角剖分还用于物理模拟、有限元分析、GIS 系统等
"所有多边形的三角剖分都一样"	不同的剖分策略（扇形、耳切、Delaunay）适用于不同场景
"三角剖分结果唯一"	同一个多边形可以有多种不同的三角剖分方式

3.6 动手试一试

练习 3.1：画一个凹六边形（像一个"L"形），尝试用扇形剖分。你会发现什么问题？思考为什么扇形剖分对凹多边形不适用。

练习 3.2：计算一下：一个 100 边形的三角剖分会生成多少个三角形？如果每个三角形需要 3 个顶点索引，总共需要多少索引？

4. Earcut 算法基础

4.1 生活类比：摘耳朵

想象你有一个形状不规则的饼干（多边形）。你要把它掰成一个个小三角形。

Earcut 算法的策略是：每次找到多边形上一个像"耳朵"一样的凸起部分，把它"摘"下来（形成一个三角形），然后对剩余的部分重复这个过程。

什么是"耳朵"？就是多边形上连续的三个顶点 A-B-C，其中线段 AC 完全在多边形内部，且三角形 ABC 不包含其他顶点。

4.2 本质是什么

Earcut 是一种**耳切法（Ear Clipping）**三角剖分算法。它的核心思想：

任何简单多边形（不自相交）至少有 2 个"耳朵"

算法步骤：

找到多边形的一个"耳朵"（三个连续顶点形成的三角形，且该三角形在多边形内部）
将这个耳朵切下来，作为一个三角形输出
从多边形中移除这个耳朵的"尖端"顶点
重复步骤 1-3，直到只剩下 3 个顶点（最后一个三角形）

4.3 代码示例

我们来看看 akira-graphics 中如何使用 Earcut 库：

// c:/Users/10603/Desktop/otherLearn2/akira-graphics/triangluations/app.js
import {earcut} from '../common/lib/earcut.js';

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

// 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 vertices = [
  [-0.7, 0.5],   // 0
  [-0.4, 0.3],   // 1
  [-0.25, 0.71], // 2
  [-0.1, 0.56],  // 3
  [-0.1, 0.13],  // 4
  [0.4, 0.21],   // 5
  [0, -0.6],     // 6
  [-0.3, -0.3],  // 7
  [-0.6, -0.3],  // 8
  [-0.45, 0.0],  // 9
];

// 将顶点数组扁平化为一维数组
const points = vertices.flat();
// [-0.7, 0.5, -0.4, 0.3, -0.25, 0.71, ...]

// 使用 Earcut 进行三角剖分！
const triangles = earcut(points);
// 返回的是索引数组，如 [0, 1, 2, 0, 2, 3, ...]
// 每三个索引组成一个三角形

console.log(triangles);
// 输出类似：[0, 1, 2, 2, 3, 4, 4, 5, 6, ...]

// 创建 WebGL 缓冲区
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);

4.4 Earcut 的输入输出格式

输入：

// 扁平化的顶点坐标数组
const points = [x0, y0, x1, y1, x2, y2, ...];

// 如果有洞，需要提供每个环的顶点数
const holeIndices = [5];  // 第一个洞从第 5 个顶点开始

// 调用方式
const triangles = earcut(points, holeIndices);

输出：

// 索引数组，每三个一组代表一个三角形
// [i0, i1, i2, j0, j1, j2, k0, k1, k2, ...]
// 三角形 1 由顶点 i0, i1, i2 组成
// 三角形 2 由顶点 j0, j1, j2 组成
// ...

4.5 常见误区

误区	真相
"Earcut 可以处理自相交多边形"	Earcut 要求多边形是简单多边形（不自相交）。自相交多边形需要先预处理
"Earcut 总是产生最优剖分"	Earcut 是贪心算法，不保证最小化三角形数量或最优形状。它追求的是速度和鲁棒性
"Earcut 只能处理 2D"	Earcut 库只处理 2D 坐标，但你可以先投影到 2D 再剖分
"三角剖分后的三角形顺序不重要"	对于背面剔除（Backface Culling），三角形的顶点顺序（顺时针/逆时针）非常重要

4.6 动手试一试

练习 4.1：创建一个带"洞"的多边形（例如一个外圈正方形，内圈小正方形作为洞），使用 Earcut 的 holeIndices 参数进行剖分。观察剖分结果如何正确处理洞。

练习 4.2：手动实现一个简单的耳切算法。给定一个凸五边形，逐步找到并"摘下"每个耳朵，记录每次摘下的三角形。

5. 点在多边形内的检测

5.1 生活类比：激光笔和靶子

想象你拿着一支激光笔，站在一个形状奇怪的房间里。你想知道某个位置是否在房间内部。

你的方法是：从那个位置朝一个方向发射激光，然后数激光穿过了多少堵墙。

穿过奇数堵墙 → 在内部
穿过偶数堵墙 → 在外部

这就是点在多边形检测的基本思想！

5.2 本质是什么

点在多边形检测（Point-in-Polygon Test）是计算机图形学中最基础、最常用的几何查询之一。它的应用包括：

鼠标点击检测（点击了哪个图形？）
碰撞检测
GIS 系统（某个坐标在哪个行政区域内？）
游戏开发（玩家是否进入了某个区域？）

方法 1：Canvas2D 的 `isPointInPath`

最简单的方法——让浏览器帮你做：

// c:/Users/10603/Desktop/otherLearn2/akira-graphics/triangluations/app2d.js
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 positions = vertices.map(([x, y]) => [x * 256, y * 256]);

function draw(ctx, points, strokeStyle = 'black', 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, y) {
  // 克隆一个临时的 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, positions, 'transparent', 'red');
  ret |= cloned.isPointInPath(x, y);

  // 如果不在第一个内，检测是否在第二个多边形内
  if(!ret) {
    draw(cloned, [[100, 100], [100, 200], [150, 200]], 'transparent', 'blue');
    ret |= cloned.isPointInPath(x, y);
  }
  return ret;
}

// 绘制两个多边形
draw(ctx, positions, 'transparent', 'red');
draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'blue');

// 鼠标移动时检测
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, positions, 'transparent', 'green');
    draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'orange');
  } else {
    // 鼠标在多边形外，保持原色
    draw(ctx, positions, 'transparent', 'red');
    draw(ctx, [[100, 100], [100, 200], [150, 200]], 'transparent', 'blue');
  }
});

方法 2：基于三角剖分的检测

如果多边形已经被三角剖分，检测就变得更简单了——只需要检测点是否在任意一个三角形内！

// c:/Users/10603/Desktop/otherLearn2/akira-graphics/triangluations/app-collision.js
import {earcut} from '../common/lib/earcut.js';
import {Vector2D} from '../common/lib/vector2d.js';

/**
 * 判断点是否在三角形内（使用叉积法）
 * 原理：如果点 P 在三角形 ABC 内部，那么：
 *   cross(AB, AP), cross(BC, BP), cross(CA, CP)
 * 这三个叉积的符号应该一致（同为正或同为负）
 */
function inTriangle(p1, p2, p3, point) {
  // 三角形的三条边向量
  const a = p2.copy().sub(p1);  // AB
  const b = p3.copy().sub(p2);  // BC
  const c = p1.copy().sub(p3);  // CA

  // 从三角形顶点到测试点的向量
  const u1 = point.copy().sub(p1);  // AP
  const u2 = point.copy().sub(p2);  // BP
  const u3 = point.copy().sub(p3);  // CP

  // 计算叉积的符号
  const s1 = Math.sign(a.cross(u1));  // cross(AB, AP)
  const s2 = Math.sign(b.cross(u2));  // cross(BC, BP)
  const s3 = Math.sign(c.cross(u3));  // cross(CA, CP)

  // 如果三个叉积符号一致（或某个为0表示在边上），点在三角形内
  return s1 === s2 && s2 === s3;
}

/**
 * 判断点是否在多边形内（基于三角剖分）
 */
function isPointInPath({vertices, cells}, point) {
  // 遍历所有三角形
  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)) {
      return true;  // 点在至少一个三角形内
    }
  }
  return false;  // 点不在任何三角形内
}

// 使用示例：先三角剖分，再检测
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);

// 鼠标移动时检测
canvas.addEventListener('mousemove', (evt) => {
  const {x, y} = evt;
  // 将鼠标坐标转换为 WebGL 坐标系（-1 到 1）
  const offsetX = 2 * (x - left) / canvas.width - 1.0;
  const offsetY = 1.0 - 2 * (y - top) / canvas.height;

  gl.clear(gl.COLOR_BUFFER_BIT);

  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);
});

方法 3：重心坐标（Barycentric Coordinates）

重心坐标是判断点是否在三角形内的另一种优雅方法。

什么是重心坐标？

对于三角形 ABC 内的任意一点 P，都可以表示为：

P = αA + βB + γC

其中 α + β + γ = 1，且 α, β, γ ≥ 0。

这三个系数 (α, β, γ) 就是 P 点相对于三角形 ABC 的重心坐标。

几何意义：

α 表示 P 点"靠近 A"的程度
β 表示 P 点"靠近 B"的程度
γ 表示 P 点"靠近 C"的程度

如何计算？

/**
 * 计算点 P 相对于三角形 ABC 的重心坐标
 * @returns {[number, number, number]} [alpha, beta, gamma]
 */
function barycentricCoordinates(A, B, C, P) {
  // 计算三角形 ABC 的面积（使用叉积）
  const areaABC = Math.abs((B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y));

  // 计算子三角形的面积
  const areaPBC = Math.abs((B.x - P.x) * (C.y - P.y) - (C.x - P.x) * (B.y - P.y));
  const areaPCA = Math.abs((C.x - P.x) * (A.y - P.y) - (A.x - P.x) * (C.y - P.y));
  const areaPAB = Math.abs((A.x - P.x) * (B.y - P.y) - (B.x - P.x) * (A.y - P.y));

  // 重心坐标 = 子三角形面积 / 总面积
  const alpha = areaPBC / areaABC;
  const beta = areaPCA / areaABC;
  const gamma = areaPAB / areaABC;

  return [alpha, beta, gamma];
}

/**
 * 使用重心坐标判断点是否在三角形内
 */
function isPointInTriangleBarycentric(A, B, C, P) {
  const [alpha, beta, gamma] = barycentricCoordinates(A, B, C, P);

  // 如果三个重心坐标都在 [0, 1] 范围内，点在三角形内（含边界）
  return alpha >= 0 && beta >= 0 && gamma >= 0 &&
         Math.abs(alpha + beta + gamma - 1) < 1e-10;
}

为什么重心坐标很有用？

重心坐标不仅告诉你"在不在"，还能帮你做属性插值：

// 假设三角形的三个顶点有不同的颜色
const colorA = [1, 0, 0];  // 红色
const colorB = [0, 1, 0];  // 绿色
const colorC = [0, 0, 1];  // 蓝色

// P 点的颜色 = 重心坐标的加权平均
const [alpha, beta, gamma] = barycentricCoordinates(A, B, C, P);
const colorP = [
  alpha * colorA[0] + beta * colorB[0] + gamma * colorC[0],
  alpha * colorA[1] + beta * colorB[1] + gamma * colorC[1],
  alpha * colorA[2] + beta * colorB[2] + gamma * colorC[2],
];

这就是 GPU 在三角形内部插值颜色、纹理坐标、法线等属性的数学基础！

5.3 常见误区

误区	真相
"isPointInPath 是最快的方法"	对于简单场景是的，但对于大量检测或 WebGL 场景，三角剖分+重心坐标更高效
"点在边上算内部还是外部"	取决于具体需求。通常算内部，但某些算法可能将其视为边界情况
"重心坐标只能用于三角形"	是的，但任何多边形都可以先三角剖分，然后对每个三角形使用重心坐标
"射线法（ray casting）只能水平发射"	射线可以朝任意方向发射，水平只是为了计算方便

5.4 动手试一试

练习 5.1：实现一个射线法（Ray Casting）判断点是否在多边形内。不调用任何内置 API，只用基础的数学运算。

练习 5.2：创建一个彩色三角形，用重心坐标在 Canvas2D 上手动绘制渐变效果（不依赖 GPU 插值）。

练习 5.3：比较三种检测方法的性能：isPointInPath、三角剖分+叉积法、三角剖分+重心坐标法。在 1000 个随机点上测试，记录耗时。

6. 线条渲染：端帽、连接与斜接限制

6.1 生活类比：马克笔和胶带

想象你正在用马克笔在白板上画一条折线：

端帽（Line Cap）：马克笔的笔尖形状。是平头（butt）、圆头（round）还是方头（square）？
连接（Line Join）：两条线相交的地方。是直接尖角（miter）、圆角（round）还是斜切（bevel）？
斜接限制（Miter Limit）：如果两条线以很小的夹角相交，尖角会变得非常长。斜接限制就是规定"尖角最长不能超过多少倍线宽"

6.2 本质是什么

Canvas2D 提供了非常方便的线条样式控制：

// c:/Users/10603/Desktop/otherLearn2/akira-graphics/polyline-curve/canvas2d.html
function drawPolyline(context, points, {
  lineWidth = 1,      // 线宽
  lineJoin = 'miter', // 连接样式：miter | round | bevel
  lineCap = 'butt',   // 端帽样式：butt | round | square
  miterLimit = 10     // 斜接限制
} = {}) {
  context.lineWidth = lineWidth;
  context.lineJoin = lineJoin;
  context.lineCap = lineCap;
  context.miterLimit = miterLimit;
  context.beginPath();
  context.moveTo(...points[0]);
  for(let i = 1; i < points.length; i++) {
    context.lineTo(...points[i]);
  }
  context.stroke();
}

const canvas = document.querySelector('canvas');
const ctx = canvas.getContext('2d');

const points = [
  [100, 100],
  [100, 200],
  [200, 150],
  [300, 200],
  [300, 100],
];

// 粗红线：round 端帽，miter 连接，miterLimit = 1.5
ctx.strokeStyle = 'red';
drawPolyline(ctx, points, {
  lineWidth: 10,
  lineCap: 'round',
  lineJoin: 'miter',
  miterLimit: 1.5
});

// 细蓝线：默认样式（作为对比）
ctx.strokeStyle = 'blue';
drawPolyline(ctx, points);

lineCap 详解

值	效果	图示描述
`butt`	线端与最后一个点齐平	像被刀切过一样整齐
`round`	线端加一个半圆	像圆珠笔画的一样圆润
`square`	线端加一个半正方形	比 butt 多出一半线宽的长度

lineJoin 详解

值	效果	适用场景
`miter`	两条线的外边缘延长相交，形成尖角	需要锐利拐角时
`round`	拐角处填充一个圆弧	圆润风格
`bevel`	拐角处直接切平	折线较多时性能更好

miterLimit 详解

当两条线以很小的夹角相交时，miter 连接会产生非常长的尖角。miterLimit 控制这个尖角的最大长度：

如果 miterLength / lineWidth > miterLimit
  则自动降级为 bevel 连接

例如，miterLimit = 1.5 表示尖角长度不能超过 1.5 倍线宽。

6.3 常见误区

误区	真相
"lineCap 影响闭合路径"	`lineCap` 只影响开放路径的两端。闭合路径（closePath）没有"端帽"
"miterLimit 越大越好"	miterLimit 太大可能导致极端尖角；太小则频繁降级为 bevel
"round 连接总是最好看"	round 连接需要更多顶点，在 WebGL 中渲染成本更高
"线条样式只影响视觉效果"	线条的实际几何形状（如 round cap 的半圆）会影响点击检测区域

6.4 动手试一试

练习 6.1：用 Canvas2D 绘制一个"之"字形折线，分别用三种 lineJoin 样式（miter、round、bevel）和三种 lineCap 样式（butt、round、square）绘制 9 种组合，观察差异。

练习 6.2：创建一个两条线以 10 度夹角相交的折线，逐步增大 miterLimit，观察尖角何时出现、何时被截断。

7. 通过几何挤压实现粗线条渲染

7.1 生活类比：挤牙膏

想象你要画一条粗线，就像挤牙膏一样。你不是在画"一条线"，而是在画一个"有宽度的形状"。

具体来说，对于一条折线：

找到每个线段的方向
计算垂直于线段方向的"法线"
沿着法线方向，向两边各偏移半个线宽
这样就得到了一个"条带"形状
把这个条带分解成三角形，交给 GPU 渲染

7.2 本质是什么

Canvas2D 的 lineWidth 是浏览器帮你做的"挤压"。但在 WebGL 中，没有内置的"画粗线"功能——gl.LINE_STRIP 只能画 1 像素宽的线（而且线宽支持还不稳定）。

所以，我们需要手动将折线挤压成三角形几何体。

7.3 代码示例

我们来看看 akira-graphics 中的实现：

// c:/Users/10603/Desktop/otherLearn2/akira-graphics/polyline-curve/webgl-lines-extrude.html
import {Renderer, Program, Geometry, Transform, Mesh, Vec2} from '../common/lib/ogl/index.mjs';

// 定义折线的顶点
const points = [
  new Vec2(100, 100),
  new Vec2(100, 200),
  new Vec2(200, 150),
  new Vec2(300, 200),
  new Vec2(300, 100),
];

/**
 * 将折线挤压成三角形几何体
 * @param {WebGLRenderingContext} gl - WebGL 上下文
 * @param {Array<Vec2>} points - 折线顶点
 * @param {number} thickness - 线宽
 * @returns {Geometry} OGL Geometry 对象
 */
function extrudePolyline(gl, points, {thickness = 10} = {}) {
  const halfThick = 0.5 * thickness;  // 半边宽
  const innerSide = [];   // 内侧顶点（折线的一侧）
  const outerSide = [];   // 外侧顶点（折线的另一侧）

  // 遍历中间顶点（跳过第一个和最后一个，单独处理）
  for(let i = 1; i < points.length - 1; i++) {
    // v1: 从前一个点指向当前点的方向向量（归一化）
    const v1 = (new Vec2()).sub(points[i], points[i - 1]).normalize();
    // v2: 从当前点指向下一个点的方向向量（归一化）
    const v2 = (new Vec2()).sub(points[i], points[i + 1]).normalize();

    // v: 两个方向向量的和，再归一化 → 得到"角平分线"方向
    const v = (new Vec2()).add(v1, v2).normalize();

    // norm: v1 的法线方向（垂直于线段）
    const norm = new Vec2(-v1.y, v1.x);

    // cos: v 和 norm 的夹角余弦
    // 几何意义：角平分线方向在法线方向上的投影
    const cos = norm.dot(v);

    // len: 挤压距离
    // 原理：halfThick / cos 确保在拐角处也能保持正确的线宽
    const len = halfThick / cos;

    // 处理起始点（只在 i === 1 时执行一次）
    if(i === 1) {
      const v0 = new Vec2(...norm).scale(halfThick);
      outerSide.push((new Vec2()).add(points[0], v0));  // 起点外侧
      innerSide.push((new Vec2()).sub(points[0], v0));  // 起点内侧
    }

    // 对当前顶点进行挤压
    v.scale(len);
    outerSide.push((new Vec2()).add(points[i], v));   // 当前顶点外侧
    innerSide.push((new Vec2()).sub(points[i], v));   // 当前顶点内侧

    // 处理结束点（只在 i === points.length - 2 时执行一次）
    if(i === points.length - 2) {
      const norm2 = new Vec2(v2.y, -v2.x);  // v2 的法线方向
      const v0 = new Vec2(...norm2).scale(halfThick);
      outerSide.push((new Vec2()).add(points[points.length - 1], v0));
      innerSide.push((new Vec2()).sub(points[points.length - 1], v0));
    }
  }

  // 构建三角形带的顶点和索引
  const count = innerSide.length * 4 - 4;
  const position = new Float32Array(count * 2);
  const index = new Uint16Array(6 * count / 4);

  // 每个线段生成两个三角形（6 个索引）
  for(let i = 0; i < innerSide.length - 1; i++) {
    const a = innerSide[i];      // 当前内侧
    const b = outerSide[i];      // 当前外侧
    const c = innerSide[i + 1];  // 下一个内侧
    const d = outerSide[i + 1];  // 下一个外侧

    const offset = i * 4;
    // 两个三角形：(a, b, c) 和 (c, b, d)
    index.set([offset, offset + 1, offset + 2, offset + 2, offset + 1, offset + 3], i * 6);
    position.set([...a, ...b, ...c, ...d], i * 8);
  }

  return new Geometry(gl, {
    position: {size: 2, data: position},
    index: {data: index},
  });
}

// 创建挤压后的几何体
const geometry = extrudePolyline(gl, points);

// 渲染
const scene = new Transform();
const polyline = new Mesh(gl, {geometry, program});
polyline.setParent(scene);
renderer.render({scene});

7.4 数学原理图解

让我们详细推导挤压算法的核心数学：

步骤 1：线段方向向量

对于线段从 P(i-1) 到 P(i)：

v1 = P(i) - P(i-1)
v1_normalized = v1 / |v1|

步骤 2：法线向量

法线就是垂直于线段方向的向量：

如果 v1 = (x, y)
那么 norm = (-y, x)  // 逆时针旋转 90 度

步骤 3：角平分线

在拐角处，两个线段的法线方向不同。我们需要找到一个"中间方向"：

v = normalize(v1 + v2)

这个 v 就是角平分线方向。

步骤 4：挤压长度

关键点：角平分线方向 v 和法线方向 norm 之间有一个夹角。

cos = norm · v
len = halfThick / cos

为什么要除以 cos？因为角平分线方向比法线方向"更斜"，需要更长的偏移距离才能保持相同的线宽。

7.5 常见误区

误区	真相
"WebGL 的 LINE_STRIP 可以画粗线"	`gl.LINE_WIDTH` 在大多数 WebGL 实现中只支持 1.0，而且行为不一致
"挤压就是简单地向两边偏移"	拐角处需要特殊处理（角平分线），否则会出现缺口或重叠
"挤压后的线条不需要端帽处理"	开放路径的端帽（round/square）需要额外生成几何体
"所有线段都可以独立挤压"	共享顶点处需要连续处理，否则会出现裂缝

7.6 动手试一试

练习 7.1：修改上面的挤压函数，为开放路径添加 round 端帽（在两端各加一个半圆）。

练习 7.2：尝试用 bevel 连接样式替代默认的 miter 连接。提示：在拐角处直接连接两个线段的端点，不延长相交。

练习 7.3：画一个闭合的折线（如五角星轮廓），观察挤压算法在闭合处的行为。需要做什么特殊处理吗？

8. 将折线转换为三角形带

8.1 生活类比：拉链

想象一条拉链。拉链的两边是平行的，中间的"齿"把它们连接在一起。

折线转三角形带就像做一条拉链：

折线的每个顶点变成拉链上的两个点（一边一个）
相邻顶点之间的四个点组成一个"链节"
每个链节由两个三角形组成

8.2 本质是什么

上一节的挤压算法本质上就是在做这件事。但让我们更系统地理解"三角形带"这个概念。

什么是三角形带（Triangle Strip）？

三角形带是一种高效存储连续三角形序列的方式：

普通三角形序列：
  三角形 1: v0, v1, v2
  三角形 2: v3, v4, v5
  三角形 3: v6, v7, v8
  ...
  需要 3n 个顶点

三角形带：
  v0, v1, v2, v3, v4, v5, ...
  三角形 1: v0, v1, v2
  三角形 2: v2, v1, v3  （注意顶点顺序！）
  三角形 3: v2, v3, v4
  ...
  只需要 n + 2 个顶点

三角形带的优势：顶点复用。每个新顶点可以和前两个顶点组成一个新三角形。

折线挤压后的三角形带结构

对于一条有 N 个顶点的折线：

折线顶点：P0, P1, P2, ..., P(N-1)

挤压后（每点生成内外两个顶点）：
  内侧：I0, I1, I2, ..., I(N-1)
  外侧：O0, O1, O2, ..., O(N-1)

三角形带顶点顺序：
  I0, O0, I1, O1, I2, O2, ...

三角形 1: I0, O0, I1
三角形 2: I1, O0, O1  （注意 winding order！）
三角形 3: I1, O1, I2
三角形 4: I2, O1, O2
...

8.3 代码示例

/**
 * 将折线转换为三角形带（简化版，不考虑拐角处理）
 * @param {Array<[number, number]>} points - 折线顶点
 * @param {number} thickness - 线宽
 * @returns {{positions: Float32Array, indices: Uint16Array}}
 */
function polylineToTriangleStrip(points, thickness) {
  const halfThick = thickness / 2;
  const positions = [];
  const indices = [];

  for (let i = 0; i < points.length; i++) {
    const [x, y] = points[i];

    // 计算当前线段的方向
    let dx, dy;
    if (i < points.length - 1) {
      dx = points[i + 1][0] - x;
      dy = points[i + 1][1] - y;
    } else {
      dx = x - points[i - 1][0];
      dy = y - points[i - 1][1];
    }

    // 归一化
    const len = Math.sqrt(dx * dx + dy * dy);
    dx /= len;
    dy /= len;

    // 法线（垂直方向）
    const nx = -dy * halfThick;
    const ny = dx * halfThick;

    // 内侧和外侧顶点
    positions.push(x - nx, y - ny);  // 内侧
    positions.push(x + nx, y + ny);  // 外侧
  }

  // 生成索引（三角形带）
  for (let i = 0; i < points.length - 1; i++) {
    const base = i * 2;
    // 两个三角形组成一个线段
    indices.push(base, base + 1, base + 2);
    indices.push(base + 2, base + 1, base + 3);
  }

  return {
    positions: new Float32Array(positions),
    indices: new Uint16Array(indices),
  };
}

// 使用示例
const linePoints = [
  [100, 100],
  [150, 200],
  [250, 150],
  [350, 250],
];

const {positions, indices} = polylineToTriangleStrip(linePoints, 20);
console.log(`顶点数: ${positions.length / 2}, 索引数: ${indices.length}`);
// 输出：顶点数: 8, 索引数: 12（4 个线段 × 2 个三角形 × 3 个索引）

8.4 与 WebGL 渲染结合

// c:/Users/10603/Desktop/otherLearn2/akira-graphics/polyline-curve/webgl-lines.html
import {Renderer, Program, Geometry, Transform, Mesh} from '../common/lib/ogl/index.mjs';

const vertex = `
  attribute vec2 position;
  void main() {
    gl_PointSize = 10.0;
    float scale = 1.0 / 256.0;
    mat3 projectionMatrix = mat3(
      scale, 0, 0,
      0, -scale, 0,
      -1, 1, 1
    );
    vec3 pos = projectionMatrix * vec3(position, 1);
    gl_Position = vec4(pos.xy, 0, 1);
  }
`;

const fragment = `
  precision highp float;
  void main() {
    gl_FragColor = vec4(1, 0, 0, 1);
  }
`;

const canvas = document.querySelector('canvas');
const renderer = new Renderer({canvas, width: 512, height: 512});
const gl = renderer.gl;
gl.clearColor(1, 1, 1, 1);

const program = new Program(gl, {vertex, fragment});

// 使用 LINE_STRIP 模式直接绘制（1 像素宽）
const geometry = new Geometry(gl, {
  position: {size: 2, data: new Float32Array([
    100, 100,
    100, 200,
    200, 150,
    300, 200,
    300, 100,
  ])},
});

const scene = new Transform();
const polyline = new Mesh(gl, {geometry, program, mode: gl.LINE_STRIP});
polyline.setParent(scene);

renderer.render({scene});

注意：上面的代码使用 gl.LINE_STRIP 模式，只能画 1 像素宽的线。要实现粗线，必须使用前面介绍的挤压算法生成三角形几何体。

8.5 常见误区

误区	真相
"三角形带一定比普通三角形序列快"	在现代 GPU 上，索引三角形列表（Indexed Triangle List）通常和三角形带一样快，甚至更快
"折线转三角形带只需要复制顶点"	拐角处需要特殊处理（角平分线、斜切或圆角），否则会出现视觉瑕疵
"所有折线都可以完美转换为三角形带"	自相交折线需要特殊处理；极短的线段可能导致数值问题
"三角形带的顶点顺序不重要"	顶点顺序决定了三角形的朝向（winding order），影响背面剔除

8.6 动手试一试

练习 8.1：实现一个函数，将折线转换为真正的 gl.TRIANGLE_STRIP 模式可用的顶点序列（不使用索引缓冲区）。比较索引方式和条带方式的顶点数量差异。

练习 8.2：创建一个动画，让一条折线像"蛇"一样移动。思考：是每帧重新挤压整条折线更高效，还是只更新变化的顶点更高效？

练习 8.3：尝试用 gl.TRIANGLE_STRIP 模式渲染一个粗线条的圆。需要多少个顶点？

9. 常见问题 Q&A

Q1：为什么 GPU 不直接支持画四边形或任意多边形？

A：三个原因：

平面性：三个点一定共面，四个点不一定
插值简单性：三角形内部的属性插值是线性的，可以用重心坐标
硬件简化：只支持一种图元，硬件设计更简单、更快、更可靠

类比：乐高只生产标准砖块，你可以用标准砖块搭出任何形状。GPU 只"生产"三角形，你可以用三角形拼出任何形状。

Q2：nonzero 和 evenodd 到底该用哪个？

A：看场景：

nonzero：适合字体渲染、大多数图形编辑软件。能正确处理"重叠区域"（如自相交多边形）
evenodd：适合简单多边形、SVG 默认行为。计算稍微简单一点

经验法则：如果你不确定，用 nonzero。它更"宽容"，在大多数场景下表现正确。

Q3：Earcut 算法的时间复杂度是多少？

A：Earcut 是 O(n^2) 的贪心算法，其中 n 是多边形顶点数。

对于每个"耳朵"，需要检查它是否包含其他顶点（O(n)），最多有 n 个耳朵，所以总复杂度是 O(n^2)。

对比：最优三角剖分算法（动态规划）是 O(n^3)，Delaunay 三角剖分是 O(n log n)。Earcut 追求的是实现简单和鲁棒性。

Q4：为什么 WebGL 的 `gl.LINE_WIDTH` 不好用？

A：WebGL 规范允许实现自由选择支持的线宽范围。大多数浏览器只支持线宽为 1.0。

即使支持更大的线宽，线条渲染的质量也不如手动挤压的三角形：

没有端帽控制
没有连接样式控制
线条端点可能不对齐像素
抗锯齿效果不一致

最佳实践：在 WebGL 中画粗线，始终使用三角形挤压方案。

Q5：重心坐标为什么叫"重心"坐标？

A：如果 α = β = γ = 1/3，那么 P 点就是三角形的几何重心（质心）。

更一般地，如果 A、B、C 处有质量 α、β、γ，那么系统的质心就在 P 点。

趣味知识：重心坐标是德国数学家奥古斯特·费迪南德·莫比乌斯（August Ferdinand Mobius，就是发现莫比乌斯环的那位）在 1827 年提出的。

Q6：三角剖分后的三角形数量可以优化吗？

A：对于简单多边形，任何三角剖分都恰好产生 (n-2) 个三角形，其中 n 是顶点数。这是固定的，无法减少。

但可以优化的是：

三角形形状：避免过于细长的三角形（影响数值稳定性）
顶点顺序：优化缓存命中率
索引复用：使用索引缓冲区减少顶点重复

Q7：如何判断一个多边形是凸的还是凹的？

A：检查所有连续三个顶点形成的转角方向：

function isConvex(polygon) {
  const n = polygon.length;
  let sign = 0;

  for (let i = 0; i < n; i++) {
    const [x1, y1] = polygon[i];
    const [x2, y2] = polygon[(i + 1) % n];
    const [x3, y3] = polygon[(i + 2) % n];

    // 计算叉积
    const cross = (x2 - x1) * (y3 - y2) - (y2 - y1) * (x3 - x2);

    if (cross !== 0) {
      const currentSign = Math.sign(cross);
      if (sign === 0) {
        sign = currentSign;
      } else if (sign !== currentSign) {
        return false;  // 发现方向变化，是凹多边形
      }
    }
  }

  return true;  // 所有转角方向一致，是凸多边形
}

Q8：miterLimit 的数学含义是什么？

A：miterLimit 控制的是 miter 连接产生的尖角长度与线宽的比值。

对于两条以角度 θ 相交的线段：

miterLength / lineWidth = 1 / sin(θ/2)

当 θ 很小时（锐角），sin(θ/2) 也很小，所以尖角长度会非常大。

miterLimit 就是限制这个比值的最大值。如果计算出的比值超过 miterLimit，就自动降级为 bevel 连接。

例如，miterLimit = 10 表示尖角长度最多是线宽的 10 倍。

Q9：挤压算法中的 `len = halfThick / cos` 是怎么来的？

A：让我们推导一下：

在拐角处，角平分线方向 v 和法线方向 norm 有一个夹角 φ，其中 cos(φ) = norm · v。

我们希望沿角平分线方向移动后，垂直于线段方向的距离恰好是 halfThick。

如果沿 v 方向移动距离 len，那么垂直于线段方向的分量是 len * cos(φ)。

令 len * cos(φ) = halfThick，得到 len = halfThick / cos(φ)。

注意：当拐角非常尖锐时，cos(φ) 接近 0，len 会变得非常大。这就是为什么需要 miterLimit 来限制。

Q10：这一章的知识在实际工作中有什么用？

A：非常实用！以下是一些真实应用场景：

技术	应用场景
多边形填充规则	SVG/Canvas 渲染、字体光栅化、矢量图形编辑器
三角剖分	地图渲染、3D 建模、物理引擎、有限元分析
点在多边形检测	地图点击查询、游戏碰撞检测、GIS 空间分析
线条挤压	地图路线渲染、数据可视化、CAD 软件、游戏描边
重心坐标	纹理映射、光照插值、变形动画、粒子系统

本章小结

恭喜你读完了这一章！让我们回顾一下核心要点：

多边形填充规则：nonzero 看"环绕方向"，evenodd 看"穿过次数"。自相交多边形下两者结果可能不同。
环绕数：描述一个点被多边形边界"绕了多少圈"。nonzero 规则就是判断环绕数是否为 0。
三角剖分：GPU 只画三角形，所以任意多边形必须先剖分成三角形。一个 n 边形可以剖分成 (n-2) 个三角形。
Earcut 算法：通过反复"摘耳朵"将多边形三角剖分。简单、鲁棒，适合大多数场景。
点在多边形检测：可以用 Canvas2D 的 isPointInPath、三角剖分+叉积法、或重心坐标法。
线条样式：lineCap 控制端点形状，lineJoin 控制拐角样式，miterLimit 限制尖角长度。
线条挤压：WebGL 不支持粗线，需要手动将折线挤压成三角形几何体。
三角形带：高效的连续三角形表示，折线挤压后可以表示为三角形带。

给 junior 程序员的一句话：几何处理是图形学的基石。不要觉得这些算法"太底层"——当你遇到渲染 bug 时，往往是这些基础概念理解不到位。花点时间把每个算法的原理吃透，未来会省掉无数调试时间。

下一章，我们将进入更有趣的领域——变换与坐标系统。准备好探索矩阵的魔法了吗？