图形算法在计算机图形学中占据核心地位，广泛应用于图像渲染、游戏开发、图像处理等领域。通过数学和编程实现几何图形的生成和操作，是该领域的基本技能之一。
目录什么是图形算法图形算法分类基础几何算法点在圆内判断点在多边形内判断线段相交检测线性绘制算法数字微分分析算法（DDA 算法）Bresenham 直线算法图形填充算法扫描线算法种子填充算法几何变换二维变换三维变换裁剪算法Cohen-Sutherland 线段裁剪Sutherland-Hodgman 多边形裁剪总结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
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
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）完成更复杂的图形任务。