图形算法
2025年2月26日大约 5 分钟
图形算法在计算机图形学中占据核心地位，广泛应用于图像渲染、游戏开发、图像处理等领域。通过数学和编程实现几何图形的生成和操作，是该领域的基本技能之一。
目录
1. 什么是图形算法
图形算法 是用于绘制、裁剪、变换和处理几何图形（点、线、面及其它图形）的算法集合，属于计算机图形学的重要研究领域。它为图形的生成、变形、裁剪、着色等操作提供支持。
应用场景
- 游戏开发
- CAD 工具（如 AutoCAD）
- 图像编辑（如 Photoshop）
- 3D 建模与渲染
2. 图形算法分类
图形算法根据功能与用途分类为以下几种：
- 基础几何算法：点、线、面及几何变换操作。
- 线性绘制算法：用于高效绘制直线或曲线。
- 图形填充算法：对多边形或区域内部进行填充（颜色、纹理）。
- 几何变换算法：对几何图形进行平移、旋转或缩放。
- 裁剪算法：对图形进行裁剪，保留特定部分。
3. 基础几何算法
3.1 点在圆内判断
原理
判断一个点是否在圆内，通过计算点与圆心之间的距离是否小于或等于圆的半径。
Java 实现
public class PointInCircle {
public static boolean isPointInCircle(int x, int y, int centerX, int centerY, int radius) {
int distanceSquared = (x - centerX) * (x - centerX) + (y - centerY) * (y - centerY);
return distanceSquared <= radius * radius;
}
public static void main(String[] args) {
System.out.println(isPointInCircle(3, 4, 0, 0, 5)); // true
}
}3.2 点在多边形内判断
原理
- 射线算法：从给定点向任意方向发射一条射线，计算射线经过多边形边的次数（奇数在内部，偶数在外部）。
Java 实现
import java.awt.geom.Point2D;
import java.util.List;
public class PointInPolygon {
public static boolean isPointInPolygon(Point2D.Double point, List<Point2D.Double> polygon) {
int intersections = 0;
for (int i = 0; i < polygon.size(); i++) {
Point2D.Double p1 = polygon.get(i);
Point2D.Double p2 = polygon.get((i + 1) % polygon.size());
if ((point.y > Math.min(p1.y, p2.y)) && (point.y <= Math.max(p1.y, p2.y))
&& (point.x <= Math.max(p1.x, p2.x))
&& (p1.y != p2.y)) {
double xinters = (point.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x;
if (xinters > point.x) {
intersections++;
}
}
}
return intersections % 2 != 0;
}
public static void main(String[] args) {
List<Point2D.Double> polygon = List.of(
new Point2D.Double(0, 0),
new Point2D.Double(4, 0),
new Point2D.Double(4, 4),
new Point2D.Double(0, 4)
);
Point2D.Double point = new Point2D.Double(2, 2);
System.out.println(isPointInPolygon(point, polygon)); // true
}
}3.3 线段相交检测
原理
利用向量叉乘判断两条线段是否相交。
Java 实现
import java.awt.geom.Line2D;
public class LineIntersection {
public static boolean doIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
return Line2D.linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4);
}
public static void main(String[] args) {
System.out.println(doIntersect(1, 1, 10, 1, 1, 2, 10, 2)); // false
System.out.println(doIntersect(10, 0, 0, 10, 0, 0, 10, 10)); // true
}
}4. 线性绘制算法
4.1 数字微分分析算法（DDA 算法）
原理
通过增量计算，每次递增一个单位，计算出线段上所有点。
Java 实现
public class DDAAlgorithm {
public static void drawLine(int x1, int y1, int x2, int y2) {
int dx = x2 - x1, dy = y2 - y1;
int steps = Math.max(Math.abs(dx), Math.abs(dy));
double xIncrement = dx / (double) steps;
double yIncrement = dy / (double) steps;
double x = x1, y = y1;
for (int i = 0; i <= steps; i++) {
System.out.println("Point: (" + Math.round(x) + ", " + Math.round(y) + ")");
x += xIncrement;
y += yIncrement;
}
}
public static void main(String[] args) {
drawLine(2, 3, 10, 8);
}
}4.2 Bresenham 直线算法
原理
通过整数运算高效计算线段上的点，适合离散绘制系统。
Java 实现
public class BresenhamLine {
public static void drawLine(int x1, int y1, int x2, int y2) {
int dx = Math.abs(x2 - x1), dy = Math.abs(y2 - y1);
int sx = x1 < x2 ? 1 : -1, sy = y1 < y2 ? 1 : -1;
int err = dx - dy;
while (true) {
System.out.println("Point: (" + x1 + ", " + y1 + ")");
if (x1 == x2 && y1 == y2) break;
int e2 = 2 * err;
if (e2 > -dy) {
err -= dy;
x1 += sx;
}
if (e2 < dx) {
err += dx;
y1 += sy;
}
}
}
public static void main(String[] args) {
drawLine(2, 3, 10, 8);
}
}5. 图形填充算法
5.1 扫描线算法
应用
用于多边形的填充，计算每一行需要填充的像素点。
5.2 种子填充算法
应用
递归填充区域中所有像素点。
6. 几何变换
6.1 二维变换
运算矩阵
- 平移：
T = [[1, 0, Tx], [0, 1, Ty], [0, 0, 1]] - 旋转：
R = [[cosθ, -sinθ, 0], [sinθ, cosθ, 0], [0, 0, 1]] - 缩放：
S = [[Sx, 0, 0], [0, Sy, 0], [0, 0, 1]]
7. 裁剪算法
7.1 Cohen-Sutherland 线段裁剪
7.2 Sutherland-Hodgman 多边形裁剪
8. 总结
本文总结了图形算法中常用的几何运算、线性绘制及相关操作算法，重点实现了基础功能，适合初学者学习。实际开发中可以借助图形库（如 Java AWT、OpenGL）完成更复杂的图形任务。