You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iotdb.apache.org by le...@apache.org on 2025/02/23 17:44:20 UTC
(iotdb) 19/44: Add
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 98cdae627c79981b57c75de2eceec1913d99d1f9
Author: Lei Rui <10...@qq.com>
AuthorDate: Thu Jan 23 02:56:14 2025 +0800
Add
---
.../java/org/apache/iotdb/db/query/eBUG/Point.java | 20 ++
.../org/apache/iotdb/db/query/eBUG/Polyline.java | 4 +
.../java/org/apache/iotdb/db/query/eBUG/Test1.java | 6 +-
.../java/org/apache/iotdb/db/query/eBUG/eBUG.java | 175 +++++------
.../eBUG/eBUG_circulateArrayForEliminated.java | 325 +++++++++++++++++++++
5 files changed, 439 insertions(+), 91 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
index 77ebdb4cb39..70aa19ea531 100644
--- 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
@@ -4,10 +4,30 @@ public class Point {
double x, y, z;
+// public boolean eliminated; // 滞后e个淘汰点 for eBUG usage
+ public Point prev; // 指向T'_max{0,k-e}里当前点的前一个点 for eBUG usage
+ public Point next; // 指向T'_max{0,k-e}里当前点的后一个点 for eBUG usage
+ // 注意Triangle里的prev&next用于最新状态下存在三角形之间的连接关系，
+ // 而这里Point的prev&next用于滞后e个淘汰点（也就是最近的e个淘汰点先不施加）状态下的未淘汰点之间的连接关系
+
public Point(double x, double y) {
this.x = x;
this.y = y;
this.z = Double.POSITIVE_INFINITY; // effective area
+
+ // for eBUG usage
+// this.eliminated = false;
+ this.prev = null;
+ this.next = null;
+ }
+
+ public void markEliminated() {
+// eliminated = true;
+
+ // to avoid traversing each point between pa to pb,
+ // instead only traversing at most e most recently eliminated points lagged
+ prev.next = next;
+ next.prev = prev;
}
@Override
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
index bed14731832..1ddfe2ebbe1 100644
--- 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
@@ -8,6 +8,10 @@ public class Polyline {
private List<Point> vertices = new ArrayList<>();
public void addVertex(Point point) {
+// if (!vertices.isEmpty()) { //before adding this point
+// vertices.get(vertices.size() - 1).next = point;
+// point.prev = vertices.get(vertices.size() - 1);
+// }
vertices.add(point);
}
diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java
index 56e73cc17e0..28b0eebd53e 100644
--- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java
+++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java
@@ -43,11 +43,7 @@ public class Test1 {
}
System.out.println("---------------------------------");
-// List<Point> results = new ArrayList<>();
- // 计算运行时间
-// int eParam = 10;
-// for (int eParam = 0; eParam < 2 * n; eParam += 1000) {
- int eParam = 2;
+ int eParam = 1000000;
long startTime = System.currentTimeMillis();
List<Point> results = buildEffectiveArea(polyline, eParam, false);
// 输出结果
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 77e21a27067..906bc4e2366 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
@@ -29,56 +29,35 @@ import static org.apache.iotdb.db.query.eBUG.Tool.triArea;
public class eBUG {
- public static List<Point> findEliminated(Polyline lineToSimplify, int[] recentEliminated,
- int pa_idx, int pi_idx, int pb_idx) {
- // 复杂度分析 记c=b-a。
- // 如果e<c，那么从最近淘汰的e个点里寻找位于pa~pb之间的，找到的点和pa pi pb一起按照时间戳递增排序，后面鞋带公式计算面积：O(e+eloge)
- // 否则e>=c，直接取T[a:b]，已经排序号了，后面鞋带公式计算面积：O(c)
-
- // 性质：最近淘汰的那一个点一定是位于pa~pb之间，因为正是这个点的淘汰才使得pi的significance要更新！
-
- // pi: the point whose significance needs updating
+ public static List<Point> findEliminated(Polyline lineToSimplify, int pa_idx, int pb_idx) {
// pa: left adjacent non-eliminated point of pi
// pb: right adjacent non-eliminated point of pi
- // 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
+ // return a list of points, T'_max{0,k-e}[a:b] order by time in ascending order
- Point pa = lineToSimplify.get(pa_idx);
- Point pi = lineToSimplify.get(pi_idx);
- Point pb = lineToSimplify.get(pb_idx);
+ // 性质：最近淘汰的那一个点一定是位于pa~pb之间，因为正是这个点的淘汰才使得pi的significance要更新！至于其他全局更早淘汰的点则不一定位于a:b之间
+ // pa,xxx,pi,xxx,pb
+ // when e=0，遍历点数就是3
+ // when e>0，遍历点数大于等于4、小于等于e+3
List<Point> res = new ArrayList<>();
-
- // TODO note: here may happen because e=c=0 or just 0<c<=e
- if (recentEliminated.length >= (pb_idx - pa_idx - 2)) { // e >= the total number of eliminated points in this region
-// System.out.println("[c=(b-a-2)]<=e, use T directly"); // worst case下, k=c
- res = lineToSimplify.getVertices().subList(pa_idx, pb_idx + 1); // 左闭右开
- return res; // 已经按照时间戳递增
+ Point start = lineToSimplify.get(pa_idx);
+ Point end = lineToSimplify.get(pb_idx);
+// int cnt = 0;
+ while (start != end) { // Point类里增加prev&next指针，这样T'_max{0,k-e}里点的连接关系就有了，这样从Pa开始沿着指针，遍历点数一定不超过e+3
+ res.add(start);
+ start = start.next; // when e=0, only traversing three points pa pi pb
+// cnt += 1;
}
-
- // TODO note: here may happen because c>e=0 or c>e>0. the latter needs search among recentEliminated and sort by timestamp
- // 从最近淘汰的e个点里寻找位于pa~pb之间的点，找到的有可能小于e个点
-// System.out.println("k>=[c=(b-a-2)]>e, search among e");
- res.add(pa); // 注意pa pi pb已经按照时间戳递增
- res.add(pi);
- res.add(pb);
-
- // 包括了c>e=0的情况
- 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);
- }
- }
-
- // 按照时间戳递增排序，这是为了后面计算total areal displacement需要
- if (recentEliminated.length > 0) { // 否则e=0，不需要排序pa pi pb三个点
- res.sort(Comparator.comparingDouble(p -> p.x)); // 按时间戳排序 这样的话时间复杂度变成e*log(e)
- }
-
+ res.add(end);
+// cnt += 1;
+// System.out.println(cnt); // 3<=cnt<=e+3
+
+// for (int i = pa_idx; i <= pb_idx; i++) { // 左闭右闭
+// Point p = lineToSimplify.get(i);
+// if (!p.eliminated) {
+// res.add(p);
+// }
+// }
return res;
}
@@ -90,8 +69,12 @@ public class eBUG {
List<Point> results = lineToSimplify.getVertices(); // 浅复制
// 用循环数组来记录最近淘汰的点
- int[] recentEliminated = new int[e]; // init 0 points to the first point, skipped in findEliminated
- int recentEliminatedIdx = 0; // index in the array, circulate
+// int[] recentEliminated = new int[e]; // init 0 points to the first point, skipped in findEliminated
+// int recentEliminatedIdx = 0; // index in the array, circulate
+
+ // 存储的是点的引用，这样可以修改原来序列里点的淘汰状态
+ // 存储的是距离当前最新状态的滞后的尚未施加、待施加的e个淘汰点
+ LinkedList<Point> laggedEliminatedPoints = new LinkedList<>();
int total = lineToSimplify.size();
if (total < 3) {
@@ -102,10 +85,21 @@ public class eBUG {
Triangle[] triangles = new Triangle[nTriangles];
// 创建所有三角形并计算初始面积
+// lineToSimplify.get(0).eliminated = false; // 初始化点的状态 for eBUG usage
+ lineToSimplify.get(0).prev = null;
+ lineToSimplify.get(0).next = lineToSimplify.get(1);
+// lineToSimplify.get(total - 1).eliminated = false; // 初始化点的状态 for eBUG usage
+ lineToSimplify.get(total - 1).next = null;
+ lineToSimplify.get(total - 1).prev = lineToSimplify.get(total - 2);
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 eBUG usage
+// lineToSimplify.get(i).eliminated = false;
+ lineToSimplify.get(i).prev = lineToSimplify.get(i - 1);
+ lineToSimplify.get(i).next = lineToSimplify.get(i + 1);
}
// 设置三角形的前后关系
@@ -138,12 +132,18 @@ public class eBUG {
if (debug) {
System.out.println("(1) eliminate " + lineToSimplify.get(tri.indices[1]));
}
- if (e > 0) { // otherwise e=0
- recentEliminated[recentEliminatedIdx] = tri.indices[1];
- recentEliminatedIdx = (recentEliminatedIdx + 1) % e; // 0~e-1 circulate
+ if (e > 0) {
+ if (laggedEliminatedPoints.size() == e) {
+ // 已经有e个滞后淘汰点了，为了把最近淘汰点加入，得先把最老的淘汰点施加上去
+ Point removedPoint = laggedEliminatedPoints.removeFirst(); // 取出最早加入的淘汰点 复杂度1
+ removedPoint.markEliminated(); // 注意是引用，所以改的内容后面可以看到
+ }
+ laggedEliminatedPoints.addLast(lineToSimplify.get(tri.indices[1])); // 加入最新的淘汰点，滞后在这里先不施加
+ } else { // e=0 没有滞后 立即标记删除 T'_k
+ lineToSimplify.get(tri.indices[1]).markEliminated();
}
if (debug) {
- System.out.println("the e most recently eliminated points:" + Arrays.toString(recentEliminated));
+ System.out.println("the e most recently eliminated points (lagged):" + laggedEliminatedPoints);
}
// 更新当前点的重要性（z 轴存储effective area,这是一个单调增的指标）
@@ -172,12 +172,10 @@ public class eBUG {
tri.prev.indices[2] = tri.indices[2];
// e parameter
- List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated,
- tri.prev.indices[0],
- tri.prev.indices[1],
- tri.prev.indices[2]); // TODO complexity ?
+ List<Point> pointsForSig = findEliminated(lineToSimplify, tri.prev.indices[0], tri.prev.indices[2]);
if (debug) {
System.out.println("(2) update point on the left " + lineToSimplify.get(tri.prev.indices[1]));
+ System.out.println("3<=cnt<=e+3. cnt=" + pointsForSig.size());
for (Point point : pointsForSig) {
System.out.println("\t" + point);
}
@@ -221,12 +219,10 @@ public class eBUG {
tri.next.indices[0] = tri.indices[0];
// e parameter
- List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated,
- tri.next.indices[0],
- tri.next.indices[1],
- tri.next.indices[2]); // TODO complexity
+ List<Point> pointsForSig = findEliminated(lineToSimplify, tri.next.indices[0], tri.next.indices[2]);
if (debug) {
System.out.println("(2) updating point on the right " + lineToSimplify.get(tri.next.indices[1]));
+ System.out.println("3<=cnt<=e+3. cnt=" + pointsForSig.size());
for (Point point : pointsForSig) {
System.out.println("\t" + point);
}
@@ -259,45 +255,52 @@ public class eBUG {
public static void main(String[] args) {
- int eParam = 2000_0000;
- try (PrintWriter writer = new PrintWriter(new File("exp_varyN_e" + eParam + ".csv"))) {
- for (int n = 100_0000; n < 2000_0000; n += 200_0000) { // 超过两千万就都变得慢多了，感觉可能是内存有限的原因，而不是算法复杂度
- // TODO 注意 要有一个点是n=300w
-
- Polyline polyline = new Polyline();
- int seed = 1;
- Random rand = new Random(seed); // TODO 注意seed在每轮里重设
- for (int i = 0; i < n; i++) {
- double v = rand.nextInt(1000000);
- polyline.addVertex(new Point(i, v));
- }
+// int eParam = 0;
+ int[] eParamList = {0, 1, 2, 3, 4, 5, 10, 14, 15, 16, 20, 30, 40, 50, 100, 200, 500, 1000, 2000, 5000,
+ 10000, 50000, 10_0000, 50_0000, 100_0000, 200_0000, 300_0000,
+ 500_0000, 800_0000, 1000_0000,
+ 1500_0000, 2000_0000, 2500_0000, 3000_0000};
+ for (int eParam : eParamList) {
+ try (PrintWriter writer = new PrintWriter(new File("exp_varyN_e" + eParam + ".csv"))) {
+ for (int n = 100_0000; n < 2000_0000; n += 200_0000) { // 超过两千万就都变得慢多了，感觉可能是内存有限的原因，而不是算法复杂度
+ // TODO 注意 要有一个点是n=300w
+
+ Polyline polyline = new Polyline();
+ int seed = 1;
+ Random rand = new Random(seed); // TODO 注意seed在每轮里重设
+ for (int i = 0; i < n; i++) {
+ double v = rand.nextInt(1000000);
+ polyline.addVertex(new Point(i, v));
+ }
- long startTime = System.currentTimeMillis();
- List<Point> results = buildEffectiveArea(polyline, eParam, false);
- long endTime = System.currentTimeMillis();
+ long startTime = System.currentTimeMillis();
+ List<Point> results = buildEffectiveArea(polyline, eParam, false);
+ long endTime = System.currentTimeMillis();
- System.out.println("n=" + n + ", e=" + eParam + ", Time taken to reduce points: " + (endTime - startTime) + "ms");
- writer.println(n + "," + eParam + "," + (endTime - startTime));
- System.out.println(results.size());
+ System.out.println("n=" + n + ", e=" + eParam + ", Time taken to reduce points: " + (endTime - startTime) + "ms");
+ writer.println(n + "," + eParam + "," + (endTime - startTime));
+ System.out.println(results.size());
- // clear
- polyline.clear();
- results.clear();
- polyline = null;
- results = null;
- System.gc();
+// // clear
+// polyline.clear();
+// results.clear();
+// polyline = null;
+// results = null;
+// System.gc();
+ }
+ } catch (FileNotFoundException e) {
+ throw new RuntimeException(e);
}
- } catch (FileNotFoundException e) {
- throw new RuntimeException(e);
}
// int n = 300_0000;
+//
// int seed = 1;
// Random rand = new Random(seed); // TODO 注意seed在每轮里重设
// Polyline polyline = new Polyline(); // 注意：如果是固定n变化e实验，这个数据要一次性生成，不然每次随机不一样
// for (int i = 0; i < n; i++) {
// double v = rand.nextInt(1000000);
-// polyline.addVertex(new Point(i, v));
+// polyline.addVertex(new Point(i, v)); // point的状态会在buildEffectiveArea里重置的，所以在下面的e遍历里可以复用这一份数据
// }
//
// try (PrintWriter writer = new PrintWriter(new File("exp_varyE_n" + n + ".csv"))) {
@@ -314,7 +317,7 @@ public class eBUG {
// System.out.println(results.size());
//
// // clear 注意不能把原始数据清除，还要接着用
-// System.gc();
+//// System.gc();
// }
// } catch (FileNotFoundException e) {
// throw new RuntimeException(e);
diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_circulateArrayForEliminated.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_circulateArrayForEliminated.java
new file mode 100644
index 00000000000..38e9c96ad4e
--- /dev/null
+++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_circulateArrayForEliminated.java
@@ -0,0 +1,325 @@
+///*
+// * Licensed to the Apache Software Foundation (ASF) under one
+// * or more contributor license agreements. See the NOTICE file
+// * distributed with this work for additional information
+// * regarding copyright ownership. The ASF licenses this file
+// * to you under the Apache License, Version 2.0 (the
+// * "License"); you may not use this file except in compliance
+// * with the License. You may obtain a copy of the License at
+// *
+// * http://www.apache.org/licenses/LICENSE-2.0
+// *
+// * Unless required by applicable law or agreed to in writing,
+// * software distributed under the License is distributed on an
+// * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// * KIND, either express or implied. See the License for the
+// * specific language governing permissions and limitations
+// * under the License.
+// */
+//
+//package org.apache.iotdb.db.query.eBUG;
+//
+//import java.io.File;
+//import java.io.FileNotFoundException;
+//import java.io.PrintWriter;
+//import java.util.*;
+//
+//import static org.apache.iotdb.db.query.eBUG.Tool.total_areal_displacement;
+//import static org.apache.iotdb.db.query.eBUG.Tool.triArea;
+//
+//
+//public class eBUG_circulateArrayForEliminated {
+// public static List<Point> findEliminated(Polyline lineToSimplify, int[] recentEliminated,
+// int pa_idx, int pi_idx, int pb_idx) {
+// // 复杂度分析 记c=b-a。
+// // 如果e<c，那么从最近淘汰的e个点里寻找位于pa~pb之间的，找到的点和pa pi pb一起按照时间戳递增排序，后面鞋带公式计算面积：O(e+eloge)
+// // 否则e>=c，直接取T[a:b]，已经排序号了，后面鞋带公式计算面积：O(c)
+//
+// // 性质：最近淘汰的那一个点一定是位于pa~pb之间，因为正是这个点的淘汰才使得pi的significance要更新！
+//
+// // pi: the point whose significance needs updating
+// // pa: left adjacent non-eliminated point of pi
+// // pb: right adjacent non-eliminated point of pi
+// // 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
+//
+// Point pa = lineToSimplify.get(pa_idx);
+// Point pi = lineToSimplify.get(pi_idx);
+// Point pb = lineToSimplify.get(pb_idx);
+//
+// List<Point> res = new ArrayList<>();
+//
+// // TODO note: here may happen because e=c=0 or just 0<c<=e
+// if (recentEliminated.length >= (pb_idx - pa_idx - 2)) { // e >= the total number of eliminated points in this region
+//// System.out.println("[c=(b-a-2)]<=e, use T directly"); // worst case下, k=c
+// res = lineToSimplify.getVertices().subList(pa_idx, pb_idx + 1); // 左闭右开
+// return res; // 已经按照时间戳递增
+// }
+//
+// // TODO note: here may happen because c>e=0 or c>e>0. the latter needs search among recentEliminated and sort by timestamp
+// // 从最近淘汰的e个点里寻找位于pa~pb之间的点，找到的有可能小于e个点
+//// System.out.println("k>=[c=(b-a-2)]>e, search among e");
+// res.add(pa); // 注意pa pi pb已经按照时间戳递增
+// res.add(pi);
+// res.add(pb);
+//
+// // 包括了c>e=0的情况
+// 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);
+// }
+// }
+//
+// // 按照时间戳递增排序，这是为了后面计算total areal displacement需要
+// if (recentEliminated.length > 0) { // 否则e=0，不需要排序pa pi pb三个点
+// res.sort(Comparator.comparingDouble(p -> p.x)); // 按时间戳排序 这样的话时间复杂度变成e*log(e)
+// }
+//
+// return res;
+// }
+//
+// public static List<Point> buildEffectiveArea(Polyline lineToSimplify, int e, boolean debug) {
+// if (e < 0) {
+// throw new IllegalArgumentException("Parameter e must be non-negative.");
+// }
+//
+// List<Point> results = lineToSimplify.getVertices(); // 浅复制
+//
+// // 用循环数组来记录最近淘汰的点
+// 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 results; // 不足 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++) { // TODO 这个可以和上一个循环合并吗？？好像不可以
+// 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); // complexity TODO O(n) or O(nlogn)?
+//
+// double previousEA = -1;
+// while (!triangleHeap.isEmpty()) {
+// // 注意peek只需要直接访问该位置的元素，不涉及任何重排或堆化操作
+// // 而poll是删除堆顶元素，需要重新堆化以维护堆的性质，复杂度是O(logk),k是当前堆的大小
+// Triangle tri = triangleHeap.poll(); // O(logn)
+//
+// // 如果该三角形已经被删除，跳过. Avoid using heap.remove(x) as it is O(n) complexity
+// // 而且除了heap里，已经没有其他节点会和它关联了，所有的connections关系已经迁移到新的角色替代节点上
+// if (tri.isDeleted) {
+// if (debug) {
+// System.out.println(">>>bottom-up, remaining " + triangleHeap.size() + " triangles (including those marked for removal)");
+// }
+// continue;
+// }
+//
+// // 真正的淘汰点
+// // 记录最近淘汰的点，注意不要重复记录也就是在上面执行之后再确认淘汰
+// if (debug) {
+// System.out.println("(1) eliminate " + lineToSimplify.get(tri.indices[1]));
+// }
+// if (e > 0) { // otherwise e=0
+// recentEliminated[recentEliminatedIdx] = tri.indices[1];
+// recentEliminatedIdx = (recentEliminatedIdx + 1) % e; // 0~e-1 circulate
+// }
+// if (debug) {
+// System.out.println("the e most recently eliminated points:" + Arrays.toString(recentEliminated));
+// }
+//
+// // 更新当前点的重要性（z 轴存储effective area,这是一个单调增的指标）
+// if (tri.area > previousEA) {
+// previousEA = tri.area;
+// }
+// results.get(tri.indices[1]).z = previousEA; // dominated significance
+// if (debug) {
+// System.out.println(Arrays.toString(tri.indices) + ", Dominated Sig=" + previousEA);
+// }
+//
+// // 更新相邻三角形
+// if (tri.prev != null) {
+// // 标记为失效点，同时new一个新的对象接管它的一切数据和前后连接关系，然后更新前后连接关系、更新significance、加入heap使其排好序
+//
+// // 1. 处理旧的tri.prev被标记删除的事情（角色替代）
+// // triangleHeap.remove(tri.prev); // Avoid using heap.remove(x) as it is O(n) complexity!
+// tri.prev.markDeleted(); // O(1) 这个点标记为废掉，前后关联都砍断，但是不remove因为那太耗时，只要heap poll到它就跳过就可以
+//
+// Triangle newPre = new Triangle(tri.prev); // deep copy and inherit connection
+// // tri.prev = newPre; // 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];
+//
+// // e parameter
+// List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated,
+// tri.prev.indices[0],
+// tri.prev.indices[1],
+// tri.prev.indices[2]); // TODO complexity ?
+// if (debug) {
+// System.out.println("(2) update point on the left " + lineToSimplify.get(tri.prev.indices[1]));
+// for (Point point : pointsForSig) {
+// System.out.println("\t" + point);
+// }
+// }
+// List<Point> baseLine = new ArrayList<>();
+// baseLine.add(pointsForSig.get(0));
+// baseLine.add(pointsForSig.get(pointsForSig.size() - 1)); // 直接连接左右两边最近的未被淘汰的点
+// double sig = total_areal_displacement(pointsForSig, baseLine, false);
+// tri.prev.area = sig;
+//
+// if (debug) {
+// System.out.println("sig=" + sig);
+// double tmpTri = triArea(lineToSimplify.get(tri.prev.indices[0]),
+// lineToSimplify.get(tri.prev.indices[1]),
+// lineToSimplify.get(tri.prev.indices[2]));
+// System.out.println("\t" + "tri=" + tmpTri + ", " + ((tmpTri > sig) ? "over-estimated" : "equal/less-estimated"));
+// }
+//
+// // 重新加入堆
+// // 在 Java 的 PriorityQueue 中，修改元素的属性不会自动更新堆的顺序
+// // 所以必须通过add来显式重新插入修改后的元素
+// triangleHeap.add(tri.prev); // O(logn) 注意加入的是一个新的对象isDeleted=false
+// }
+//
+// if (tri.next != null) {
+// // 标记为失效点，同时new一个新的对象接管它的一切数据和前后连接关系，然后更新前后连接关系、更新significance、加入heap使其排好序
+//
+// // 1. 处理旧的tri.next被标记删除的事情（角色替代）
+// // triangleHeap.remove(tri.next); // Avoid using heap.remove(x) as it is O(n) complexity
+// tri.next.markDeleted(); // O(1) 这个点标记为废掉，前后关联都砍断，但是不remove因为那太耗时，只有poll到它就跳过就可以
+//
+// Triangle newNext = new Triangle(tri.next); // deep copy and inherit connection
+// // tri.next = newNext; // omit, because already done by new Triangle(tri.prev)
+//
+// if (tri.prev != null) {
+// tri.prev.next = tri.next; // ATTENTION!!!: 这里的tri.next已经被换掉！所以之前的要重新赋值！
+// }
+//
+// // 2. 处理pi被淘汰引起tri.next被更新的事情
+// tri.next.prev = tri.prev; // 注意此时tri.prev已经是替代后的节点，tri.next也是，从而被标记为废点的前后关联真正砍断
+// tri.next.indices[0] = tri.indices[0];
+//
+// // e parameter
+// List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated,
+// tri.next.indices[0],
+// tri.next.indices[1],
+// tri.next.indices[2]); // TODO complexity
+// if (debug) {
+// System.out.println("(2) updating point on the right " + lineToSimplify.get(tri.next.indices[1]));
+// for (Point point : pointsForSig) {
+// System.out.println("\t" + point);
+// }
+// }
+// List<Point> baseLine = new ArrayList<>();
+// baseLine.add(pointsForSig.get(0));
+// baseLine.add(pointsForSig.get(pointsForSig.size() - 1)); // 直接连接左右两边最近的未被淘汰的点
+// double sig = total_areal_displacement(pointsForSig, baseLine, false);
+// tri.next.area = sig;
+//
+// if (debug) {
+// System.out.println("sig=" + sig);
+// double tmpTri = triArea(lineToSimplify.get(tri.next.indices[0]),
+// lineToSimplify.get(tri.next.indices[1]),
+// lineToSimplify.get(tri.next.indices[2]));
+// System.out.println("\t" + "tri=" + tmpTri + ", " + ((tmpTri > sig) ? "over-estimated" : "equal/less-estimated"));
+// }
+//
+// // 重新加入堆
+// // 在 Java 的 PriorityQueue 中，修改元素的属性不会自动更新堆的顺序
+// // 所以必须通过add 来显式重新插入修改后的元素
+// triangleHeap.add(tri.next); // 注意加入的是一个新的对象isDeleted=false
+// }
+// if (debug) {
+// System.out.println(">>>bottom-up, remaining " + triangleHeap.size() + " triangles (including those marked for removal)");
+// }
+// }
+// return results; // 注意这就是lineToSimplify.getVertices()
+// }
+//
+// public static void main(String[] args) {
+//
+// int eParam = 2000_0000;
+// try (PrintWriter writer = new PrintWriter(new File("exp_varyN_e" + eParam + ".csv"))) {
+// for (int n = 100_0000; n < 2000_0000; n += 200_0000) { // 超过两千万就都变得慢多了，感觉可能是内存有限的原因，而不是算法复杂度
+// // TODO 注意 要有一个点是n=300w
+//
+// Polyline polyline = new Polyline();
+// int seed = 1;
+// Random rand = new Random(seed); // TODO 注意seed在每轮里重设
+// for (int i = 0; i < n; i++) {
+// double v = rand.nextInt(1000000);
+// polyline.addVertex(new Point(i, v));
+// }
+//
+// long startTime = System.currentTimeMillis();
+// List<Point> results = buildEffectiveArea(polyline, eParam, false);
+// long endTime = System.currentTimeMillis();
+//
+// System.out.println("n=" + n + ", e=" + eParam + ", Time taken to reduce points: " + (endTime - startTime) + "ms");
+// writer.println(n + "," + eParam + "," + (endTime - startTime));
+// System.out.println(results.size());
+//
+// // clear
+// polyline.clear();
+// results.clear();
+// polyline = null;
+// results = null;
+// System.gc();
+// }
+// } catch (FileNotFoundException e) {
+// throw new RuntimeException(e);
+// }
+//
+//// int n = 300_0000;
+//// int seed = 1;
+//// Random rand = new Random(seed); // TODO 注意seed在每轮里重设
+//// Polyline polyline = new Polyline(); // 注意：如果是固定n变化e实验，这个数据要一次性生成，不然每次随机不一样
+//// for (int i = 0; i < n; i++) {
+//// double v = rand.nextInt(1000000);
+//// polyline.addVertex(new Point(i, v));
+//// }
+////
+//// try (PrintWriter writer = new PrintWriter(new File("exp_varyE_n" + n + ".csv"))) {
+//// int[] eParamList = {0, 1, 2, 10, 1000, 10000, 10_0000, 30_0000, 50_0000, 60_0000, 80_0000, 100_0000, 150_0000, 200_0000};
+//// for (int eParam : eParamList) {
+//// eParam *= 3; // TODO 注意 因为n=300w而不是100w
+////
+//// long startTime = System.currentTimeMillis();
+//// List<Point> results = buildEffectiveArea(polyline, eParam, false);
+//// long endTime = System.currentTimeMillis();
+////
+//// System.out.println("n=" + n + ", e=" + eParam + ", Time taken to reduce points: " + (endTime - startTime) + "ms");
+//// writer.println(n + "," + eParam + "," + (endTime - startTime));
+//// System.out.println(results.size());
+////
+//// // clear 注意不能把原始数据清除，还要接着用
+//// System.gc();
+//// }
+//// } catch (FileNotFoundException e) {
+//// throw new RuntimeException(e);
+//// }
+//
+// System.out.println("finish");
+// }
+//}