第5章：2D 图形绘制算法
5.1 直线绘制算法
5.1.1 问题定义
在光栅显示器上，图像由离散的像素点组成。绘制直线的核心问题是：如何选择最佳的像素点来近似表示一条数学上连续的直线？
直线光栅化问题
数学直线（连续）： 光栅化后（离散）：
│ │
│ ╱ │ □
│ ╱ │ □
│ ╱ │ □
│ ╱ │ □ □
│╱ │□
────┼──── ────┼────
│ │
问题：如何选择像素使直线看起来"最直"？5.1.2 DDA 算法（Digital Differential Analyzer）
DDA 是最直观的直线绘制算法，基于直线的参数方程：
DDA 算法原理
直线方程：y = kx + b，其中 k = Δy/Δx
如果 |k| ≤ 1（偏水平）：
- x 每次增加 1
- y 每次增加 k
如果 |k| > 1（偏垂直）：
- y 每次增加 1
- x 每次增加 1/k
图示（k = 0.5 的情况）：
步骤：x=0, y=0
x=1, y=0.5 → 取整为 (1, 1) 或 (1, 0)
x=2, y=1.0 → (2, 1)
x=3, y=1.5 → (3, 2) 或 (3, 1)
...
y
3 │ □
2 │ □ □
1 │ □ □
0 │ □
└───────────────► x
0 1 2 3 45.1.3 DDA 代码实现
javascript
/**
* DDA 直线绘制算法
* @param x1, y1 起点
* @param x2, y2 终点
* @param setPixel 绘制像素的回调函数
*/
function drawLineDDA(x1, y1, x2, y2, setPixel) {
const dx = x2 - x1;
const dy = y2 - y1;
// 计算步数（取 dx 和 dy 的较大者）
const steps = Math.max(Math.abs(dx), Math.abs(dy));
if (steps === 0) {
setPixel(Math.round(x1), Math.round(y1));
return;
}
// 计算每步的增量
const xIncrement = dx / steps;
const yIncrement = dy / steps;
let x = x1;
let y = y1;
for (let i = 0; i <= steps; i++) {
setPixel(Math.round(x), Math.round(y));
x += xIncrement;
y += yIncrement;
}
}
// 使用示例
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
function setPixel(x, y) {
ctx.fillRect(x, y, 1, 1);
}
drawLineDDA(10, 10, 100, 60, setPixel);5.1.4 Bresenham 直线算法
Bresenham 算法是更高效的直线绘制算法，只使用整数运算：
Bresenham 算法原理
核心思想：
在每个 x 位置，判断下一个像素应该选择：
- 当前 y（保持不变）
- y + 1（上移）
判断依据是比较实际直线与两个候选像素的距离。
决策变量 d：
d = 2Δy - Δx（初始值）
如果 d < 0：
- 选择 (x+1, y)
- d = d + 2Δy
如果 d ≥ 0：
- 选择 (x+1, y+1)
- d = d + 2Δy - 2Δx
图示：
对于点 (x, y)，下一个点是 (x+1, y) 还是 (x+1, y+1)？
│ ╱ 实际直线
y+1 │ ○╱ ← 候选点 B
│ ╱│
│ ╱ │ d1
│ ╱──│
│ ╱ │ d2
y │○────┴── ← 候选点 A
│
└─────────────
x x+1
如果 d1 < d2，选择 A；否则选择 B5.1.5 Bresenham 代码实现
javascript
/**
* Bresenham 直线算法
* @param x0, y0 起点
* @param x1, y1 终点
* @param setPixel 绘制像素的回调函数
*/
function drawLineBresenham(x0, y0, x1, y1, setPixel) {
// 计算差值
let dx = Math.abs(x1 - x0);
let dy = Math.abs(y1 - y0);
// 确定步进方向
const sx = x0 < x1 ? 1 : -1;
const sy = y0 < y1 ? 1 : -1;
// 判断斜率是否大于1
const steep = dy > dx;
if (steep) {
// 如果斜率>1，交换 dx 和 dy
[dx, dy] = [dy, dx];
}
// 初始决策变量
let d = 2 * dy - dx;
let x = x0;
let y = y0;
for (let i = 0; i <= dx; i++) {
setPixel(x, y);
if (d > 0) {
if (steep) {
x += sx;
} else {
y += sy;
}
d -= 2 * dx;
}
if (steep) {
y += sy;
} else {
x += sx;
}
d += 2 * dy;
}
}
// 更简洁的通用版本
function drawLine(x0, y0, x1, y1, setPixel) {
const dx = Math.abs(x1 - x0);
const dy = Math.abs(y1 - y0);
const sx = x0 < x1 ? 1 : -1;
const sy = y0 < y1 ? 1 : -1;
let err = dx - dy;
while (true) {
setPixel(x0, y0);
if (x0 === x1 && y0 === y1) break;
const e2 = 2 * err;
if (e2 > -dy) {
err -= dy;
x0 += sx;
}
if (e2 < dx) {
err += dx;
y0 += sy;
}
}
}5.2 圆绘制算法
5.2.1 圆的特性
圆的对称性
圆心在原点的圆具有 8 重对称性：
如果 (x, y) 在圆上，则以下 7 个点也在圆上：
(-x, y), (x, -y), (-x, -y)
(y, x), (-y, x), (y, -x), (-y, -x)
y
│
────┼────
╱ │ ╲
╱ │ ╲
│ 2 │ 1 │
│ (-x,y)│(x,y)│
─┼──────┼──────┼─ x
│ 3 │ 8 │
│(-x,-y)│(x,-y)│
╲ │ ╱
╲ │ ╱
────┼────
│
利用对称性，只需要计算 1/8 的圆弧！5.2.2 中点圆算法
中点圆算法（Midpoint Circle Algorithm）
基于圆的隐式方程：F(x, y) = x² + y² - r² = 0
F(x, y) < 0：点在圆内
F(x, y) = 0：点在圆上
F(x, y) > 0：点在圆外
决策过程：
从 (0, r) 开始，向右下方遍历（在第一象限的第一段弧）
对于当前点 (x, y)，下一个点是：
- E: (x+1, y)
- SE: (x+1, y-1)
判断中点 M = (x+1, y-0.5) 在圆内还是圆外
(x, y)
○
│╲
│ ╲
M ────● ╲
│ ○ (x+1, y-1)
│
○ (x+1, y)
如果 F(M) < 0，M 在圆内，选择 E
如果 F(M) ≥ 0，M 在圆外或圆上，选择 SE5.2.3 中点圆算法实现
javascript
/**
* 中点圆算法
* @param cx, cy 圆心
* @param r 半径
* @param setPixel 绘制像素的回调
*/
function drawCircleMidpoint(cx, cy, r, setPixel) {
// 利用 8 重对称性绘制 8 个点
function drawCirclePoints(x, y) {
setPixel(cx + x, cy + y);
setPixel(cx - x, cy + y);
setPixel(cx + x, cy - y);
setPixel(cx - x, cy - y);
setPixel(cx + y, cy + x);
setPixel(cx - y, cy + x);
setPixel(cx + y, cy - x);
setPixel(cx - y, cy - x);
}
let x = 0;
let y = r;
// 初始决策变量：d = F(1, r-0.5) = 1 + (r-0.5)² - r² = 1.25 - r
// 为避免浮点运算，使用 4d 代替 d
let d = 1 - r;
drawCirclePoints(x, y);
while (x < y) {
if (d < 0) {
// 选择 E 点
d += 2 * x + 3;
} else {
// 选择 SE 点
d += 2 * (x - y) + 5;
y--;
}
x++;
drawCirclePoints(x, y);
}
}
// Bresenham 圆算法（另一种实现）
function drawCircleBresenham(cx, cy, r, setPixel) {
let x = 0;
let y = r;
let d = 3 - 2 * r;
function drawCirclePoints(x, y) {
setPixel(cx + x, cy + y);
setPixel(cx - x, cy + y);
setPixel(cx + x, cy - y);
setPixel(cx - x, cy - y);
setPixel(cx + y, cy + x);
setPixel(cx - y, cy + x);
setPixel(cx + y, cy - x);
setPixel(cx - y, cy - x);
}
drawCirclePoints(x, y);
while (y >= x) {
x++;
if (d > 0) {
y--;
d = d + 4 * (x - y) + 10;
} else {
d = d + 4 * x + 6;
}
drawCirclePoints(x, y);
}
}5.3 椭圆绘制
5.3.1 椭圆的特性
椭圆方程
标准椭圆方程：x²/a² + y²/b² = 1
其中 a 是水平半轴，b 是垂直半轴
椭圆的对称性：
椭圆有 4 重对称性（相比圆的 8 重）
如果 (x, y) 在椭圆上，则：
(-x, y), (x, -y), (-x, -y) 也在椭圆上
椭圆分区：
由于椭圆不是圆，需要将其分为两个区域：
区域 1：斜率 |dy/dx| < 1（靠近水平轴）
区域 2：斜率 |dy/dx| > 1（靠近垂直轴）
分界点：斜率 = -1 的位置
y
│ 区域2
│ ╱────────╲
│ ╱ ╲
│╱ 区域1 ╲
○──────────────○─► x
│╲ ╱
│ ╲ ╱
│ ╲────────╱
│5.3.2 中点椭圆算法
javascript
/**
* 中点椭圆算法
* @param cx, cy 中心点
* @param a 水平半轴
* @param b 垂直半轴
* @param setPixel 绘制像素的回调
*/
function drawEllipseMidpoint(cx, cy, a, b, setPixel) {
// 绘制 4 个对称点
function drawEllipsePoints(x, y) {
setPixel(cx + x, cy + y);
setPixel(cx - x, cy + y);
setPixel(cx + x, cy - y);
setPixel(cx - x, cy - y);
}
const a2 = a * a;
const b2 = b * b;
const twoA2 = 2 * a2;
const twoB2 = 2 * b2;
let x = 0;
let y = b;
// 区域 1
let px = 0;
let py = twoA2 * y;
// 区域 1 的初始决策变量
let d1 = b2 - (a2 * b) + (0.25 * a2);
drawEllipsePoints(x, y);
// 区域 1：当 b²x < a²y（斜率 > -1）
while (px < py) {
x++;
px += twoB2;
if (d1 < 0) {
d1 += b2 + px;
} else {
y--;
py -= twoA2;
d1 += b2 + px - py;
}
drawEllipsePoints(x, y);
}
// 区域 2 的初始决策变量
let d2 = b2 * (x + 0.5) * (x + 0.5) +
a2 * (y - 1) * (y - 1) -
a2 * b2;
// 区域 2：当 b²x >= a²y（斜率 <= -1）
while (y > 0) {
y--;
py -= twoA2;
if (d2 > 0) {
d2 += a2 - py;
} else {
x++;
px += twoB2;
d2 += a2 - py + px;
}
drawEllipsePoints(x, y);
}
}5.4 多边形填充
5.4.1 填充算法概述
多边形填充的主要算法
1. 种子填充（Flood Fill）
- 从内部一点开始，向外扩散
- 简单但效率低
2. 扫描线填充（Scanline Fill）
- 按行扫描，找交点，填充区间
- 效率高，适合凸/凹多边形
3. 边界填充（Boundary Fill）
- 从内部开始，遇到边界停止
- 适合简单形状5.4.2 扫描线填充算法
扫描线填充原理
对于每条水平扫描线：
1. 找到与多边形边的所有交点
2. 将交点按 x 坐标排序
3. 两两配对，填充之间的像素
示例：
多边形：
╱╲
╱ ╲
╱ ╲
╱ ╲
╱────────╲
╱ ╲
╱────────────╲
扫描线 y=3：
│
╱╲ │
╱ ╲ ───┼─── y=3
╱────╲ ● │ ●
╱ ╲ │
│
交点 x1 交点 x2
填充 [x1, x2] 之间的像素5.4.3 扫描线填充实现
javascript
/**
* 扫描线多边形填充
* @param vertices 多边形顶点数组 [{x, y}, ...]
* @param setPixel 绘制像素的回调
*/
function fillPolygonScanline(vertices, setPixel) {
if (vertices.length < 3) return;
// 找到 y 的范围
let minY = Infinity;
let maxY = -Infinity;
for (const v of vertices) {
minY = Math.min(minY, v.y);
maxY = Math.max(maxY, v.y);
}
minY = Math.ceil(minY);
maxY = Math.floor(maxY);
// 构建边表
const edges = [];
const n = vertices.length;
for (let i = 0; i < n; i++) {
const v1 = vertices[i];
const v2 = vertices[(i + 1) % n];
// 跳过水平边
if (v1.y === v2.y) continue;
// 确保 v1.y < v2.y
const [p1, p2] = v1.y < v2.y ? [v1, v2] : [v2, v1];
edges.push({
yMin: p1.y,
yMax: p2.y,
x: p1.x,
slope: (p2.x - p1.x) / (p2.y - p1.y)
});
}
// 按 yMin 排序边
edges.sort((a, b) => a.yMin - b.yMin);
// 活动边列表
let activeEdges = [];
let edgeIndex = 0;
// 逐行扫描
for (let y = minY; y <= maxY; y++) {
// 添加新的活动边
while (edgeIndex < edges.length && edges[edgeIndex].yMin <= y) {
activeEdges.push({ ...edges[edgeIndex] });
edgeIndex++;
}
// 移除过期的边
activeEdges = activeEdges.filter(e => e.yMax > y);
// 按 x 排序活动边
activeEdges.sort((a, b) => a.x - b.x);
// 配对填充
for (let i = 0; i < activeEdges.length - 1; i += 2) {
const x1 = Math.ceil(activeEdges[i].x);
const x2 = Math.floor(activeEdges[i + 1].x);
for (let x = x1; x <= x2; x++) {
setPixel(x, y);
}
}
// 更新边的 x 值
for (const edge of activeEdges) {
edge.x += edge.slope;
}
}
}
// 使用示例
const triangle = [
{ x: 100, y: 50 },
{ x: 50, y: 150 },
{ x: 150, y: 150 }
];
fillPolygonScanline(triangle, setPixel);5.4.4 种子填充算法
javascript
/**
* 递归种子填充（Flood Fill）
* 注意：大区域可能导致栈溢出
*/
function floodFillRecursive(x, y, targetColor, fillColor, getPixel, setPixel) {
if (getPixel(x, y) !== targetColor) return;
setPixel(x, y, fillColor);
floodFillRecursive(x + 1, y, targetColor, fillColor, getPixel, setPixel);
floodFillRecursive(x - 1, y, targetColor, fillColor, getPixel, setPixel);
floodFillRecursive(x, y + 1, targetColor, fillColor, getPixel, setPixel);
floodFillRecursive(x, y - 1, targetColor, fillColor, getPixel, setPixel);
}
/**
* 非递归种子填充（使用队列）
*/
function floodFillIterative(startX, startY, targetColor, fillColor, getPixel, setPixel, width, height) {
if (getPixel(startX, startY) !== targetColor) return;
const queue = [[startX, startY]];
const visited = new Set();
while (queue.length > 0) {
const [x, y] = queue.shift();
const key = `${x},${y}`;
if (visited.has(key)) continue;
if (x < 0 || x >= width || y < 0 || y >= height) continue;
if (getPixel(x, y) !== targetColor) continue;
visited.add(key);
setPixel(x, y, fillColor);
queue.push([x + 1, y]);
queue.push([x - 1, y]);
queue.push([x, y + 1]);
queue.push([x, y - 1]);
}
}
/**
* 扫描线种子填充（更高效）
*/
function floodFillScanline(startX, startY, targetColor, fillColor, getPixel, setPixel, width, height) {
if (getPixel(startX, startY) !== targetColor) return;
const stack = [[startX, startY]];
while (stack.length > 0) {
let [x, y] = stack.pop();
// 向左找到边界
while (x > 0 && getPixel(x - 1, y) === targetColor) {
x--;
}
let spanAbove = false;
let spanBelow = false;
// 向右扫描填充
while (x < width && getPixel(x, y) === targetColor) {
setPixel(x, y, fillColor);
// 检查上方
if (!spanAbove && y > 0 && getPixel(x, y - 1) === targetColor) {
stack.push([x, y - 1]);
spanAbove = true;
} else if (spanAbove && y > 0 && getPixel(x, y - 1) !== targetColor) {
spanAbove = false;
}
// 检查下方
if (!spanBelow && y < height - 1 && getPixel(x, y + 1) === targetColor) {
stack.push([x, y + 1]);
spanBelow = true;
} else if (spanBelow && y < height - 1 && getPixel(x, y + 1) !== targetColor) {
spanBelow = false;
}
x++;
}
}
}5.5 抗锯齿
5.5.1 锯齿问题
锯齿（Aliasing）
由于光栅化将连续图形离散化，产生了阶梯状的"锯齿"。
理想直线： 光栅化后：
╱ □
╱ □
╱ □ □
╱ □ □
╱ □ □
锯齿在斜线、曲线边缘特别明显。
抗锯齿（Anti-aliasing）：
通过颜色混合，使边缘看起来更平滑。5.5.2 抗锯齿直线（Wu's Algorithm）
吴小林抗锯齿算法
原理：根据像素与理想直线的距离，设置不同的透明度。
│
│ ■ 100%（直线穿过）
│ ▪ 60%（部分覆盖）
│ · 20%（轻微覆盖）
│
────────┼────────
│
对于非整数坐标 (x, y.3)：
- (x, floor(y)) 的强度 = 1 - 0.3 = 0.7
- (x, ceil(y)) 的强度 = 0.3
y
▲
y+1 │ ▪ 30%
│ ╱
│ ╱
y │■ 70%
└───────► x5.5.3 抗锯齿直线实现
javascript
/**
* 吴小林抗锯齿直线算法
* @param x0, y0 起点
* @param x1, y1 终点
* @param setPixelAlpha 设置像素及透明度的回调 (x, y, alpha)
*/
function drawLineAntialiased(x0, y0, x1, y1, setPixelAlpha) {
// 判断是否更陡峭
const steep = Math.abs(y1 - y0) > Math.abs(x1 - x0);
if (steep) {
[x0, y0] = [y0, x0];
[x1, y1] = [y1, x1];
}
if (x0 > x1) {
[x0, x1] = [x1, x0];
[y0, y1] = [y1, y0];
}
const dx = x1 - x0;
const dy = y1 - y0;
const gradient = dx === 0 ? 1 : dy / dx;
// 绘制像素（考虑陡峭情况）
function plot(x, y, alpha) {
if (steep) {
setPixelAlpha(Math.floor(y), Math.floor(x), alpha);
} else {
setPixelAlpha(Math.floor(x), Math.floor(y), alpha);
}
}
// 辅助函数
function fpart(x) {
return x - Math.floor(x);
}
function rfpart(x) {
return 1 - fpart(x);
}
// 处理起点
let xend = Math.round(x0);
let yend = y0 + gradient * (xend - x0);
let xgap = rfpart(x0 + 0.5);
const xpxl1 = xend;
const ypxl1 = Math.floor(yend);
plot(xpxl1, ypxl1, rfpart(yend) * xgap);
plot(xpxl1, ypxl1 + 1, fpart(yend) * xgap);
let intery = yend + gradient;
// 处理终点
xend = Math.round(x1);
yend = y1 + gradient * (xend - x1);
xgap = fpart(x1 + 0.5);
const xpxl2 = xend;
const ypxl2 = Math.floor(yend);
plot(xpxl2, ypxl2, rfpart(yend) * xgap);
plot(xpxl2, ypxl2 + 1, fpart(yend) * xgap);
// 主循环
for (let x = xpxl1 + 1; x < xpxl2; x++) {
plot(x, Math.floor(intery), rfpart(intery));
plot(x, Math.floor(intery) + 1, fpart(intery));
intery += gradient;
}
}
// 使用示例
function setPixelWithAlpha(x, y, alpha) {
ctx.fillStyle = `rgba(0, 0, 0, ${alpha})`;
ctx.fillRect(x, y, 1, 1);
}
drawLineAntialiased(10, 10, 100, 60, setPixelWithAlpha);5.6 裁剪算法
5.6.1 裁剪的概念
裁剪（Clipping）
裁剪是去除视窗外部图元的过程，只显示视窗内的部分。
视窗
┌─────────────┐
│ │
│ ╱────╲ │
─────┼───╱──────╲──┼──── ← 部分可见
│ ╱ ╲ │
│ ╱ ╲│
└─────────────┘
↑
需要裁剪
裁剪的目的：
1. 提高渲染效率（不渲染看不见的部分）
2. 保证正确显示（防止绘制到视窗外）5.6.2 Cohen-Sutherland 直线裁剪
Cohen-Sutherland 算法
核心思想：使用区域码（Outcode）快速判断直线与视窗的关系。
区域码定义：
1001 │ 1000 │ 1010
──────┼──────┼──────
0001 │ 0000 │ 0010 ← 中间是视窗
──────┼──────┼──────
0101 │ 0100 │ 0110
4 位分别表示：
- bit 0：左边 (x < xmin)
- bit 1：右边 (x > xmax)
- bit 2：下边 (y < ymin)
- bit 3：上边 (y > ymax)
判断规则：
1. 两端点的 outcode 都是 0000：完全在视窗内，接受
2. 两端点的 outcode 按位与 ≠ 0：完全在视窗外，拒绝
3. 其他情况：部分可见，需要裁剪5.6.3 Cohen-Sutherland 实现
javascript
// 区域码
const INSIDE = 0; // 0000
const LEFT = 1; // 0001
const RIGHT = 2; // 0010
const BOTTOM = 4; // 0100
const TOP = 8; // 1000
/**
* 计算点的区域码
*/
function computeOutCode(x, y, xmin, ymin, xmax, ymax) {
let code = INSIDE;
if (x < xmin) code |= LEFT;
else if (x > xmax) code |= RIGHT;
if (y < ymin) code |= BOTTOM;
else if (y > ymax) code |= TOP;
return code;
}
/**
* Cohen-Sutherland 直线裁剪
* @returns 裁剪后的线段 {x0, y0, x1, y1} 或 null（完全在外）
*/
function clipLineCohenSutherland(x0, y0, x1, y1, xmin, ymin, xmax, ymax) {
let outcode0 = computeOutCode(x0, y0, xmin, ymin, xmax, ymax);
let outcode1 = computeOutCode(x1, y1, xmin, ymin, xmax, ymax);
while (true) {
if ((outcode0 | outcode1) === 0) {
// 完全在内部
return { x0, y0, x1, y1 };
}
if ((outcode0 & outcode1) !== 0) {
// 完全在外部
return null;
}
// 部分可见，需要裁剪
const outcodeOut = outcode0 !== 0 ? outcode0 : outcode1;
let x, y;
// 找到与边界的交点
if (outcodeOut & TOP) {
x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);
y = ymax;
} else if (outcodeOut & BOTTOM) {
x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);
y = ymin;
} else if (outcodeOut & RIGHT) {
y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);
x = xmax;
} else if (outcodeOut & LEFT) {
y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);
x = xmin;
}
// 更新端点
if (outcodeOut === outcode0) {
x0 = x;
y0 = y;
outcode0 = computeOutCode(x0, y0, xmin, ymin, xmax, ymax);
} else {
x1 = x;
y1 = y;
outcode1 = computeOutCode(x1, y1, xmin, ymin, xmax, ymax);
}
}
}
// 使用示例
const clipped = clipLineCohenSutherland(
-10, 20, 150, 80, // 线段
0, 0, 100, 100 // 视窗
);
if (clipped) {
drawLine(clipped.x0, clipped.y0, clipped.x1, clipped.y1, setPixel);
}5.6.4 Sutherland-Hodgman 多边形裁剪
javascript
/**
* Sutherland-Hodgman 多边形裁剪
* @param polygon 多边形顶点数组
* @param clipRect 裁剪矩形 {xmin, ymin, xmax, ymax}
* @returns 裁剪后的多边形顶点
*/
function clipPolygonSutherlandHodgman(polygon, clipRect) {
const { xmin, ymin, xmax, ymax } = clipRect;
// 定义四条边
const edges = [
{ // 左边
inside: (p) => p.x >= xmin,
intersect: (p1, p2) => ({
x: xmin,
y: p1.y + (p2.y - p1.y) * (xmin - p1.x) / (p2.x - p1.x)
})
},
{ // 右边
inside: (p) => p.x <= xmax,
intersect: (p1, p2) => ({
x: xmax,
y: p1.y + (p2.y - p1.y) * (xmax - p1.x) / (p2.x - p1.x)
})
},
{ // 下边
inside: (p) => p.y >= ymin,
intersect: (p1, p2) => ({
x: p1.x + (p2.x - p1.x) * (ymin - p1.y) / (p2.y - p1.y),
y: ymin
})
},
{ // 上边
inside: (p) => p.y <= ymax,
intersect: (p1, p2) => ({
x: p1.x + (p2.x - p1.x) * (ymax - p1.y) / (p2.y - p1.y),
y: ymax
})
}
];
let output = polygon;
// 依次对四条边裁剪
for (const edge of edges) {
if (output.length === 0) break;
const input = output;
output = [];
for (let i = 0; i < input.length; i++) {
const current = input[i];
const next = input[(i + 1) % input.length];
const currentInside = edge.inside(current);
const nextInside = edge.inside(next);
if (currentInside) {
if (nextInside) {
// 两点都在内部：添加下一点
output.push(next);
} else {
// 出去了：添加交点
output.push(edge.intersect(current, next));
}
} else {
if (nextInside) {
// 进来了：添加交点和下一点
output.push(edge.intersect(current, next));
output.push(next);
}
// 两点都在外部：不添加任何点
}
}
}
return output;
}5.7 本章小结
核心算法
| 算法 | 用途 | 特点 |
|---|---|---|
| DDA | 直线绘制 | 简单，浮点运算 |
| Bresenham 直线 | 直线绘制 | 高效，纯整数 |
| 中点圆算法 | 圆绘制 | 利用对称性 |
| 中点椭圆算法 | 椭圆绘制 | 分区处理 |
| 扫描线填充 | 多边形填充 | 高效，通用 |
| 种子填充 | 区域填充 | 简单，递归/迭代 |
| Wu's 抗锯齿 | 抗锯齿直线 | 平滑边缘 |
| Cohen-Sutherland | 直线裁剪 | 区域码快速判断 |
算法选择指南
选择直线算法：
- 精度要求不高 → DDA
- 追求效率 → Bresenham
- 需要平滑 → Wu's 抗锯齿
选择填充算法：
- 简单形状、交互式 → 种子填充
- 复杂多边形 → 扫描线填充
选择裁剪算法：
- 直线裁剪 → Cohen-Sutherland
- 多边形裁剪 → Sutherland-Hodgman下一章预告：在第6章中，我们将学习曲线与曲面的数学表示，包括贝塞尔曲线、B-样条和 NURBS。
文档版本：v1.0
字数统计：约 12,000 字