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 b9109823f632b659bc1c3a1a1077765c1a7d1864 Author: Lei Rui <[email protected]> AuthorDate: Thu Dec 19 23:40:45 2024 +0800 add standard implementation --- .../groupby/LocalGroupByExecutorTri_Visval.java | 4 +- .../query/simpiece/{Visval.java => VisvalOld.java} | 24 ++- .../iotdb/db/query/simpiece/Visval_standard.java | 202 +++++++++++++++++++++ 3 files changed, 227 insertions(+), 3 deletions(-) diff --git a/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_Visval.java b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_Visval.java index 8cb330812a6..40793c6651b 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_Visval.java +++ b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_Visval.java @@ -32,7 +32,7 @@ import org.apache.iotdb.db.query.control.QueryResourceManager; import org.apache.iotdb.db.query.filter.TsFileFilter; import org.apache.iotdb.db.query.reader.series.SeriesReader; import org.apache.iotdb.db.query.simpiece.TimeSeriesReader; -import org.apache.iotdb.db.query.simpiece.Visval; +import org.apache.iotdb.db.query.simpiece.VisvalOld; import org.apache.iotdb.db.query.simpiece.VisvalPoint; import org.apache.iotdb.tsfile.file.metadata.enums.TSDataType; import org.apache.iotdb.tsfile.file.metadata.statistics.MinMaxInfo; @@ -135,7 +135,7 @@ public class LocalGroupByExecutorTri_Visval implements GroupByExecutor { } // Visval - List<VisvalPoint> reducedPoints = Visval.reducePoints(points, m); + List<VisvalPoint> reducedPoints = VisvalOld.reducePoints(points, m); for (VisvalPoint p : reducedPoints) { series.append(p.y).append("[").append(p.x).append("]").append(","); diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/VisvalOld.java similarity index 70% rename from server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval.java rename to server/src/main/java/org/apache/iotdb/db/query/simpiece/VisvalOld.java index 62b3019edac..9f6e80897b0 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval.java +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/VisvalOld.java @@ -19,10 +19,12 @@ package org.apache.iotdb.db.query.simpiece; +import java.util.ArrayList; import java.util.List; +import java.util.Random; import java.util.concurrent.ConcurrentSkipListMap; -public class Visval { +public class VisvalOld { public static List<VisvalPoint> reducePoints(List<VisvalPoint> points, int targetCount) { if (points.size() <= targetCount) { @@ -39,6 +41,8 @@ public class Visval { } while (points.size() > targetCount) { + // 这里有个问题：points remove和heap不对齐，因为有可能heap里有多个点的area相同就一起被remove了，但是points里还没有remove + System.out.println(points.size()); VisvalPoint p = minHeap.pollFirstEntry().getValue(); if (p == null) { return points; @@ -67,4 +71,22 @@ public class Visval { private static double calculateArea(VisvalPoint a, VisvalPoint b, VisvalPoint c) { return Math.abs(a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2.0; } + + public static void main(String[] args) { + List<VisvalPoint> points = new ArrayList<>(); + // 添加点到列表 points 100万数据 + Random rand = new Random(); + int n = 10000; + int m = 1; + for (int i = 0; i < n; i++) { + points.add(new VisvalPoint(i, rand.nextInt(1000))); + } + // 计算运行时间 + long startTime = System.currentTimeMillis(); + List<VisvalPoint> reducedPoints = VisvalOld.reducePoints(points, m); + // 输出结果 + System.out.println(reducedPoints.size()); + long endTime = System.currentTimeMillis(); + System.out.println("Time taken to reduce points: " + (endTime - startTime) + "ms"); + } } diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval_standard.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval_standard.java new file mode 100644 index 00000000000..98fdb790057 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval_standard.java @@ -0,0 +1,202 @@ +package org.apache.iotdb.db.query.simpiece; + +import java.io.BufferedReader; +import java.io.FileReader; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.List; +import java.util.PriorityQueue; +import java.util.Random; + +// adapted from the open source C++ code https://github.com/ofZach/Visvalingam-Whyatt/blob/master/src/testApp.cpp +class Triangle { + + int[] indices = new int[3]; + double area; + Triangle prev; + Triangle next; + + public Triangle(int index1, int index2, int index3, double area) { + this.indices[0] = index1; + this.indices[1] = index2; + this.indices[2] = index3; + this.area = area; + } +} + +class vPoint { + + double x, y, z; + + public vPoint(double x, double y) { + this.x = x; + this.y = y; + this.z = Double.POSITIVE_INFINITY;// effective area + } +} + +class Polyline { + + private List<vPoint> vertices = new ArrayList<>(); + + public void addVertex(vPoint point) { + vertices.add(point); + } + + public List<vPoint> getVertices() { + return new ArrayList<>(vertices); + } + + public int size() { + return vertices.size(); + } + + public vPoint get(int index) { + return vertices.get(index); + } +} + +public class Visval_standard { + + // 计算三角形面积 + private static double triArea(vPoint d0, vPoint d1, vPoint d2) { + double dArea = ((d1.x - d0.x) * (d2.y - d0.y) - (d2.x - d0.x) * (d1.y - d0.y)) / 2.0; + return (double) ((dArea > 0.0) ? dArea : -dArea); // abs + } + + public static void buildEffectiveArea(Polyline lineToSimplify, List<vPoint> results) { + results.clear(); + results.addAll(lineToSimplify.getVertices()); + + int total = lineToSimplify.size(); + if (total < 3) { + return; // 不足 3 个点无法形成三角形 + } + + int nTriangles = total - 2; + Triangle[] triangles = new Triangle[nTriangles]; + + // 创建所有三角形并计算初始面积 + for (int i = 1; i < total - 1; i++) { + int index1 = i - 1, index2 = i, index3 = i + 1; + double area = triArea(lineToSimplify.get(index1), lineToSimplify.get(index2), + lineToSimplify.get(index3)); + triangles[i - 1] = new Triangle(index1, index2, index3, area); + } + + // 设置三角形的前后关系 + for (int i = 0; i < nTriangles; i++) { + triangles[i].prev = (i == 0 ? null : triangles[i - 1]); + triangles[i].next = (i == nTriangles - 1 ? null : triangles[i + 1]); + } + + // 使用优先队列构建 minHeap + PriorityQueue<Triangle> triangleHeap = new PriorityQueue<>( + Comparator.comparingDouble(t -> t.area)); + Collections.addAll(triangleHeap, triangles); + + double previousEA = -1; + while (!triangleHeap.isEmpty()) { + // 注意peek只需要直接访问该位置的元素，不涉及任何重排或堆化操作 + // 而poll是删除堆顶元素，需要重新堆化以维护堆的性质，复杂度是O(logk),k是当前堆的大小 + Triangle tri = triangleHeap.poll(); + + // 更新当前点的重要性（z 轴存储effective area,这是一个单调增的指标） + if (tri.area > previousEA) { + previousEA = tri.area; + } + results.get(tri.indices[1]).z = previousEA; +// System.out.println(tri.indices[1] + "," + previousEA); + + // 更新相邻三角形 + if (tri.prev != null) { + // 前一个三角形连到后一个三角形 + tri.prev.next = tri.next; + tri.prev.indices[2] = tri.indices[2]; + tri.prev.area = triArea( + lineToSimplify.get(tri.prev.indices[0]), + lineToSimplify.get(tri.prev.indices[1]), + lineToSimplify.get(tri.prev.indices[2]) + ); + + // 重新加入堆 + // 在 Java 的 PriorityQueue 中，修改元素的属性不会自动更新堆的顺序 + // 所以必须通过 remove 和 add 来显式重新插入修改后的元素 + triangleHeap.remove(tri.prev); + triangleHeap.add(tri.prev); + } + + if (tri.next != null) { + // 后一个三角形连到前一个三角形 + tri.next.prev = tri.prev; + tri.next.indices[0] = tri.indices[0]; + tri.next.area = triArea( + lineToSimplify.get(tri.next.indices[0]), + lineToSimplify.get(tri.next.indices[1]), + lineToSimplify.get(tri.next.indices[2]) + ); + + // 重新加入堆 + triangleHeap.remove(tri.next); + triangleHeap.add(tri.next); + } + } + } + + public static void main(String[] args) { + Polyline polyline = new Polyline(); +// polyline.addVertex(new ofPoint(0, 0)); +// polyline.addVertex(new ofPoint(1, 0)); +// polyline.addVertex(new ofPoint(1, 1)); +// polyline.addVertex(new ofPoint(0, 1)); + + Random rand = new Random(); + int n = 10000; + for (int i = 0; i < n; i++) { + polyline.addVertex(new vPoint(i, rand.nextInt(1000))); + } + +// float[] vlist = new float[]{11346, 33839, 35469, 23108, 22812, 5519, 5526, 4865, 5842, 23089}; +// for (int i = 0; i < vlist.length; i++) { +// polyline.addVertex(new vPoint(i, vlist[i])); +// } + +// ArrayList<Double> v = new ArrayList<>(); +// String filePath = "D://desktop//数据集//New York Stock Exchange//merged_prices.csv"; +// try (BufferedReader br = new BufferedReader(new FileReader(filePath))) { +// String line; +// int count = 0; +// while ((line = br.readLine()) != null && count < 1000) { +// String[] columns = line.split(","); // 假设 CSV 文件以逗号分隔 +// v.add(Double.parseDouble(columns[0])); // 读取第一列数据 +// count++; +// } +// } catch (Exception e) { +// e.printStackTrace(); +// } +// // 打印数据长度 +// System.out.println("Data length: " + v.size()); +// for (int i = 0; i < v.size(); i++) { +// polyline.addVertex(new vPoint(i, v.get(i))); +// } + + List<vPoint> results = new ArrayList<>(); + + // 计算运行时间 + long startTime = System.currentTimeMillis(); + + buildEffectiveArea(polyline, results); + + // 输出结果 + long endTime = System.currentTimeMillis(); + System.out.println("Time taken to reduce points: " + (endTime - startTime) + "ms"); + System.out.println(results.size()); + +// for (int i = 0; i < results.size(); i++) { +// vPoint point = results.get(i); +// System.out.println("Point: (" + point.x + ", " + point.y + ", " + point.z + ")"); +// } + } +} +
