| ¶Ô±ÈÐÂÎļþ |
| | |
| | | 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); |
| | | } |
| | | } |