引言
折纸（Origami）是一门将二维纸张通过折叠变换为三维造型的艺术。在计算几何领域，折纸问题涉及平面折叠序列规划与几何约束满足两大核心算法挑战：给定目标形状，如何确定折叠的顺序与角度？本文用Java实现折纸的平面几何仿真系统，讲解折痕直线计算、面片翻折变换以及刚性折叠的约束传播判定算法。
问题分析
折纸的数学模型
一张平面纸可建模为多边形网格，每条折痕（crease）将纸面划分为可相对转动的两个部分：
– 山折（Mountain）：折痕凸起，两面夹角小于180°
– 谷折（Valley）：折痕凹陷，两面夹角大于180°
– 面片（Facet）：折痕之间的多边形区域，折叠过程中保持刚性不变形
刚性折叠约束
刚性折叠要求每个面片在折叠过程中保持平面且形状不变，只允许绕折痕旋转。这产生了一组角度约束方程：围绕每个顶点的所有扇形角之和必须满足特定的相容性条件。
核心算法一：折痕的直线方程与面片变换
给定折痕的两个端点，计算该直线将平面分割为两个半平面。折叠操作本质上是关于折痕直线的镜像反射：
P' = P - 2 * ((P - A) · n) * n
其中 n 为折痕直线的单位法向量，A 为直线上任一点。
核心算法二：Kawasaki-Justin定理与刚性折叠判定
Kawasaki-Justin定理给出了单个顶点可刚性折叠的充要条件：围绕顶点的交替扇形角之和等于 π。
α₁ + α₃ + α₅ + ... = α₂ + α₄ + α₆ + ... = π
本文实现该定理的判定算法，并基于约束传播思想验证整个折纸图案是否可刚性折叠。
完整Java实现
package origami.geometry;
import java.util.*;
/**
* 折纸几何仿真系统
*
* 核心功能：
* 1. 折痕直线计算：两点确定直线，分割半平面
* 2. 面片翻折变换：关于折痕直线的镜像反射
* 3. Kawasaki-Justin定理：单顶点刚性折叠判定
* 4. 约束传播：全局折叠序列验证
*/
public class OrigamiSimulator {
// 精度阈值
private static final double EPS = 1e-9;
/**
* 二维点/向量
*/
public static class Point {
public final double x, y;
public Point(double x, double y) { this.x = x; this.y = y; }
public Point add(Point p) { return new Point(x + p.x, y + p.y); }
public Point sub(Point p) { return new Point(x - p.x, y - p.y); }
public Point mul(double s) { return new Point(x * s, y * s); }
public double dot(Point p) { return x * p.x + y * p.y; }
public double cross(Point p) { return x * p.y - y * p.x; }
public double length() { return Math.sqrt(x * x + y * y); }
public Point normalize() {
double len = length();
if (len < EPS) return new Point(0, 0);
return new Point(x / len, y / len);
}
@Override
public String toString() { return String.format("(%.3f, %.3f)", x, y); }
}
/**
* 折痕：由两点定义的直线段，附带折叠方向
*/
public static class Crease {
public final Point p1, p2;
public final boolean mountain; // true=山折, false=谷折
public final double foldAngle; // 折叠角度 (0 = 平铺, π = 完全对折)
public Crease(Point p1, Point p2, boolean mountain, double foldAngle) {
this.p1 = p1;
this.p2 = p2;
this.mountain = mountain;
this.foldAngle = foldAngle;
}
/**
* 获取折痕直线的单位方向向量
*/
public Point direction() {
return p2.sub(p1).normalize();
}
/**
* 获取折痕直线的单位法向量（指向"右侧"半平面）
*/
public Point normal() {
Point dir = direction();
return new Point(-dir.y, dir.x); // 逆时针旋转90°
}
/**
* 判断点位于折痕的哪一侧
* 返回值 > 0：右侧（法向量方向）
* 返回值 < 0：左侧
* 返回值 = 0：在直线上
*/
public double sideOf(Point p) {
Point n = p2.sub(p1);
return n.cross(p.sub(p1));
}
}
/**
* 面片：由顶点序列定义的多边形
*/
public static class Facet {
public List<Point> vertices;
public int id;
public Facet(List<Point> vertices, int id) {
this.vertices = new ArrayList<>(vertices);
this.id = id;
}
/**
* 计算多边形面积（有向面积，正值表示逆时针）
*/
public double area() {
double sum = 0;
int n = vertices.size();
for (int i = 0; i < n; i++) {
Point a = vertices.get(i);
Point b = vertices.get((i + 1) % n);
sum += a.cross(b);
}
return sum / 2;
}
/**
* 判断点是否在面片内部（射线法）
*/
public boolean contains(Point p) {
int n = vertices.size();
boolean inside = false;
for (int i = 0, j = n - 1; i < n; j = i++) {
Point pi = vertices.get(i);
Point pj = vertices.get(j);
if (((pi.y > p.y) != (pj.y > p.y)) &&
(p.x < (pj.x - pi.x) * (p.y - pi.y) / (pj.y - pi.y) + pi.x)) {
inside = !inside;
}
}
return inside;
}
}
/**
* 将点 P 关于由点 A 和方向 dir 定义的直线做镜像反射
*/
public static Point reflect(Point P, Point A, Point dir) {
Point AP = P.sub(A);
// 投影长度
double proj = AP.dot(dir);
// 投影点
Point projPoint = A.add(dir.mul(proj));
// 反射点 = 投影点 - (P - 投影点) = 2*投影点 - P
return projPoint.mul(2).sub(P);
}
/**
* 将整个面片关于指定折痕做翻折变换
* 只变换位于折痕"左侧"（side < 0）的点
*/
public static Facet foldFacet(Facet facet, Crease crease) {
Point dir = crease.direction();
List<Point> newVertices = new ArrayList<>();
for (Point v : facet.vertices) {
if (crease.sideOf(v) < -EPS) {
// 点位于折叠侧，执行镜像反射
newVertices.add(reflect(v, crease.p1, dir));
} else {
// 点位于固定侧，保持不变
newVertices.add(v);
}
}
return new Facet(newVertices, facet.id);
}
/**
* Kawasaki-Justin定理判定
* 给定围绕一个顶点的所有扇形角（按顺序），判定该顶点是否可刚性折叠
*
* 定理：交替扇形角之和相等，即 α₁+α₃+... = α₂+α₄+... = π
*
* @param sectorAngles 围绕顶点的扇形角数组（弧度，按逆时针顺序）
* @return true 如果满足Kawasaki-Justin条件
*/
public static boolean kawasakiJustinCheck(double[] sectorAngles) {
int n = sectorAngles.length;
if (n % 2 != 0) return false; // 必须偶数个扇形
double oddSum = 0, evenSum = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) oddSum += sectorAngles[i];
else evenSum += sectorAngles[i];
}
return Math.abs(oddSum - Math.PI) < EPS && Math.abs(evenSum - Math.PI) < EPS;
}
/**
* 计算围绕某顶点的扇形角
* @param center 中心顶点
* @param neighbors 相邻顶点（按逆时针顺序排列）
* @return 扇形角数组
*/
public static double[] computeSectorAngles(Point center, List<Point> neighbors) {
int n = neighbors.size();
double[] angles = new double[n];
for (int i = 0; i < n; i++) {
Point v1 = neighbors.get(i).sub(center);
Point v2 = neighbors.get((i + 1) % n).sub(center);
// 扇形角 = v1 到 v2 的夹角
double dot = v1.dot(v2);
double cross = v1.cross(v2);
angles[i] = Math.atan2(cross, dot);
if (angles[i] < 0) angles[i] += 2 * Math.PI;
}
return angles;
}
/**
* 折纸图案类：管理面片和折痕的集合
*/
public static class OrigamiPattern {
public List<Facet> facets;
public List<Crease> creases;
public OrigamiPattern() {
facets = new ArrayList<>();
creases = new ArrayList<>();
}
/**
* 执行一次折叠操作
*/
public void applyFold(Crease crease) {
List<Facet> newFacets = new ArrayList<>();
for (Facet f : facets) {
newFacets.add(foldFacet(f, crease));
}
facets = newFacets;
}
/**
* 打印当前所有面片的状态
*/
public void printState() {
System.out.println("===== 当前折纸状态 =====");
for (Facet f : facets) {
System.out.print("面片 " + f.id + ": ");
for (Point v : f.vertices) {
System.out.print(v + " ");
}
System.out.println();
}
}
}
/**
* 创建一个简单的正方形折纸（单面片）
*/
public static OrigamiPattern createSquare(double size) {
OrigamiPattern pattern = new OrigamiPattern();
List<Point> square = Arrays.asList(
new Point(0, 0),
new Point(size, 0),
new Point(size, size),
new Point(0, size)
);
pattern.facets.add(new Facet(square, 0));
return pattern;
}
/**
* 创建带有预设折痕的正方形折纸
*/
public static OrigamiPattern createSquareWithDiagonal(double size) {
OrigamiPattern pattern = createSquare(size);
// 添加对角线折痕
pattern.creases.add(new Crease(
new Point(0, 0), new Point(size, size), true, Math.PI / 2));
return pattern;
}
/**
* 约束传播：验证整个折纸图案的所有顶点是否满足刚性折叠条件
*/
public static boolean validateRigidFoldability(OrigamiPattern pattern) {
// 提取所有顶点及其相邻面片
Map<Point, List<Point>> vertexNeighbors = new HashMap<>();
for (Facet f : pattern.facets) {
int n = f.vertices.size();
for (int i = 0; i < n; i++) {
Point v = f.vertices.get(i);
Point prev = f.vertices.get((i - 1 + n) % n);
Point next = f.vertices.get((i + 1) % n);
vertexNeighbors.computeIfAbsent(v, k -> new ArrayList<>());
if (!vertexNeighbors.get(v).contains(prev)) vertexNeighbors.get(v).add(prev);
if (!vertexNeighbors.get(v).contains(next)) vertexNeighbors.get(v).add(next);
}
}
// 对每个内部顶点应用Kawasaki-Justin判定
boolean valid = true;
for (Map.Entry<Point, List<Point>> entry : vertexNeighbors.entrySet()) {
List<Point> neighbors = entry.getValue();
if (neighbors.size() >= 4) {
double[] sectors = computeSectorAngles(entry.getKey(), neighbors);
boolean kj = kawasakiJustinCheck(sectors);
if (!kj) {
System.out.println("顶点 " + entry.getKey() + " 不满足Kawasaki-Justin条件");
valid = false;
}
}
}
return valid;
}
// ==================== 测试入口 ====================
public static void main(String[] args) {
System.out.println("===== 折纸几何仿真系统 =====\n");
// 测试1：镜像反射
System.out.println("【测试1】点关于直线的镜像反射");
Point P = new Point(2, 3);
Point A = new Point(0, 0);
Point B = new Point(5, 5);
Point reflected = reflect(P, A, B.sub(A).normalize());
System.out.println("原点 P = " + P);
System.out.println("关于直线 (0,0)-(5,5) 的镜像 = " + reflected);
System.out.println();
// 测试2：Kawasaki-Justin定理
System.out.println("【测试2】Kawasaki-Justin刚性折叠判定");
// 标准水 bomb 底的扇形角：4个90°扇形
double[] waterBombAngles = {Math.PI/2, Math.PI/2, Math.PI/2, Math.PI/2};
System.out.println("水炸弹底 (4×90°): " + kawasakiJustinCheck(waterBombAngles));
// 不满足条件的角
double[] badAngles = {Math.PI/3, Math.PI/3, Math.PI/3, Math.PI/2};
System.out.println("不规则角 (60°,60°,60°,90°): " + kawasakiJustinCheck(badAngles));
System.out.println();
// 测试3：正方形对角线折叠
System.out.println("【测试3】正方形对角线折叠");
OrigamiPattern pattern = createSquareWithDiagonal(10);
System.out.println("折叠前：");
pattern.printState();
Crease diagonal = pattern.creases.get(0);
pattern.applyFold(diagonal);
System.out.println("\n沿对角线折叠后：");
pattern.printState();
System.out.println();
// 测试4：约束传播验证
System.out.println("【测试4】刚性折叠约束验证");
OrigamiPattern simple = createSquare(10);
boolean valid = validateRigidFoldability(simple);
System.out.println("单面片正方形是否可刚性折叠: " + valid);
}
}
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 点镜像反射 | O(1) | 固定次数的向量运算 |
| 面片折叠 | O(v) | v为面片顶点数 |
| Kawasaki判定 | O(k) | k为顶点扇形数 |
| 全局约束验证 | O(V × k log k) | V为顶点数，需排序邻居 |
| 空间复杂度 | O(F × v) | F为面片数 |
扩展与优化
- 树状折叠序列：将折叠顺序建模为二叉树，每个内部节点代表一次折叠操作
- Maekawa-Justin定理：额外验证每个顶点的山折/谷折数量差为 ±2
- 三维展开：将折叠后的二维面片映射到三维空间，计算各面片的法向量
- 自动折痕生成：给定目标3D形状，通过优化算法反推折痕图案
- 数值稳定性：对于接近共线的点，使用高精度浮点或符号计算
总结
本文用Java实现了折纸的平面几何仿真系统，将计算几何中的镜像变换与折纸数学中的Kawasaki-Justin定理进行了有机结合。通过将折纸问题抽象为面片集合的刚性变换，我们不仅实现了基础的折叠模拟，还建立了可折叠性的形式化判定框架。这种”几何建模 + 约束验证”的方法论，在计算机辅助设计（CAD）、可展开结构和折叠机器人等领域都有重要应用。
