This is an automated email from the ASF dual-hosted git repository. leirui pushed a commit to branch research/area-visualization in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit 364f0d8d0b6f2780e69203b5a5240be3bc3b337b Author: Lei Rui <[email protected]> AuthorDate: Mon Jan 27 21:53:44 2025 +0800 dp --- server/pom.xml | 10 +- server/sample_eBUG-jar-with-dependencies.jar | Bin 38715994 -> 38716020 bytes .../java/org/apache/iotdb/db/query/eBUG/DP.java | 286 +++++++++ .../java/org/apache/iotdb/db/query/eBUG/Tool.java | 712 +++++++++++---------- .../java/org/apache/iotdb/db/query/eBUG/eBUG.java | 44 +- 5 files changed, 694 insertions(+), 358 deletions(-) diff --git a/server/pom.xml b/server/pom.xml index 66ccebdb43a..b0b6be3c539 100644 --- a/server/pom.xml +++ b/server/pom.xml @@ -281,13 +281,13 @@ <plugin> <artifactId>maven-assembly-plugin</artifactId> <configuration> - <finalName>sample_fsw</finalName> - <!-- <finalName>sample_eBUG</finalName>--> - <!-- <finalName>sample_BUL2</finalName>--> + <!-- <finalName>sample_fsw</finalName>--> + <finalName>sample_eBUG</finalName> + <!-- <finalName>sample_BUL2</finalName>--> <archive> <manifest> - <mainClass>org.apache.iotdb.db.query.eBUG.sample_FSW</mainClass> - <!-- <mainClass>org.apache.iotdb.db.query.eBUG.sample_eBUG</mainClass>--> + <!-- <mainClass>org.apache.iotdb.db.query.eBUG.sample_FSW</mainClass>--> + <mainClass>org.apache.iotdb.db.query.eBUG.sample_eBUG</mainClass> <!-- <mainClass>org.apache.iotdb.db.query.eBUG.sample_bottomUpL2</mainClass>--> </manifest> </archive> diff --git a/server/sample_eBUG-jar-with-dependencies.jar b/server/sample_eBUG-jar-with-dependencies.jar index a37acfd0590..0df972fa4a5 100644 Binary files a/server/sample_eBUG-jar-with-dependencies.jar and b/server/sample_eBUG-jar-with-dependencies.jar differ diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/DP.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/DP.java new file mode 100644 index 00000000000..a6a9647fb4b --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/DP.java @@ -0,0 +1,286 @@ +package org.apache.iotdb.db.query.eBUG; + +import java.io.FileWriter; +import java.io.IOException; +import java.util.*; + +// Some public references about dynamic programming: +// https://justinwillmert.com/articles/2014/bellman-k-segmentation-algorithm/ +// https://github.com/CrivelliLab/Protein-Structure-DL + +public class DP { // Dynamic-Programming + + // Enum to represent error types + public enum ERROR { + L1, L2, L_infy, area + } + + // precomputing error measures of all possible segments, e.g., ad2 table + public static double[][] prepareCostTable(List<Point> points, ERROR errorType, boolean debug) { + int N = points.size(); + double[][] dists = new double[N][N]; // 默认0，对角线元素已经都是0了 + + // 外层循环i：range长度=right boundary-left boundary + // 内层循环j: 矩阵逐行 + for (int i = 1; i < N; i++) { // TODO + for (int j = 0; j < N - i; j++) { + // j = left boundary, r = right boundary, 左闭右闭 + int r = i + j; // r<N + if (debug) { + System.out.println(">>>> i=" + i + ", j=" + j + ", r=" + r); + } + + // lx=j,rx=r, 从lx=j到rx=r（左闭右闭）的linear interpolation（即连接lx和rx点）的errorType类型的误差 + double mc = joint_segment_error(points, j, r, errorType); + dists[j][r] = mc; + if (debug) { + System.out.println("dists="); + Tool.printArray(dists); + System.out.println("---------------------"); + } + } + } + return dists; + } + + // 注意k是分段数，不是采点数 + public static List<Point> dynamic_programming(List<Point> points, int k, ERROR errorType, boolean debug) { + int N = points.size(); + + // 预计算dists（即ad2 table），dists[i][j]代表对子序列i:j左闭右闭直接连接pi和pj的近似误差 + double[][] dists = prepareCostTable(points, errorType, debug); + if (debug) { + Tool.printArray(dists); + System.out.println("----------------------------------"); + } + + // 创建dp table。kSegDist[i][j]代表把子序列T[0:j]左闭右闭分成i段(java从0开始计数)的最小误差 + double[][] kSegDist = new double[k][N]; + // Initialize the case k=1 directly from the pre-computed distances + // 注意java从0开始，所以是0 index第一行代表分段数1 + System.arraycopy(dists[0], 0, kSegDist[0], 0, kSegDist[0].length); + if (debug) { + System.out.println("k_seg_dist="); + Tool.printArray(kSegDist); + } + + // 创建path table。记录子问题的解。kSegPath[i][j]代表把T[0:j]分成i段这个问题的最优子问题的位置 + // 子问题是把T[0:kSegPath[i][j]]分成i-1段，以及最后一段T[kSegPath[i][j]:end] + int[][] kSegPath = new int[k][N]; + // 第一行只分一段，所以不管终点是哪个（列），左边的闭合起点都是0 + // 虽然java数组默认初始是0，但是这里还是显式赋值 + Arrays.fill(kSegPath[0], 0); + if (debug) { + System.out.println("k_seg_path="); + Tool.printArray(kSegPath); + } + + // 外层循环i：分段数，注意python从0开始，所以实际含义是2~k个分段数 + for (int i = 1; i < k; i++) { + // 内层循环j：从第一个点开始到j终点（闭合）的序列 + // 所以含义是：找到从第一个点开始到j终点（闭合）的序列的分成(i+1)段的最佳分段方案（误差最小） + for (int j = 0; j < N; j++) { + // 动态规划 + // 注意linear interpolation不需要单点成为一个分段的情况 + // TODO 误差类型 + // TODO ghost修复 + // 从0:j的序列分成i段的问题：遍历所有可能的子问题组合解 + if (debug) { + System.out.println(">>>分段数i+1" + (i + 1) + ",end pos j=" + j); + } + double[] choices = new double[j + 1]; // java从0开始 + for (int xtmp = 0; xtmp < j + 1; xtmp++) { + if (errorType == ERROR.L_infy) { + choices[xtmp] = Math.max(kSegDist[i - 1][xtmp], dists[xtmp][j]); + } else { + choices[xtmp] = kSegDist[i - 1][xtmp] + dists[xtmp][j]; + } + } + if (debug) { + for (int xtmp = 0; xtmp < j + 1; xtmp++) { // 遍历从 0 到 j 的每个元素 + if (errorType == ERROR.L_infy) { + System.out.printf(" max((k_seg_dist[%d, %d] = %f), (dists[%d, %d] = %f)) --> %f%n", + i - 1, xtmp, kSegDist[i - 1][xtmp], + xtmp, j, dists[xtmp][j], + Math.max(kSegDist[i - 1][xtmp], dists[xtmp][j])); + } else { + System.out.printf(" (k_seg_dist[%d, %d] = %f) + (dists[%d, %d] = %f) --> %f%n", + i - 1, xtmp, kSegDist[i - 1][xtmp], + xtmp, j, dists[xtmp][j], + kSegDist[i - 1][xtmp] + dists[xtmp][j]); + } + } + } + + int bestIndex = getIndexOfMin(choices); + double bestVal = choices[bestIndex]; + + // Store the sub-problem solution + kSegPath[i][j] = bestIndex; + + kSegDist[i][j] = bestVal; + + if (debug) { + System.out.println("kSegDist[" + i + "][" + j + "] = " + bestVal); + System.out.println("kSegDist="); + Tool.printArray(kSegDist); + System.out.println("kSegPath="); + Tool.printArray(kSegPath); + } + } + } + + // 开始回溯构建采样结果 + List<Point> sDs = new ArrayList<>(); // k+1个采样点 + List<Integer> sDs_idx = new ArrayList<>(); + int rhs = N - 1; + sDs.add(points.get(rhs)); // 全局尾点 + sDs_idx.add(rhs); + + for (int i = k - 1; i >= 0; i--) { + int lhs = kSegPath[i][rhs]; + sDs.add(points.get(lhs)); + sDs_idx.add(lhs); + rhs = lhs; + } + + // 反转列表 + Collections.reverse(sDs); + Collections.reverse(sDs_idx); + + if (debug) { + System.out.println(sDs); + System.out.println(">>>>>ad2[][]="); + Tool.printArray(dists); + System.out.println(">>>>>dp[][]="); + Tool.printTransposeArray(kSegDist); + System.out.println(">>>>>path[][]="); + Tool.printTransposeArray(kSegPath); + System.out.println(error(points, sDs_idx, errorType)); + } + + return sDs; + } + + // Helper method to get index of minimum value + private static int getIndexOfMin(double[] array) { + double minVal = array[0]; + int minIndex = 0; + for (int i = 1; i < array.length; i++) { + if (array[i] < minVal) { + minVal = array[i]; + minIndex = i; + } + } + return minIndex; + } + + // Method to calculate joint segment error based on error type + private static double joint_segment_error(List<Point> points, int lx, int rx, ERROR errorType) { + // 默认joint=true, residual=true，即使用linear interpolation近似分段 + // lx~rx 左闭右闭 + if (errorType != ERROR.area) { + double x1 = points.get(lx).x; + double y1 = points.get(lx).y; + double x2 = points.get(rx).x; + double y2 = points.get(rx).y; + + // linear interpolation: + double k = (y2 - y1) / (x2 - x1); + double b = (y1 * x2 - y2 * x1) / (x2 - x1); + + double tmp = 0; + if (errorType == ERROR.L2) { + for (int i = lx; i <= rx; i++) { + double e = (k * points.get(i).x + b - points.get(i).y) * (k * points.get(i).x + b - points.get(i).y); + tmp += e; + } + } else if (errorType == ERROR.L1) { + for (int i = lx; i <= rx; i++) { + double e = Math.abs(k * points.get(i).x + b - points.get(i).y); + tmp += e; + } + } else if (errorType == ERROR.L_infy) { + for (int i = lx; i <= rx; i++) { + double e = Math.abs(k * points.get(i).x + b - points.get(i).y); // 注意绝对值 + if (e > tmp) { + tmp = e; + } + } + } + return tmp; + } else { // AD + List<Point> linearInterpolation = new ArrayList<>(); + linearInterpolation.add(points.get(lx)); + linearInterpolation.add(points.get(rx)); + return Tool.total_areal_displacement(points.subList(lx, rx + 1), // 注意lx,rx左闭右闭 + linearInterpolation, false); + } + } + + public static double error(List<Point> points, List<Integer> sampledIdx, ERROR errorType) { + double res = 0; + for (int i = 0; i < sampledIdx.size() - 1; i++) { + int lx = sampledIdx.get(i); + int rx = sampledIdx.get(i + 1); + double e = joint_segment_error(points, lx, rx, errorType); + if (errorType == ERROR.L_infy) { + res = Math.max(res, e); + } else { + res += e; + } + } + return res; + } + + // Example usage + public static void main(String[] args) { + Random rand = new Random(10); + String input = "D:\\LabSync\\iotdb\\我的Gitbook基地\\RUI Lei gitbook\\士论\\49. visval改进\\notebook\\raw.csv"; + boolean hasHeader = true; + int timeIdx = 0; + int valueIdx = 1; + int N = -1; + List<Point> points = Tool.readFromFile(input, hasHeader, timeIdx, valueIdx, N); +// Polyline polyline = new Polyline(); +// for (int i = 0; i < N; i += 1) { +// double v = rand.nextInt(1000); +// polyline.addVertex(new Point(i, v)); +// } +// List<Point> points = polyline.getVertices(); + try (FileWriter writer = new FileWriter("raw.csv")) { + // 写入CSV头部 + writer.append("x,y,z\n"); + + // 写入每个点的数据 + for (Point point : points) { + writer.append(point.x + "," + point.y + "," + point.z + "\n"); + } + System.out.println(points.size() + " Data has been written"); + } catch (IOException e) { + System.out.println("Error writing to CSV file: " + e.getMessage()); + } + + long startTime = System.currentTimeMillis(); +// double[][] ad2 = prepareKSegments(points, ERROR.L1, false); + int m = 4; + List<Point> sampled = dynamic_programming(points, m - 1, ERROR.area, false); + long endTime = System.currentTimeMillis(); + System.out.println("Time taken: " + (endTime - startTime) + "ms"); + + for (Point p : sampled) { + System.out.println(p); + } + System.out.println(sampled.size()); + +// try (PrintWriter writer = new PrintWriter(new File("output.csv"))) { +// // 写入字符串 +// for (int i = 0; i < sampled.size(); i++) { +// writer.println(sampled.get(i).x + "," + sampled.get(i).y); +// } +// +// } catch (FileNotFoundException e) { +// e.printStackTrace(); +// } + } +} diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Tool.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Tool.java index a61f091198a..9a54f835ec3 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Tool.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Tool.java @@ -11,363 +11,407 @@ import java.util.List; import java.util.stream.Stream; public class Tool { - // Assumed interface for the simplification function - interface SimplifyFunction { - List<Point> reducePoints(List<Point> points, double epsilon, Object... kwargs) - throws IOException; - } - - // Method to generate the output file name based on input path - public static String generateOutputFileName( - String inputFilePath, String outDir, String customize) { - // Get the file name without extension - Path path = Paths.get(inputFilePath); - String fileNameWithoutExtension = path.getFileName().toString(); - String name = fileNameWithoutExtension.substring(0, fileNameWithoutExtension.lastIndexOf('.')); - - // Get the file extension - String extension = - path.getFileName().toString().substring(fileNameWithoutExtension.lastIndexOf('.')); - - // Create output file path by appending '-ds' before the extension - // String outputFile = name + "-ds-e" + e + extension; - String outputFile = name + customize + extension; - - if (outDir == null) { // 表示使用input文件所在的文件夹 - // Handle path compatibility for different operating systems (Linux/Windows) - return path.getParent().resolve(outputFile).toString(); - } else { - Path out = Paths.get(outDir); - return out.resolve(outputFile).toString(); - } - } - - public static double getParam( - List<Point> points, - int m, - SimplifyFunction simplifyFunc, - double tolerantPts, - Object... kwargs) - throws IOException { - // double x = 1; 不要从1开始，因为对于swab来说使用如此小的maxError会很慢，宁可让maxError从大到小 - double x = 10; - boolean directLess = false; - boolean directMore = false; - - int iterNum = 0; - int maxIterNum = 50; - - // First binary search loop to find the initial range - double base = 2; - while (true) { - // System.out.println("x=" + x); - iterNum++; - if (iterNum > maxIterNum) { - // System.out.println("reach maxIterNum1"); - break; // Avoid infinite loops for special cases - } - List<Point> res = simplifyFunc.reducePoints(points, x, kwargs); - int length = res.size(); - // System.out.println(length); - - if (Math.abs(length - m) <= tolerantPts) { - return x; // Return the found parameter - } - - if (length > m) { - if (directMore) { - break; // Reach the first more - } - if (!directLess) { - directLess = true; + + public static void printArray(double[][] array) { + // 遍历每一行 + for (double[] row : array) { + for (double value : row) { + // 格式化输出：%10.2f 表示右对齐，占10个字符，保留2位小数 + System.out.printf("%10.2f ", value); + } + System.out.println(); // 换行 } + } - x *= base; // Need less points, increase x - } else { - if (directLess) { - break; // Reach the first less + public static void printTransposeArray(double[][] array) { + // 遍历每一列 + for (int i = 0; i < array[0].length; i++) { + for (int j = 0; j < array.length; j++) { + // 格式化输出：%10.2f 表示右对齐，占10个字符，保留2位小数 + System.out.printf("%10.2f ", array[j][i]); + } + System.out.println(); // 换行 } - if (!directMore) { - directMore = true; + } + + public static void printArray(int[][] array) { + // 遍历每一行 + for (int[] row : array) { + for (int value : row) { + System.out.printf("%10d ", value); + } + System.out.println(); // 换行 } + } - x /= base; // Need more points, decrease x - } + public static void printTransposeArray(int[][] array) { + // 遍历每一列 + for (int i = 0; i < array[0].length; i++) { + for (int j = 0; j < array.length; j++) { + // 格式化输出：%10.2f 表示右对齐，占10个字符，保留2位小数 + System.out.printf("%10d ", array[j][i]); + } + System.out.println(); // 换行 + } } - // Determine the initial left and right bounds - double left = (directLess) ? x / base : x; - double right = (directMore) ? x * base : x; - - // Refine the range with binary search - iterNum = 0; - while (true) { - iterNum++; - if (iterNum > maxIterNum) { - // System.out.println("reach maxIterNum"); - break; // Avoid infinite loops - } - - double mid = (left + right) / 2; - - List<Point> res = simplifyFunc.reducePoints(points, mid, kwargs); - int length = res.size(); - // System.out.println(length); - - if (Math.abs(length - m) <= tolerantPts) { - return mid; // Return the refined parameter - } - - if (length > m) { - left = mid; // Need less, narrow range to the left - } else { - right = mid; // Need more, narrow range to the right - } - // System.out.println(left + "," + right); + // Assumed interface for the simplification function + interface SimplifyFunction { + List<Point> reducePoints(List<Point> points, double epsilon, Object... kwargs) + throws IOException; } - return (left + right) / 2; // Return the average of left and right as the final parameter - } - - public static List<Point> readFromFile( - String input, boolean hasHeader, int timeIdx, int valueIdx, int N) { - List<Point> res = new ArrayList<>(); - - // Using Files.lines() for memory-efficient line-by-line reading - try (Stream<String> lines = Files.lines(Paths.get(input))) { - Iterator<String> iterator = lines.iterator(); - int lineNumber = 0; - - // Skip the header line if necessary - if (hasHeader && iterator.hasNext()) { - iterator.next(); // Skip the header - } - - // Process each line - while (iterator.hasNext()) { - lineNumber++; - String line = iterator.next(); - String[] columns = line.split(","); - - if (columns.length > Math.max(timeIdx, valueIdx)) { - double time; - if (timeIdx < 0) { - time = lineNumber; - } else { - time = Double.parseDouble(columns[timeIdx]); - } - double value = Double.parseDouble(columns[valueIdx]); - res.add(new Point(time, value)); - // System.out.println("Line " + lineNumber + " - Time: " + time + ", - // Value: " + value); + // Method to generate the output file name based on input path + public static String generateOutputFileName( + String inputFilePath, String outDir, String customize) { + // Get the file name without extension + Path path = Paths.get(inputFilePath); + String fileNameWithoutExtension = path.getFileName().toString(); + String name = fileNameWithoutExtension.substring(0, fileNameWithoutExtension.lastIndexOf('.')); + + // Get the file extension + String extension = + path.getFileName().toString().substring(fileNameWithoutExtension.lastIndexOf('.')); + + // Create output file path by appending '-ds' before the extension + // String outputFile = name + "-ds-e" + e + extension; + String outputFile = name + customize + extension; + + if (outDir == null) { // 表示使用input文件所在的文件夹 + // Handle path compatibility for different operating systems (Linux/Windows) + return path.getParent().resolve(outputFile).toString(); } else { - System.out.println("Line " + lineNumber + " is malformed (not enough columns)."); + Path out = Paths.get(outDir); + return out.resolve(outputFile).toString(); + } + } + + public static double getParam( + List<Point> points, + int m, + SimplifyFunction simplifyFunc, + double tolerantPts, + Object... kwargs) + throws IOException { + // double x = 1; 不要从1开始，因为对于swab来说使用如此小的maxError会很慢，宁可让maxError从大到小 + double x = 10; + boolean directLess = false; + boolean directMore = false; + + int iterNum = 0; + int maxIterNum = 50; + + // First binary search loop to find the initial range + double base = 2; + while (true) { + // System.out.println("x=" + x); + iterNum++; + if (iterNum > maxIterNum) { + // System.out.println("reach maxIterNum1"); + break; // Avoid infinite loops for special cases + } + List<Point> res = simplifyFunc.reducePoints(points, x, kwargs); + int length = res.size(); + // System.out.println(length); + + if (Math.abs(length - m) <= tolerantPts) { + return x; // Return the found parameter + } + + if (length > m) { + if (directMore) { + break; // Reach the first more + } + if (!directLess) { + directLess = true; + } + + x *= base; // Need less points, increase x + } else { + if (directLess) { + break; // Reach the first less + } + if (!directMore) { + directMore = true; + } + + x /= base; // Need more points, decrease x + } } - if (N > 0 && lineNumber >= N) { - // N>0控制点数，否则N<=0表示读全部数据 - break; + + // Determine the initial left and right bounds + double left = (directLess) ? x / base : x; + double right = (directMore) ? x * base : x; + + // Refine the range with binary search + iterNum = 0; + while (true) { + iterNum++; + if (iterNum > maxIterNum) { + // System.out.println("reach maxIterNum"); + break; // Avoid infinite loops + } + + double mid = (left + right) / 2; + + List<Point> res = simplifyFunc.reducePoints(points, mid, kwargs); + int length = res.size(); + // System.out.println(length); + + if (Math.abs(length - m) <= tolerantPts) { + return mid; // Return the refined parameter + } + + if (length > m) { + left = mid; // Need less, narrow range to the left + } else { + right = mid; // Need more, narrow range to the right + } + // System.out.println(left + "," + right); } - } - } catch (IOException e) { - e.printStackTrace(); + + return (left + right) / 2; // Return the average of left and right as the final parameter } - return res; - } - - // 计算三角形面积 - public static double triArea(Point d0, Point d1, Point d2) { - double dArea = ((d1.x - d0.x) * (d2.y - d0.y) - (d2.x - d0.x) * (d1.y - d0.y)) / 2.0; - return (dArea > 0.0) ? dArea : -dArea; // abs - } - - // 计算简单多边形（边不交叉）的面积（鞋带公式） - public static double calculatePolygonArea(List<Point> points) { - // points多边形顶点，要求按照逆时针或者顺时针的顺序枚举，否则鞋带公式无法给出正确结果 - int n = points.size(); - double area = 0; - for (int i = 0; i < n; i++) { - int next = (i + 1) % n; - area += points.get(i).x * points.get(next).y - points.get(next).x * points.get(i).y; + + public static List<Point> readFromFile( + String input, boolean hasHeader, int timeIdx, int valueIdx, int N) { + List<Point> res = new ArrayList<>(); + + // Using Files.lines() for memory-efficient line-by-line reading + try (Stream<String> lines = Files.lines(Paths.get(input))) { + Iterator<String> iterator = lines.iterator(); + int lineNumber = 0; + + // Skip the header line if necessary + if (hasHeader && iterator.hasNext()) { + iterator.next(); // Skip the header + } + + // Process each line + while (iterator.hasNext()) { + lineNumber++; + String line = iterator.next(); + String[] columns = line.split(","); + + if (columns.length > Math.max(timeIdx, valueIdx)) { + double time; + if (timeIdx < 0) { + time = lineNumber; + } else { + time = Double.parseDouble(columns[timeIdx]); + } + double value = Double.parseDouble(columns[valueIdx]); + res.add(new Point(time, value)); + // System.out.println("Line " + lineNumber + " - Time: " + time + ", + // Value: " + value); + } else { + System.out.println("Line " + lineNumber + " is malformed (not enough columns)."); + } + if (N > 0 && lineNumber >= N) { + // N>0控制点数，否则N<=0表示读全部数据 + break; + } + } + } catch (IOException e) { + e.printStackTrace(); + } + return res; } - return Math.abs(area) / 2.0; - } - - // 计算两个向量的叉积 - public static double crossProduct(double x1, double y1, double x2, double y2) { - // >0: (x2,y2)在(x1,y1)的逆时针方向 - // <0: (x2,y2)在(x1,y1)的顺时针方向 - // =0: 平行或共线 - return x1 * y2 - y1 * x2; - } - - // 判断两条线段是否相交并计算交点 - // L1包含一个线段的两个端点，L2包含另一个线段的两个端点 - public static Object[] lineIntersection(Point[] L1, Point[] L2) { - double x1 = L1[0].x, y1 = L1[0].y, x2 = L1[1].x, y2 = L1[1].y; - double x3 = L2[0].x, y3 = L2[0].y, x4 = L2[1].x, y4 = L2[1].y; - - // 判断是否相交（叉积） - double d1 = crossProduct(x2 - x1, y2 - y1, x3 - x1, y3 - y1); - double d2 = crossProduct(x2 - x1, y2 - y1, x4 - x1, y4 - y1); - double d3 = crossProduct(x4 - x3, y4 - y3, x1 - x3, y1 - y3); - double d4 = crossProduct(x4 - x3, y4 - y3, x2 - x3, y2 - y3); - - // 如果叉积条件满足，表示有交点 - // d1*d2<0意味着P3、P4分别在L12的两边 - // d3*d4<0意味着P1、P2分别在L34的两边 - // 两个同时满足说明有交点 - if (d1 * d2 < 0 && d3 * d4 < 0) { - double denominator = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1); // 不可能为0（平行或共线），因为已经判断相交了 - double t1 = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denominator; - double x = x1 + t1 * (x2 - x1); - double y = y1 + t1 * (y2 - y1); - return new Object[] {true, new Point(x, y)}; + + // 计算三角形面积 + public static double triArea(Point d0, Point d1, Point d2) { + double dArea = ((d1.x - d0.x) * (d2.y - d0.y) - (d2.x - d0.x) * (d1.y - d0.y)) / 2.0; + return (dArea > 0.0) ? dArea : -dArea; // abs } - // 检查是否起点或终点重合 - if ((x1 == x3 && y1 == y3) || (x1 == x4 && y1 == y4)) { - return new Object[] {true, new Point(x1, y1)}; + // 计算简单多边形（边不交叉）的面积（鞋带公式） + public static double calculatePolygonArea(List<Point> points) { + // points多边形顶点，要求按照逆时针或者顺时针的顺序枚举，否则鞋带公式无法给出正确结果 + int n = points.size(); + double area = 0; + for (int i = 0; i < n; i++) { + int next = (i + 1) % n; + area += points.get(i).x * points.get(next).y - points.get(next).x * points.get(i).y; + } + return Math.abs(area) / 2.0; } - if ((x2 == x3 && y2 == y3) || (x2 == x4 && y2 == y4)) { - return new Object[] {true, new Point(x2, y2)}; + + // 计算两个向量的叉积 + public static double crossProduct(double x1, double y1, double x2, double y2) { + // >0: (x2,y2)在(x1,y1)的逆时针方向 + // <0: (x2,y2)在(x1,y1)的顺时针方向 + // =0: 平行或共线 + return x1 * y2 - y1 * x2; } - return new Object[] {false, null}; - } - - // 计算总的多边形面积（通过时间序列扫描交点），默认要求点按照时间戳严格递增排列 - public static double total_areal_displacement( - List<Point> points, List<Point> points2, boolean debug) { - double totalArea = 0; - int i = 0, j = 0; // i for points, j for points2 - Point prevIntersection = null; - int prevI = -1, prevJ = -1; - - // List<double[]> intersectionCoords = new ArrayList<>(); - List<Double> areaList = new ArrayList<>(); - - while (i < points.size() - 1 && j < points2.size() - 1) { - if (debug) { - System.out.println("--------- " + i + " " + j + " ------------"); - } - - // 当前线段 - Point[] L1 = {points.get(i), points.get(i + 1)}; - Point[] L2 = {points2.get(j), points2.get(j + 1)}; - - // 判断是否有交点 - Object[] result = lineIntersection(L1, L2); - boolean isIntersect = (boolean) result[0]; - Point intersection = (Point) result[1]; - - if (isIntersect) { - // intersectionCoords.add(intersection); - - if (prevIntersection != null) { - // 构造多边形点集 - List<Point> polygon = new ArrayList<>(); // 按照顺时针/逆时针几何连接顺序枚举多边形的顶点 - polygon.add(prevIntersection); - if (debug) { - System.out.println("- start intersection: " + prevIntersection); - } - polygon.addAll(points.subList(prevI, i + 1)); // 添加当前线段的点，左闭右开 - // polygon.addAll(Arrays.asList(Arrays.copyOfRange(points, prevI, i + - // 1))); // 添加当前线段的点，左闭右开 - if (debug) { - System.out.println("- one side: " + points.subList(prevI, i + 1)); - } - polygon.add(intersection); - if (debug) { - System.out.println("- end intersection: " + intersection); - } - List<Point> tempPoints2 = points2.subList(prevJ, j + 1); - Collections.reverse(tempPoints2); // 添加另一序列的点 - polygon.addAll(tempPoints2); - if (debug) { - System.out.println("- another side: " + tempPoints2); - } - - // double[][] polygonArray = new double[polygon.size()][2]; - // for (int k = 0; k < polygon.size(); k++) { - // polygonArray[k] = polygon.get(k); - // } - - // 计算多边形面积，注意polygon里的点一定是按照顺时针/逆时针几何连接顺序枚举的多边形顶点 - double area = calculatePolygonArea(polygon); - if (debug) { - System.out.println("Area = " + area); - } - totalArea += area; - areaList.add(area); + // 判断两条线段是否相交并计算交点 + // L1包含一个线段的两个端点，L2包含另一个线段的两个端点 + public static Object[] lineIntersection(Point[] L1, Point[] L2) { + double x1 = L1[0].x, y1 = L1[0].y, x2 = L1[1].x, y2 = L1[1].y; + double x3 = L2[0].x, y3 = L2[0].y, x4 = L2[1].x, y4 = L2[1].y; + + // 判断是否相交（叉积） + double d1 = crossProduct(x2 - x1, y2 - y1, x3 - x1, y3 - y1); + double d2 = crossProduct(x2 - x1, y2 - y1, x4 - x1, y4 - y1); + double d3 = crossProduct(x4 - x3, y4 - y3, x1 - x3, y1 - y3); + double d4 = crossProduct(x4 - x3, y4 - y3, x2 - x3, y2 - y3); + + // 如果叉积条件满足，表示有交点 + // d1*d2<0意味着P3、P4分别在L12的两边 + // d3*d4<0意味着P1、P2分别在L34的两边 + // 两个同时满足说明有交点 + if (d1 * d2 < 0 && d3 * d4 < 0) { + double denominator = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1); // 不可能为0（平行或共线），因为已经判断相交了 + double t1 = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denominator; + double x = x1 + t1 * (x2 - x1); + double y = y1 + t1 * (y2 - y1); + return new Object[]{true, new Point(x, y)}; } - prevIntersection = intersection; - prevI = i + 1; - prevJ = j + 1; + // 检查是否起点或终点重合 + if ((x1 == x3 && y1 == y3) || (x1 == x4 && y1 == y4)) { + return new Object[]{true, new Point(x1, y1)}; + } + if ((x2 == x3 && y2 == y3) || (x2 == x4 && y2 == y4)) { + return new Object[]{true, new Point(x2, y2)}; + } + + return new Object[]{false, null}; + } + + // 计算总的多边形面积（通过时间序列扫描交点），默认要求点按照时间戳严格递增排列 + public static double total_areal_displacement( + List<Point> points, List<Point> points2, boolean debug) { + double totalArea = 0; + int i = 0, j = 0; // i for points, j for points2 + Point prevIntersection = null; + int prevI = -1, prevJ = -1; + + // List<double[]> intersectionCoords = new ArrayList<>(); + List<Double> areaList = new ArrayList<>(); + + while (i < points.size() - 1 && j < points2.size() - 1) { + if (debug) { + System.out.println("--------- " + i + " " + j + " ------------"); + } + + // 当前线段 + Point[] L1 = {points.get(i), points.get(i + 1)}; + Point[] L2 = {points2.get(j), points2.get(j + 1)}; + + // 判断是否有交点 + Object[] result = lineIntersection(L1, L2); + boolean isIntersect = (boolean) result[0]; + Point intersection = (Point) result[1]; + + if (isIntersect) { + // intersectionCoords.add(intersection); + + if (prevIntersection != null) { + // 构造多边形点集 + List<Point> polygon = new ArrayList<>(); // 按照顺时针/逆时针几何连接顺序枚举多边形的顶点 + polygon.add(prevIntersection); + if (debug) { + System.out.println("- start intersection: " + prevIntersection); + } + polygon.addAll(points.subList(prevI, i + 1)); // 添加当前线段的点，左闭右开 + // polygon.addAll(Arrays.asList(Arrays.copyOfRange(points, prevI, i + + // 1))); // 添加当前线段的点，左闭右开 + if (debug) { + System.out.println("- one side: " + points.subList(prevI, i + 1)); + } + polygon.add(intersection); + if (debug) { + System.out.println("- end intersection: " + intersection); + } + List<Point> tempPoints2 = points2.subList(prevJ, j + 1); + Collections.reverse(tempPoints2); // 添加另一序列的点 + polygon.addAll(tempPoints2); + if (debug) { + System.out.println("- another side: " + tempPoints2); + } + + // double[][] polygonArray = new double[polygon.size()][2]; + // for (int k = 0; k < polygon.size(); k++) { + // polygonArray[k] = polygon.get(k); + // } + + // 计算多边形面积，注意polygon里的点一定是按照顺时针/逆时针几何连接顺序枚举的多边形顶点 + double area = calculatePolygonArea(polygon); + if (debug) { + System.out.println("Area = " + area); + } + totalArea += area; + areaList.add(area); + } + + prevIntersection = intersection; + prevI = i + 1; + prevJ = j + 1; + if (debug) { + System.out.println( + "This intersection = " + + intersection + + ", next polygon: side1 = " + + prevI + + ", side2 = " + + prevJ); + } + } + + int currentI = i; // 临时存储i + int currentJ = j; // 临时存储j + if (points.get(currentI + 1).x <= points2.get(currentJ + 1).x) { + i += 1; // 基于时间戳严格递增的假设，Line不会回头或者垂直 + } + if (points.get(currentI + 1).x >= points2.get(currentJ + 1).x) { + j += 1; // 基于时间戳严格递增的假设，Line不会回头或者垂直 + } + } // end of while + if (debug) { - System.out.println( - "This intersection = " - + intersection - + ", next polygon: side1 = " - + prevI - + ", side2 = " - + prevJ); + System.out.println(areaList); } - } - - int currentI = i; // 临时存储i - int currentJ = j; // 临时存储j - if (points.get(currentI + 1).x <= points2.get(currentJ + 1).x) { - i += 1; // 基于时间戳严格递增的假设，Line不会回头或者垂直 - } - if (points.get(currentI + 1).x >= points2.get(currentJ + 1).x) { - j += 1; // 基于时间戳严格递增的假设，Line不会回头或者垂直 - } - } // end of while - - if (debug) { - System.out.println(areaList); + + return totalArea; } - return totalArea; - } - - // 测试方法 - public static void main(String[] args) { - // 示例数据 - List<Point> points = new ArrayList<>(); - points.add(new Point(0, 0)); - points.add(new Point(1, 2)); - points.add(new Point(2, -20)); - points.add(new Point(3, 0)); - points.add(new Point(4, -1)); - points.add(new Point(5, -1.5)); - points.add(new Point(6, 0)); - - List<Point> points2 = new ArrayList<>(); - // points2.add(points.get(0)); - // points2.add(points.get(3)); - // points2.add(points.get(6)); - points2.add(new Point(1, -10)); - points2.add(new Point(3, 0)); - - double area = total_areal_displacement(points, points2, true); - System.out.println("Total area: " + area); - - // points = new ArrayList<>(); - // points.add(new Point(0, 0)); - // points.add(new Point(1, 2)); - // points.add(new Point(1.5, -10)); - // double area = calculatePolygonArea(points); - // System.out.println(area); - // - // Point[] L1 = new Point[2]; - // L1[0] = new Point(1, 2); - // L1[1] = new Point(2, -2); - // Point[] L2 = new Point[2]; - // L2[0] = new Point(0, 0); - // L2[1] = new Point(3, 0); - // Object[] res = lineIntersection(L1, L2); - // System.out.println(res[1]); - } + // 测试方法 + public static void main(String[] args) { + // 示例数据 + List<Point> points = new ArrayList<>(); + points.add(new Point(0, 0)); + points.add(new Point(1, 2)); + points.add(new Point(2, -20)); + points.add(new Point(3, 0)); + points.add(new Point(4, -1)); + points.add(new Point(5, -1.5)); + points.add(new Point(6, 0)); + + List<Point> points2 = new ArrayList<>(); + // points2.add(points.get(0)); + // points2.add(points.get(3)); + // points2.add(points.get(6)); + points2.add(new Point(1, -10)); + points2.add(new Point(3, 0)); + + double area = total_areal_displacement(points, points2, true); + System.out.println("Total area: " + area); + + // points = new ArrayList<>(); + // points.add(new Point(0, 0)); + // points.add(new Point(1, 2)); + // points.add(new Point(1.5, -10)); + // double area = calculatePolygonArea(points); + // System.out.println(area); + // + // Point[] L1 = new Point[2]; + // L1[0] = new Point(1, 2); + // L1[1] = new Point(2, -2); + // Point[] L2 = new Point[2]; + // L2[0] = new Point(0, 0); + // L2[1] = new Point(3, 0); + // Object[] res = lineIntersection(L1, L2); + // System.out.println(res[1]); + } } diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java index 8da7cca5175..44fc3298d96 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java @@ -76,16 +76,18 @@ public class eBUG { throw new IllegalArgumentException("Parameter e must be non-negative."); } - if (m > 2) { - System.out.println( - "online sampling mode, " - + "returning " - + m - + " sampled points sorted by time in ascending order"); - } else { - System.out.println( - "offline precomputation mode, " - + "returning each point sorted by dominated significance (DS) in ascending order"); + if (debug) { + if (m > 2) { + System.out.println( + "online sampling mode, " + + "returning " + + m + + " sampled points sorted by time in ascending order"); + } else { + System.out.println( + "offline precomputation mode, " + + "returning each point sorted by dominated significance (DS) in ascending order"); + } } // List<Point> results = lineToSimplify.getVertices(); // 浅复制 @@ -177,14 +179,16 @@ public class eBUG { } // 更新当前点的重要性（z 轴存储effective area,这是一个单调增的指标） - if (tri.area > previousEA) { - previousEA = tri.area; - } - // results.get(tri.indices[1]).z = previousEA; // dominated significance - points.get(tri.indices[1]).z = previousEA; // dominated significance - resultsBottomUpEliminated.add(points.get(tri.indices[1])); // TODO add的是Point引用，所以没有多用一倍的空间 - if (debug) { - System.out.println(Arrays.toString(tri.indices) + ", Dominated Sig=" + previousEA); + if (m <= 2) { // precomputation mode + if (tri.area > previousEA) { + previousEA = tri.area; + } + // results.get(tri.indices[1]).z = previousEA; // dominated significance + points.get(tri.indices[1]).z = previousEA; // dominated significance + resultsBottomUpEliminated.add(points.get(tri.indices[1])); // TODO add的是Point引用，所以没有多用一倍的空间 + if (debug) { + System.out.println(Arrays.toString(tri.indices) + ", Dominated Sig=" + previousEA); + } } // 更新相邻三角形 @@ -326,6 +330,8 @@ public class eBUG { if (m > 2) { // online sampling mode // 把滞后的淘汰点施加上去，然后返回在线采样结果（也就是返回剩余未被淘汰的点） + // 注意未淘汰的点的Dominated significance尚未赋值，还都是infinity + // 不过既然m>2在线采样模式，所以其实淘汰点的DS本身也没有记录 for (Point p : laggedEliminatedPoints) { p.markEliminated(); if (debug) { @@ -337,7 +343,7 @@ public class eBUG { Point end = points.get(points.size() - 1); while (start != end) { // Point类里增加prev&next指针，这样T'_max{0,k-e}里点的连接关系就有了，这样从Pa开始沿着指针，遍历点数一定不超过e+3 - onlineSampled.add(start); // 注意未淘汰的点的Dominated significance尚未赋值，还都是infinity + onlineSampled.add(start); start = start.next; // when e=0, only traversing three points pa pi pb } onlineSampled.add(end);
