package lujing;
|
import java.util.ArrayList;
|
import java.util.LinkedList;
|
import java.util.List;
|
import java.util.stream.Collectors;
|
|
public class WangfanpathJisuan {
|
|
/**
|
* 坐标点类，使用记录处理提高精度控制
|
*/
|
private static class Point {
|
final double x;
|
final double y;
|
final int originalIndex; // 记录原始位置，便于调试
|
|
Point(double x, double y, int index) {
|
this.x = x;
|
this.y = y;
|
this.originalIndex = index;
|
}
|
|
Point(double x, double y) {
|
this(x, y, -1);
|
}
|
|
double distanceTo(Point other) {
|
if (other == null) return Double.MAX_VALUE;
|
double dx = this.x - other.x;
|
double dy = this.y - other.y;
|
return Math.sqrt(dx * dx + dy * dy);
|
}
|
|
@Override
|
public boolean equals(Object obj) {
|
if (this == obj) return true;
|
if (obj == null || getClass() != obj.getClass()) return false;
|
Point point = (Point) obj;
|
// 使用1e-6的精度判断相等，比直接比较double更稳定
|
return Math.abs(point.x - x) < 1e-6 && Math.abs(point.y - y) < 1e-6;
|
}
|
|
@Override
|
public int hashCode() {
|
// 使用固定精度进行哈希计算，确保精度范围内相等的点有相同哈希值
|
long xBits = Double.doubleToLongBits(Math.round(x * 1e6) / 1e6);
|
long yBits = Double.doubleToLongBits(Math.round(y * 1e6) / 1e6);
|
return (int)(xBits ^ (xBits >>> 32) ^ yBits ^ (yBits >>> 32));
|
}
|
|
@Override
|
public String toString() {
|
return String.format("%.3f,%.3f", x, y);
|
}
|
|
public String toString(int precision) {
|
return String.format("%." + precision + "f,%." + precision + "f", x, y);
|
}
|
}
|
|
/**
|
* 线段类，用于计算点到线段的距离
|
*/
|
private static class LineSegment {
|
final Point start;
|
final Point end;
|
final double length;
|
|
LineSegment(Point start, Point end) {
|
this.start = start;
|
this.end = end;
|
this.length = start.distanceTo(end);
|
}
|
|
/**
|
* 计算点到线段的垂直距离
|
*/
|
double perpendicularDistance(Point point) {
|
if (length == 0) {
|
return point.distanceTo(start);
|
}
|
|
// 使用向量方法计算投影距离
|
double x1 = start.x, y1 = start.y;
|
double x2 = end.x, y2 = end.y;
|
double x0 = point.x, y0 = point.y;
|
|
// 计算点到直线距离公式
|
double numerator = Math.abs((y2 - y1) * x0 - (x2 - x1) * y0 + x2 * y1 - y2 * x1);
|
double denominator = Math.sqrt((y2 - y1) * (y2 - y1) + (x2 - x1) * (x2 - x1));
|
|
return numerator / denominator;
|
}
|
|
/**
|
* 判断点是否在线段的边界框内（用于判断是否在线段上）
|
*/
|
boolean isPointInBoundingBox(Point point) {
|
double minX = Math.min(start.x, end.x);
|
double maxX = Math.max(start.x, end.x);
|
double minY = Math.min(start.y, end.y);
|
double maxY = Math.max(start.y, end.y);
|
|
return point.x >= minX && point.x <= maxX &&
|
point.y >= minY && point.y <= maxY;
|
}
|
}
|
|
/**
|
* 优化配置类
|
*/
|
public static class OptimizationConfig {
|
private double distanceTolerance = 0.1; // 距离容差（米）
|
private double angleTolerance = 1.0; // 角度容差（度）
|
private int outputPrecision = 3; // 输出精度（小数位数）
|
private boolean keepEndpoints = true; // 是否保留端点
|
private boolean useFastSimplify = false; // 是否使用快速简化算法
|
|
public OptimizationConfig() {}
|
|
public OptimizationConfig setDistanceTolerance(double tolerance) {
|
this.distanceTolerance = Math.max(0.01, tolerance); // 最小0.01米
|
return this;
|
}
|
|
public OptimizationConfig setAngleTolerance(double degrees) {
|
this.angleTolerance = Math.max(0.1, Math.min(degrees, 45)); // 限制在0.1-45度
|
return this;
|
}
|
|
public OptimizationConfig setOutputPrecision(int precision) {
|
this.outputPrecision = Math.max(0, Math.min(precision, 8)); // 限制在0-8位
|
return this;
|
}
|
|
public OptimizationConfig setKeepEndpoints(boolean keep) {
|
this.keepEndpoints = keep;
|
return this;
|
}
|
|
public OptimizationConfig setUseFastSimplify(boolean useFast) {
|
this.useFastSimplify = useFast;
|
return this;
|
}
|
}
|
|
private OptimizationConfig config;
|
|
public WangfanpathJisuan() {
|
this.config = new OptimizationConfig();
|
}
|
|
public WangfanpathJisuan(OptimizationConfig config) {
|
this.config = config;
|
}
|
|
/**
|
* 主优化方法
|
*/
|
public String optimizePath(String pathStr) {
|
return optimizePath(pathStr, this.config);
|
}
|
|
/**
|
* 带配置的优化方法
|
*/
|
public String optimizePath(String pathStr, OptimizationConfig config) {
|
if (pathStr == null || pathStr.trim().isEmpty()) {
|
return "";
|
}
|
|
List<Point> points = parsePoints(pathStr);
|
if (points.size() <= 2) {
|
return pointsToString(points, config.outputPrecision);
|
}
|
|
// 执行优化流水线
|
List<Point> result = optimizationPipeline(points, config);
|
|
return pointsToString(result, config.outputPrecision);
|
}
|
|
/**
|
* 优化流水线：按顺序执行多个优化步骤
|
*/
|
private List<Point> optimizationPipeline(List<Point> points, OptimizationConfig config) {
|
List<Point> result = new ArrayList<>(points);
|
|
// 步骤1: 去除连续重复点
|
result = removeConsecutiveDuplicates(result);
|
|
// 步骤2: 根据配置选择简化算法
|
if (config.useFastSimplify) {
|
result = fastSimplify(result, config.distanceTolerance, config.angleTolerance);
|
} else {
|
result = douglasPeuckerSimplify(result, config.distanceTolerance);
|
}
|
|
// 步骤3: 确保端点（可选）
|
if (config.keepEndpoints && result.size() > 1) {
|
ensureEndpoints(points, result);
|
}
|
|
return result;
|
}
|
|
/**
|
* 解析坐标点，带位置索引
|
*/
|
private List<Point> parsePoints(String pathStr) {
|
List<Point> points = new ArrayList<>();
|
String[] pointStrs = pathStr.split(";");
|
|
for (int i = 0; i < pointStrs.length; i++) {
|
String pointStr = pointStrs[i].trim();
|
if (pointStr.isEmpty()) continue;
|
|
String[] xy = pointStr.split(",");
|
if (xy.length != 2) continue;
|
|
try {
|
double x = Double.parseDouble(xy[0].trim());
|
double y = Double.parseDouble(xy[1].trim());
|
points.add(new Point(x, y, i));
|
} catch (NumberFormatException e) {
|
// 跳过格式错误的点，记录日志（实际使用时可添加日志）
|
continue;
|
}
|
}
|
|
return points;
|
}
|
|
/**
|
* 去除连续重复点（优化版）
|
*/
|
private List<Point> removeConsecutiveDuplicates(List<Point> points) {
|
if (points.size() <= 1) {
|
return new ArrayList<>(points);
|
}
|
|
List<Point> result = new ArrayList<>(points.size());
|
result.add(points.get(0));
|
|
for (int i = 1; i < points.size(); i++) {
|
Point current = points.get(i);
|
Point last = result.get(result.size() - 1);
|
|
// 使用距离判断是否重复，考虑浮点精度
|
if (current.distanceTo(last) > config.distanceTolerance * 0.1) {
|
result.add(current);
|
}
|
// 如果距离很小但实际是不同的点（浮点误差），仍保留
|
else if (!current.equals(last)) {
|
result.add(current);
|
}
|
}
|
|
return result;
|
}
|
|
/**
|
* 快速简化算法（结合距离和角度判断）
|
*/
|
private List<Point> fastSimplify(List<Point> points, double distanceTolerance, double angleToleranceDeg) {
|
if (points.size() < 3) {
|
return new ArrayList<>(points);
|
}
|
|
List<Point> result = new ArrayList<>();
|
result.add(points.get(0));
|
|
int i = 1;
|
while (i < points.size() - 1) {
|
Point prev = result.get(result.size() - 1);
|
Point current = points.get(i);
|
Point next = points.get(i + 1);
|
|
// 检查距离条件
|
double distToPrev = current.distanceTo(prev);
|
double distToNext = current.distanceTo(next);
|
|
// 检查角度条件（将角度容差转换为弧度）
|
double angleToleranceRad = Math.toRadians(angleToleranceDeg);
|
double angle = calculateAngle(prev, current, next);
|
|
// 如果点距离前一点或后一点很近，或者三点形成的角度接近180度（共线），则剔除当前点
|
if (distToPrev < distanceTolerance ||
|
distToNext < distanceTolerance ||
|
Math.abs(Math.PI - angle) < angleToleranceRad) {
|
i++; // 跳过当前点
|
} else {
|
result.add(current);
|
i++;
|
}
|
}
|
|
// 添加最后一个点
|
if (points.size() > 1) {
|
result.add(points.get(points.size() - 1));
|
}
|
|
return result;
|
}
|
|
/**
|
* 计算三点形成的角度（以中间点为顶点）
|
*/
|
private double calculateAngle(Point a, Point b, Point c) {
|
double baX = a.x - b.x;
|
double baY = a.y - b.y;
|
double bcX = c.x - b.x;
|
double bcY = c.y - b.y;
|
|
double dotProduct = baX * bcX + baY * bcY;
|
double magnitudeBA = Math.sqrt(baX * baX + baY * baY);
|
double magnitudeBC = Math.sqrt(bcX * bcX + bcY * bcY);
|
|
if (magnitudeBA == 0 || magnitudeBC == 0) {
|
return 0;
|
}
|
|
double cosAngle = dotProduct / (magnitudeBA * magnitudeBC);
|
// 处理浮点误差
|
cosAngle = Math.max(-1.0, Math.min(1.0, cosAngle));
|
|
return Math.acos(cosAngle);
|
}
|
|
/**
|
* 道格拉斯-普克算法（迭代实现，避免递归栈溢出）
|
*/
|
private List<Point> douglasPeuckerSimplify(List<Point> points, double epsilon) {
|
if (points.size() <= 2) {
|
return new ArrayList<>(points);
|
}
|
|
// 使用位标记数组，比递归更节省内存
|
boolean[] keep = new boolean[points.size()];
|
keep[0] = keep[points.size() - 1] = true;
|
|
// 使用栈来模拟递归
|
LinkedList<int[]> stack = new LinkedList<>();
|
stack.push(new int[]{0, points.size() - 1});
|
|
while (!stack.isEmpty()) {
|
int[] range = stack.pop();
|
int start = range[0];
|
int end = range[1];
|
|
if (end - start < 2) {
|
continue;
|
}
|
|
double maxDistance = 0;
|
int maxIndex = start;
|
|
Point startPoint = points.get(start);
|
Point endPoint = points.get(end);
|
LineSegment segment = new LineSegment(startPoint, endPoint);
|
|
// 寻找离线段最远的点
|
for (int i = start + 1; i < end; i++) {
|
double distance = segment.perpendicularDistance(points.get(i));
|
if (distance > maxDistance) {
|
maxDistance = distance;
|
maxIndex = i;
|
}
|
}
|
|
// 如果最远点距离大于容差，则处理两侧
|
if (maxDistance > epsilon) {
|
keep[maxIndex] = true;
|
if (maxIndex - start > 1) {
|
stack.push(new int[]{start, maxIndex});
|
}
|
if (end - maxIndex > 1) {
|
stack.push(new int[]{maxIndex, end});
|
}
|
}
|
}
|
|
// 收集保留的点
|
List<Point> result = new ArrayList<>();
|
for (int i = 0; i < points.size(); i++) {
|
if (keep[i]) {
|
result.add(points.get(i));
|
}
|
}
|
|
return result;
|
}
|
|
/**
|
* 确保端点被保留
|
*/
|
private void ensureEndpoints(List<Point> original, List<Point> simplified) {
|
if (original.isEmpty() || simplified.isEmpty()) return;
|
|
Point firstOriginal = original.get(0);
|
Point lastOriginal = original.get(original.size() - 1);
|
|
// 检查首点
|
if (!simplified.get(0).equals(firstOriginal)) {
|
simplified.add(0, firstOriginal);
|
}
|
|
// 检查尾点
|
Point lastSimplified = simplified.get(simplified.size() - 1);
|
if (!lastSimplified.equals(lastOriginal)) {
|
simplified.add(lastOriginal);
|
}
|
}
|
|
/**
|
* 将点列表转换为字符串
|
*/
|
private String pointsToString(List<Point> points, int precision) {
|
if (points.isEmpty()) {
|
return "";
|
}
|
|
return points.stream()
|
.map(p -> p.toString(precision))
|
.collect(Collectors.joining(";"));
|
}
|
|
/**
|
* 批处理优化方法
|
*/
|
public List<String> optimizePaths(List<String> pathStrings, OptimizationConfig config) {
|
return pathStrings.stream()
|
.map(path -> optimizePath(path, config))
|
.collect(Collectors.toList());
|
}
|
|
/**
|
* 性能统计信息
|
*/
|
public static class OptimizationStats {
|
public final int originalPoints;
|
public final int optimizedPoints;
|
public final double reductionPercentage;
|
public final long processingTimeMs;
|
|
public OptimizationStats(int original, int optimized, long timeMs) {
|
this.originalPoints = original;
|
this.optimizedPoints = optimized;
|
this.reductionPercentage = original > 0 ?
|
(1.0 - (double)optimized / original) * 100 : 0;
|
this.processingTimeMs = timeMs;
|
}
|
|
@Override
|
public String toString() {
|
return String.format("优化统计: %d -> %d 点 (减少 %.1f%%)，耗时 %dms",
|
originalPoints, optimizedPoints, reductionPercentage, processingTimeMs);
|
}
|
}
|
|
/**
|
* 带统计信息的优化方法
|
*/
|
public OptimizationResult optimizePathWithStats(String pathStr, OptimizationConfig config) {
|
long startTime = System.currentTimeMillis();
|
|
if (pathStr == null || pathStr.trim().isEmpty()) {
|
return new OptimizationResult("", new OptimizationStats(0, 0, 0));
|
}
|
|
List<Point> originalPoints = parsePoints(pathStr);
|
String optimizedPath = optimizePath(pathStr, config);
|
List<Point> optimizedPoints = parsePoints(optimizedPath);
|
|
long endTime = System.currentTimeMillis();
|
|
OptimizationStats stats = new OptimizationStats(
|
originalPoints.size(),
|
optimizedPoints.size(),
|
endTime - startTime
|
);
|
|
return new OptimizationResult(optimizedPath, stats);
|
}
|
|
/**
|
* 优化结果封装类
|
*/
|
public static class OptimizationResult {
|
public final String optimizedPath;
|
public final OptimizationStats stats;
|
|
public OptimizationResult(String path, OptimizationStats stats) {
|
this.optimizedPath = path;
|
this.stats = stats;
|
}
|
}
|
|
|
|
/**
|
* 生成测试路径
|
*/
|
private static String generateTestPath(int pointCount) {
|
StringBuilder sb = new StringBuilder();
|
for (int i = 0; i < pointCount; i++) {
|
sb.append(i).append(",").append(i % 10);
|
if (i < pointCount - 1) {
|
sb.append(";");
|
}
|
}
|
return sb.toString();
|
}
|
|
/**
|
* 性能测试
|
*/
|
private static void testPerformance(WangfanpathJisuan calculator, int iterations) {
|
String testPath = generateTestPath(1000);
|
|
long startTime = System.currentTimeMillis();
|
for (int i = 0; i < iterations; i++) {
|
calculator.optimizePath(testPath);
|
}
|
long endTime = System.currentTimeMillis();
|
|
System.out.printf("处理 %d 次，每次1000点，总耗时: %dms，平均每次: %.2fms\n",
|
iterations, endTime - startTime,
|
(double)(endTime - startTime) / iterations);
|
}
|
}
|
