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 6857dc2e13d65bbe6b074cc49593c85a1d057eb2 Author: Lei Rui <[email protected]> AuthorDate: Tue Jan 21 17:16:58 2025 +0800 add ad --- .../java/org/apache/iotdb/db/query/eBUG/Point.java | 17 ++ .../org/apache/iotdb/db/query/eBUG/Polyline.java | 25 ++ .../java/org/apache/iotdb/db/query/eBUG/Tool.java | 198 +++++++++++++++ .../org/apache/iotdb/db/query/eBUG/Triangle.java | 49 ++++ .../query/{simpiece => eBUG}/Visval_standard.java | 174 ++++--------- .../Visval_standard.java => eBUG/eBUG.java} | 282 ++++++++++----------- 6 files changed, 480 insertions(+), 265 deletions(-) diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Point.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Point.java new file mode 100644 index 00000000000..77ebdb4cb39 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Point.java @@ -0,0 +1,17 @@ +package org.apache.iotdb.db.query.eBUG; + +public class Point { + + double x, y, z; + + public Point(double x, double y) { + this.x = x; + this.y = y; + this.z = Double.POSITIVE_INFINITY; // effective area + } + + @Override + public String toString() { + return "Point: (" + x + ", " + y + ", " + z + ")"; + } +} diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Polyline.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Polyline.java new file mode 100644 index 00000000000..b6e2f231c14 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Polyline.java @@ -0,0 +1,25 @@ +package org.apache.iotdb.db.query.eBUG; + +import java.util.ArrayList; +import java.util.List; + +public class Polyline { + + private List<Point> vertices = new ArrayList<>(); + + public void addVertex(Point point) { + vertices.add(point); + } + + public List<Point> getVertices() { + return new ArrayList<>(vertices); + } + + public int size() { + return vertices.size(); + } + + public Point get(int index) { + return vertices.get(index); + } +} 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 new file mode 100644 index 00000000000..48c1544e76b --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Tool.java @@ -0,0 +1,198 @@ +package org.apache.iotdb.db.query.eBUG; + + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +public class Tool { + // 计算三角形面积 + 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; + } + 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)}; + } + + // 检查是否起点或终点重合 + 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); +// } + + // 计算多边形面积 + 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(areaList); + } + + 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(points.get(5)); + + 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/Triangle.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Triangle.java new file mode 100644 index 00000000000..79f7d440c99 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Triangle.java @@ -0,0 +1,49 @@ +package org.apache.iotdb.db.query.eBUG; + +// adapted from the open source C++ code +// https://github.com/ofZach/Visvalingam-Whyatt/blob/master/src/testApp.cpp +public class Triangle { + + int[] indices = new int[3]; + double area; + Triangle prev; + Triangle next; + boolean isDeleted; + + 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; + this.isDeleted = false; // flag for removal. Avoid using heap.remove(x) as it is O(n) complexity + } + + public Triangle(Triangle oldTri) { + // deep copy and inherit connection + + this.indices[0] = oldTri.indices[0]; + this.indices[1] = oldTri.indices[1]; + this.indices[2] = oldTri.indices[2]; + this.area = oldTri.area; + this.prev = oldTri.prev; + this.next = oldTri.next; + + // TODO important! inherit connection relationship to this new point + if (this.prev != null) { // previous point to this new point + this.prev.next = this; + } + if (this.next != null) { // next point to this new point + this.next.prev = this; + } + + this.isDeleted = false; // this new triangle is not deleted + } + + public boolean isValid() { + return !isDeleted; + } + + public void markDeleted() { + this.isDeleted = true; + } +} 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/eBUG/Visval_standard.java similarity index 72% copy from server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval_standard.java copy to server/src/main/java/org/apache/iotdb/db/query/eBUG/Visval_standard.java index 4edf126b531..a85332d3846 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval_standard.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Visval_standard.java @@ -17,102 +17,18 @@ * under the License. */ -package org.apache.iotdb.db.query.simpiece; +package org.apache.iotdb.db.query.eBUG; import java.io.FileWriter; import java.io.IOException; import java.util.*; import java.util.stream.Collectors; -// 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; - boolean isDeleted; - - 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; - this.isDeleted = false; // flag for removal. Avoid using heap.remove(x) as it is O(n) complexity - } - - public Triangle(Triangle oldTri) { - // deep copy and inherit connection - - this.indices[0] = oldTri.indices[0]; - this.indices[1] = oldTri.indices[1]; - this.indices[2] = oldTri.indices[2]; - this.area = oldTri.area; - this.prev = oldTri.prev; - this.next = oldTri.next; - - // TODO important! inherit connection relationship to this new point - if (this.prev != null) { // previous point to this new point - this.prev.next = this; - } - if (this.next != null) { // next point to this new point - this.next.prev = this; - } - - this.isDeleted = false; // this new triangle is not deleted - } - - public boolean isValid() { - return !isDeleted; - } - - public void markDeleted() { - this.isDeleted = true; - } -} - -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); - } -} +import static org.apache.iotdb.db.query.eBUG.Tool.triArea; 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) { + public static void buildEffectiveArea(Polyline lineToSimplify, List<Point> results) { results.clear(); results.addAll(lineToSimplify.getVertices()); // TODO debug @@ -216,37 +132,37 @@ public class Visval_standard { Polyline polyline = new Polyline(); List<Polyline> polylineList = new ArrayList<>(); Random rand = new Random(1); - int n = 100_0000; + int n = 10_0000; - int p = 1000; + int p = 700; for (int i = 0; i < n; i += p) { Polyline polylineBatch = new Polyline(); for (int j = i; j < Math.min(i + p, n); j++) { double v = rand.nextInt(1000000); - polyline.addVertex(new vPoint(j, v)); + polyline.addVertex(new Point(j, v)); - polylineBatch.addVertex(new vPoint(j, v)); + polylineBatch.addVertex(new Point(j, v)); } polylineList.add(polylineBatch); } -// try (FileWriter writer = new FileWriter("raw.csv")) { -// // 写入CSV头部 -// writer.append("x,y,z\n"); -// -// // 写入每个点的数据 -// for (int i = 0; i < polyline.size(); i++) { -// vPoint point = polyline.get(i); -// writer.append(point.x + "," + point.y + "," + point.z + "\n"); -// } -// System.out.println("Data has been written"); -// } catch (IOException e) { -// System.out.println("Error writing to CSV file: " + e.getMessage()); -// } + try (FileWriter writer = new FileWriter("raw.csv")) { + // 写入CSV头部 + writer.append("x,y,z\n"); + + // 写入每个点的数据 + for (int i = 0; i < polyline.size(); i++) { + Point point = polyline.get(i); + writer.append(point.x + "," + point.y + "," + point.z + "\n"); + } + System.out.println("Data has been written"); + } catch (IOException e) { + System.out.println("Error writing to CSV file: " + e.getMessage()); + } System.out.println("---------------------------------"); - List<vPoint> results = new ArrayList<>(); + List<Point> results = new ArrayList<>(); // 计算运行时间 long startTime = System.currentTimeMillis(); buildEffectiveArea(polyline, results); @@ -258,32 +174,32 @@ public class Visval_standard { if (results.size() <= 100) { System.out.println("+++++++++++++++++++"); for (int i = 0; i < results.size(); i++) { - vPoint point = results.get(i); + Point point = results.get(i); System.out.println("Point: (" + point.x + ", " + point.y + ", " + point.z + ")"); } } -// try (FileWriter writer = new FileWriter("fast.csv")) { -// // 写入CSV头部 -// writer.append("x,y,z\n"); -// -// // 写入每个点的数据 -// for (int i = 0; i < results.size(); i++) { -// vPoint point = results.get(i); -// writer.append(point.x + "," + point.y + "," + point.z + "\n"); -// } -// System.out.println("Data has been written"); -// } catch (IOException e) { -// System.out.println("Error writing to CSV file: " + e.getMessage()); -// } + try (FileWriter writer = new FileWriter("fast.csv")) { + // 写入CSV头部 + writer.append("x,y,z\n"); + + // 写入每个点的数据 + for (int i = 0; i < results.size(); i++) { + Point point = results.get(i); + writer.append(point.x + "," + point.y + "," + point.z + "\n"); + } + System.out.println("Data has been written"); + } catch (IOException e) { + System.out.println("Error writing to CSV file: " + e.getMessage()); + } System.out.println("---------------------------------"); - List<List<vPoint>> resultsBatchList = new ArrayList<>(); + List<List<Point>> resultsBatchList = new ArrayList<>(); // 计算运行时间 int cnt = 0; startTime = System.currentTimeMillis(); for (Polyline polylineBatch : polylineList) { - List<vPoint> resultsBatch = new ArrayList<>(); + List<Point> resultsBatch = new ArrayList<>(); buildEffectiveArea(polylineBatch, resultsBatch); cnt += resultsBatch.size(); resultsBatchList.add(resultsBatch); @@ -295,7 +211,7 @@ public class Visval_standard { System.out.println("---------------------------------"); // 使用 Stream API 合并所有列表 - List<vPoint> mergedList = + List<Point> mergedList = resultsBatchList.stream().flatMap(List::stream).collect(Collectors.toList()); int sameCnt = 0; for (int i = 0; i < mergedList.size(); i++) { @@ -304,6 +220,20 @@ public class Visval_standard { } } System.out.println("sameCnt=" + sameCnt + ", percent=" + sameCnt * 1.0 / mergedList.size()); + + try (FileWriter writer = new FileWriter("batch.csv")) { + // 写入CSV头部 + writer.append("x,y,z\n"); + + // 写入每个点的数据 + for (int i = 0; i < mergedList.size(); i++) { + Point point = mergedList.get(i); + writer.append(point.x + "," + point.y + "," + point.z + "\n"); + } + System.out.println("Data has been written"); + } catch (IOException e) { + System.out.println("Error writing to CSV file: " + e.getMessage()); + } } // float[] vlist = new float[]{11346, 33839, 35469, 23108, 22812, 5519, 5526, 4865, 5842, 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/eBUG/eBUG.java similarity index 57% rename from server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval_standard.java rename to server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java index 4edf126b531..cc512cbcc9c 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval_standard.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java @@ -17,105 +17,50 @@ * under the License. */ -package org.apache.iotdb.db.query.simpiece; +package org.apache.iotdb.db.query.eBUG; import java.io.FileWriter; import java.io.IOException; import java.util.*; -import java.util.stream.Collectors; - -// 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; - boolean isDeleted; - - 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; - this.isDeleted = false; // flag for removal. Avoid using heap.remove(x) as it is O(n) complexity - } - - public Triangle(Triangle oldTri) { - // deep copy and inherit connection - - this.indices[0] = oldTri.indices[0]; - this.indices[1] = oldTri.indices[1]; - this.indices[2] = oldTri.indices[2]; - this.area = oldTri.area; - this.prev = oldTri.prev; - this.next = oldTri.next; - // TODO important! inherit connection relationship to this new point - if (this.prev != null) { // previous point to this new point - this.prev.next = this; - } - if (this.next != null) { // next point to this new point - this.next.prev = this; +import static org.apache.iotdb.db.query.eBUG.Tool.triArea; + + +public class eBUG { + public static List<Point> findEliminated(Polyline lineToSimplify, int[] recentEliminated, + Point pa, Point pi, Point pb) { + // TODO 寻找最近淘汰的e个点，并且是位于pa~pb之间的 + // 性质：最近淘汰的那一个点一定是位于pa~pb之间，因为正是这个点的淘汰才使得pi的significance要更新！ + // pi: point need significance updating + // pa: left adjacent non-eliminated point + // pb: right adjacent non-eliminated point + // return a list of points, containing pa,p,pb and points between pa&pa from the e most recently eliminated points, + // order by time in ascending order + List<Point> res = new ArrayList<>(); + for (int idx : recentEliminated) { // e points + if (idx == 0) { // init, not filled by real eliminated points yet + break; + } + Point p = lineToSimplify.get(idx); + if (p.x > pa.x && p.x < pb.x) { + res.add(p); + } } - - this.isDeleted = false; // this new triangle is not deleted + res.add(pa); + res.add(pi); + res.add(pb); + res.sort(Comparator.comparingDouble(p -> p.x)); // 按时间戳排序 TODO 这样的话时间复杂度要变成e*log(e)了吧？ + return res; } - public boolean isValid() { - return !isDeleted; - } - - public void markDeleted() { - this.isDeleted = true; - } -} - -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) { + public static void buildEffectiveArea(Polyline lineToSimplify, List<Point> results, int e) { results.clear(); results.addAll(lineToSimplify.getVertices()); // TODO debug + // TODO 需要一个东西来记录最近淘汰的点依次是谁 + int[] recentEliminated = new int[e]; // init 0 points to the first point, skipped in findEliminated + int recentEliminatedIdx = 0; // index in the array, circulate + int total = lineToSimplify.size(); if (total < 3) { return; // 不足 3 个点无法形成三角形 @@ -153,6 +98,16 @@ public class Visval_standard { continue; } + // 真正的淘汰点 + //TODO 记录最近淘汰的点，注意不要重复记录也就是在上面执行之后再确认淘汰 +// popOrder.add(tri.indices[1]); + System.out.println("eliminate " + lineToSimplify.get(tri.indices[1])); + if (e > 0) { + recentEliminated[recentEliminatedIdx] = tri.indices[1]; + recentEliminatedIdx = (recentEliminatedIdx + 1) % e; // 0~e-1 + } + System.out.println(Arrays.toString(recentEliminated)); + // 更新当前点的重要性（z 轴存储effective area,这是一个单调增的指标） if (tri.area > previousEA) { previousEA = tri.area; @@ -171,13 +126,26 @@ public class Visval_standard { tri.prev.markDeleted(); // O(1) 这个点标记为废掉，前后关联都砍断，但是不remove因为那太耗时，只要heap poll到它就跳过就可以 Triangle newPre = new Triangle(tri.prev); // deep copy and inherit connection -// tri.prev = newPre; // replace TODO can omit +// tri.prev = newPre; // replace TODO can omit, because already done by new Triangle(tri.prev) // 2. 处理pi被淘汰引起tri.prev被更新的事情 // 前一个三角形连到后一个三角形 tri.prev.next = tri.next; // ATTENTION!!!: 这里的tri.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])); + + // TODO e parameter + List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, + lineToSimplify.get(tri.prev.indices[0]), + lineToSimplify.get(tri.prev.indices[1]), + lineToSimplify.get(tri.prev.indices[2])); + System.out.println("for updating Point on the left " + lineToSimplify.get(tri.prev.indices[1])); + for (Point point : pointsForSig) { + System.out.println(point); + } + + tri.prev.area = triArea(lineToSimplify.get(tri.prev.indices[0]), + lineToSimplify.get(tri.prev.indices[1]), + lineToSimplify.get(tri.prev.indices[2])); // 重新加入堆 // 在 Java 的 PriorityQueue 中，修改元素的属性不会自动更新堆的顺序 @@ -193,7 +161,7 @@ public class Visval_standard { tri.next.markDeleted(); // O(1) 这个点标记为废掉，前后关联都砍断，但是不remove因为那太耗时，只有poll到它就跳过就可以 Triangle newNext = new Triangle(tri.next); // deep copy and inherit connection -// tri.next = newNext; // replace TODO can omit +// tri.next = newNext; // replace TODO can omit, because already done by new Triangle(tri.prev) if (tri.prev != null) { tri.prev.next = tri.next; // ATTENTION!!!: 这里的tri.next已经被换掉！所以之前的要重新赋值！ @@ -202,13 +170,27 @@ public class Visval_standard { // 2. 处理pi被淘汰引起tri.next被更新的事情 tri.next.prev = tri.prev; // 注意此时tri.prev已经是替代后的节点，tri.next也是，从而被标记为废点的前后关联真正砍断 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])); + + // TODO e parameter + List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, + lineToSimplify.get(tri.next.indices[0]), + lineToSimplify.get(tri.next.indices[1]), + lineToSimplify.get(tri.next.indices[2])); + System.out.println("for updating Point on the right " + lineToSimplify.get(tri.next.indices[1])); + for (Point point : pointsForSig) { + System.out.println(point); + } + + tri.next.area = triArea(lineToSimplify.get(tri.next.indices[0]), + lineToSimplify.get(tri.next.indices[1]), + lineToSimplify.get(tri.next.indices[2])); // 重新加入堆 // 在 Java 的 PriorityQueue 中，修改元素的属性不会自动更新堆的顺序 // 所以必须通过add 来显式重新插入修改后的元素 triangleHeap.add(tri.next); // 注意加入的是一个新的对象isDeleted=false } + System.out.println(">>>"); } } @@ -216,40 +198,41 @@ public class Visval_standard { Polyline polyline = new Polyline(); List<Polyline> polylineList = new ArrayList<>(); Random rand = new Random(1); - int n = 100_0000; + int n = 10; - int p = 1000; + int p = 10; for (int i = 0; i < n; i += p) { Polyline polylineBatch = new Polyline(); for (int j = i; j < Math.min(i + p, n); j++) { double v = rand.nextInt(1000000); - polyline.addVertex(new vPoint(j, v)); + polyline.addVertex(new Point(j, v)); - polylineBatch.addVertex(new vPoint(j, v)); + polylineBatch.addVertex(new Point(j, v)); } polylineList.add(polylineBatch); } -// try (FileWriter writer = new FileWriter("raw.csv")) { -// // 写入CSV头部 -// writer.append("x,y,z\n"); -// -// // 写入每个点的数据 -// for (int i = 0; i < polyline.size(); i++) { -// vPoint point = polyline.get(i); -// writer.append(point.x + "," + point.y + "," + point.z + "\n"); -// } -// System.out.println("Data has been written"); -// } catch (IOException e) { -// System.out.println("Error writing to CSV file: " + e.getMessage()); -// } + try (FileWriter writer = new FileWriter("raw.csv")) { + // 写入CSV头部 + writer.append("x,y,z\n"); + + // 写入每个点的数据 + for (int i = 0; i < polyline.size(); i++) { + Point point = polyline.get(i); + writer.append(point.x + "," + point.y + "," + point.z + "\n"); + } + System.out.println("Data has been written"); + } catch (IOException e) { + System.out.println("Error writing to CSV file: " + e.getMessage()); + } System.out.println("---------------------------------"); - List<vPoint> results = new ArrayList<>(); + List<Point> results = new ArrayList<>(); // 计算运行时间 + int eParam = 3; long startTime = System.currentTimeMillis(); - buildEffectiveArea(polyline, results); + buildEffectiveArea(polyline, results, eParam); // 输出结果 long endTime = System.currentTimeMillis(); System.out.println("Time taken to reduce points: " + (endTime - startTime) + "ms"); @@ -258,52 +241,65 @@ public class Visval_standard { if (results.size() <= 100) { System.out.println("+++++++++++++++++++"); for (int i = 0; i < results.size(); i++) { - vPoint point = results.get(i); + Point point = results.get(i); System.out.println("Point: (" + point.x + ", " + point.y + ", " + point.z + ")"); } } -// try (FileWriter writer = new FileWriter("fast.csv")) { + try (FileWriter writer = new FileWriter("fast.csv")) { + // 写入CSV头部 + writer.append("x,y,z\n"); + + // 写入每个点的数据 + for (int i = 0; i < results.size(); i++) { + Point point = results.get(i); + writer.append(point.x + "," + point.y + "," + point.z + "\n"); + } + System.out.println("Data has been written"); + } catch (IOException e) { + System.out.println("Error writing to CSV file: " + e.getMessage()); + } + +// System.out.println("---------------------------------"); +// List<List<Point>> resultsBatchList = new ArrayList<>(); +// // 计算运行时间 +// int cnt = 0; +// startTime = System.currentTimeMillis(); +// for (Polyline polylineBatch : polylineList) { +// List<Point> resultsBatch = new ArrayList<>(); +// buildEffectiveArea(polylineBatch, resultsBatch); +// cnt += resultsBatch.size(); +// resultsBatchList.add(resultsBatch); +// } +// // 输出结果 +// endTime = System.currentTimeMillis(); +// System.out.println("Time taken to reduce points: " + (endTime - startTime) + "ms"); +// System.out.println(cnt); +// +// System.out.println("---------------------------------"); +// // 使用 Stream API 合并所有列表 +// List<Point> mergedList = resultsBatchList.stream().flatMap(List::stream).collect(Collectors.toList()); +// int sameCnt = 0; +// for (int i = 0; i < mergedList.size(); i++) { +// if (mergedList.get(i).z == results.get(i).z) { +// sameCnt += 1; +// } +// } +// System.out.println("sameCnt=" + sameCnt + ", percent=" + sameCnt * 1.0 / mergedList.size()); +// +// try (FileWriter writer = new FileWriter("batch.csv")) { // // 写入CSV头部 // writer.append("x,y,z\n"); // // // 写入每个点的数据 -// for (int i = 0; i < results.size(); i++) { -// vPoint point = results.get(i); +// for (int i = 0; i < mergedList.size(); i++) { +// Point point = mergedList.get(i); // writer.append(point.x + "," + point.y + "," + point.z + "\n"); // } // System.out.println("Data has been written"); // } catch (IOException e) { // System.out.println("Error writing to CSV file: " + e.getMessage()); // } - - System.out.println("---------------------------------"); - List<List<vPoint>> resultsBatchList = new ArrayList<>(); - // 计算运行时间 - int cnt = 0; - startTime = System.currentTimeMillis(); - for (Polyline polylineBatch : polylineList) { - List<vPoint> resultsBatch = new ArrayList<>(); - buildEffectiveArea(polylineBatch, resultsBatch); - cnt += resultsBatch.size(); - resultsBatchList.add(resultsBatch); - } - // 输出结果 - endTime = System.currentTimeMillis(); - System.out.println("Time taken to reduce points: " + (endTime - startTime) + "ms"); - System.out.println(cnt); - - System.out.println("---------------------------------"); - // 使用 Stream API 合并所有列表 - List<vPoint> mergedList = - resultsBatchList.stream().flatMap(List::stream).collect(Collectors.toList()); - int sameCnt = 0; - for (int i = 0; i < mergedList.size(); i++) { - if (mergedList.get(i).z == results.get(i).z) { - sameCnt += 1; - } - } - System.out.println("sameCnt=" + sameCnt + ", percent=" + sameCnt * 1.0 / mergedList.size()); } // float[] vlist = new float[]{11346, 33839, 35469, 23108, 22812, 5519, 5526, 4865, 5842,
