▶ 书中第六章部分程序，包括在加上自己补充的代码，粒子碰撞系统及用到的粒子类
● 粒子系统
package package01; import java.awt.Color;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.Particle; public class class01
{
private static final double HZ = 0.5; // 每个时间步长内重画的次数
private MinPQ<Event> pq; // 优先队列
private double t = 0.0; // 计时器
private Particle[] particles; // 粒子数据列表 private static class Event implements Comparable<Event> // 碰撞事件类
{
private final double time; // 预计事件发生时间
private final Particle a, b; // 事件中的粒子
private final int countA, countB; // 粒子在加入事件中时的已碰撞的次数 public Event(double inputT, Particle inputA, Particle inputB) // 输入当前时间和两个粒子，计算碰撞事件
{
time = inputT;
a = inputA;
b = inputB;
countA = (a != null) ? a.count() : -1;
countB = (b != null) ? b.count() : -1;
} public int compareTo(Event that) // 比较两个事件哪个先发生
{
return Double.compare(this.time, that.time);
} public boolean isValid() // 判断事件是否有效
{
return (a == null || a.count() == countA) && (b == null || b.count() == countB);// 原代码简化版
//if (a != null && a.count() != countA || b != null && b.count() != countB) // 原代码，只要有粒子当前实际碰撞数与事件中记录的 count 不等，说明事件失效
// return false;
//return true;
}
} public class01(Particle[] inputParticle)
{
particles = inputParticle.clone(); // 输入列表的深拷贝
} private void predict(Particle a, double limit) // 更新优先队列中关于粒子 a 的事件
{
if (a == null)
return;
for (int i = 0; i < particles.length; i++) // 预测 a 与各粒子碰撞的时间，只要时间小于阈值就将其放入优先队列
{
double targetTime = t + a.timeToHit(particles[i]);
if (targetTime <= limit)
pq.insert(new Event(targetTime, a, particles[i]));
}
double targetTimeX = t + a.timeToHitVerticalWall(), targetTimeY = t + a.timeToHitHorizontalWall();
if (targetTimeX <= limit)
pq.insert(new Event(targetTimeX, a, null));
if (targetTimeY <= limit)
pq.insert(new Event(targetTimeY, null, a));
} private void redraw(double limit) // 重画所有粒子位置
{
StdDraw.clear();
for (int i = 0; i < particles.length; i++)
particles[i].draw();
StdDraw.show();
StdDraw.pause(20); // 暂停 20 ms
if (t < limit) // 还没到时限，加入重画事件
pq.insert(new Event(t + 1.0 / HZ, null, null));
} public void simulate(double limit) // 模拟器
{
pq = new MinPQ<Event>();
for (int i = 0; i < particles.length; i++) // 首次计算所有粒子之间的碰撞
predict(particles[i], limit);
for (pq.insert(new Event(0, null, null)); !pq.isEmpty();) // 多加入一个重画所有粒子位置的事件
{
Event e = pq.delMin(); // 取出发生时间最近的时间，判断是否有效
if (!e.isValid())
continue;
Particle a = e.a, b = e.b;
for (int i = 0; i < particles.length; i++) // 更新所有粒子位置
particles[i].move(e.time - t);
t = e.time; // 更新当前时间 if (a != null && b != null) // 粒子 - 粒子碰撞
a.bounceOff(b);
else if (a != null && b == null) // 粒子撞竖直墙壁
a.bounceOffVerticalWall();
else if (a == null && b != null)
b.bounceOffHorizontalWall(); // 粒子撞水平墙壁
else if (a == null && b == null)
redraw(limit); // 仅重画所有粒子位置
predict(a, limit); // 重新预测 a 与 b相关的事件
predict(b, limit);
}
} public static void main(String[] args)
{
StdDraw.setCanvasSize(600, 600); // 窗口大小
StdDraw.enableDoubleBuffering(); // double 缓冲区
Particle[] particles; // 粒子列表 if (args.length == 1) // 输入一个参数，生成相应个数的个粒子
{
int n = Integer.parseInt(args[0]);
particles = new Particle[n];
for (int i = 0; i < n; i++)
particles[i] = new Particle();
}
else // 否则按标准输入流依次输入每个粒子的信息
{
int n = StdIn.readInt();
particles = new Particle[n];
for (int i = 0; i < n; i++)
{
double rx = StdIn.readDouble();
double ry = StdIn.readDouble();
double vx = StdIn.readDouble();
double vy = StdIn.readDouble();
double radius = StdIn.readDouble();
double mass = StdIn.readDouble();
int r = StdIn.readInt();
int g = StdIn.readInt();
int b = StdIn.readInt();
Color color = new Color(r, g, b);
particles[i] = new Particle(rx, ry, vx, vy, radius, mass, color);
}
}
class01 system = new class01(particles); // 模拟和输出
system.simulate(10000); // 模拟事件 10s
}
}
● 粒子类
package package01; import java.awt.Color;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdRandom; public class class01
{
private static final double INFINITY = Double.POSITIVE_INFINITY; private double rx, ry;
private double vx, vy;
private int count; // 粒子已经碰撞的次数
private final double radius;
private final double mass;
private final Color color; public class01(double inputRx, double inputRy, double inputVx, double inputVy, double inputRadius, double inputMass, Color inputColor)
{
rx = inputRx;
ry = inputRy;
vx = inputVx;
vy = inputVy;
radius = inputRadius;
mass = inputMass;
color = inputColor;
} public class01()
{
rx = StdRandom.uniform(0.0, 1.0);
ry = StdRandom.uniform(0.0, 1.0);
vx = StdRandom.uniform(-0.005, 0.005);
vy = StdRandom.uniform(-0.005, 0.005);
radius = 0.02;
mass = 0.5;
color = Color.BLACK;
} public void move(double dt)
{
rx += vx * dt;
ry += vy * dt;
} public void draw() // 绘制粒子
{
StdDraw.setPenColor(color);
StdDraw.filledCircle(rx, ry, radius);
} public int count()
{
return count;
} public double timeToHit(class01 that)
{
if (this == that)
return INFINITY;
double dx = that.rx - rx, dy = that.ry - ry, dvx = that.vx - vx, dvy = that.vy - vy;
double dvdr = dx * dvx + dy * dvy;
if (dvdr > 0) // Δx 与 Δv 同号，不会撞
return INFINITY;
double dvdv = dvx * dvx + dvy * dvy;
if (dvdv == 0) // 速度完全相等，不会撞
return INFINITY;
double drdr = dx * dx + dy * dy;
double dist = radius + that.radius;
double d = (dvdr*dvdr) - dvdv * (drdr - dist * dist);
return (d > 0) ? -(dvdr + Math.sqrt(d)) / dvdv : INFINITY;
} public double timeToHitVerticalWall()
{
return (vx > 0) ? (1.0 - rx - radius) / vx : ((vx < 0) ? (radius - rx) / vx : INFINITY);
} public double timeToHitHorizontalWall()
{
return (vy > 0) ? (1.0 - ry - radius) / vy : ((vy < 0) ? (radius - ry) / vy : INFINITY);
} public void bounceOff(class01 that)
{
double dx = that.rx - rx, dy = that.ry - ry;
double dvx = that.vx - vx, dvy = that.vy - vy;
double dvdr = dx * dvx + dy * dvy;
double dist = radius + that.radius;
double magnitude = 2 * mass * that.mass * dvdr / ((mass + that.mass) * dist);
double fx = magnitude * dx / dist, fy = magnitude * dy / dist;
vx += fx / mass;
vy += fy / mass;
that.vx -= fx / that.mass;
that.vy -= fy / that.mass;
count++;
that.count++;
} public void bounceOffVerticalWall()
{
vx = -vx;
count++;
} public void bounceOffHorizontalWall()
{
vy = -vy;
count++;
} public double kineticEnergy()
{
return 0.5 * mass * (vx*vx + vy * vy);
}
}