This is an automated email from the ASF dual-hosted git repository. leirui pushed a commit to branch research/LTS-visualization in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit 44b0c441c7dee1437fd62b5abf8a63ff1dcaf2c3 Author: Lei Rui <[email protected]> AuthorDate: Mon Jul 15 18:27:12 2024 +0800 add --- .../resources/conf/iotdb-engine.properties | 2 +- .../groupby/GroupByWithoutValueFilterDataSet.java | 3 + .../groupby/LocalGroupByExecutorTri_Visval.java | 160 ++++++++++++++++ .../iotdb/db/query/simpiece/MySample_visval.java | 94 ++++++++++ .../iotdb/db/query/simpiece/TimeSeriesReader.java | 94 ++++++++++ .../org/apache/iotdb/db/query/simpiece/Visval.java | 111 +++++++++++ .../iotdb/db/query/simpiece/VisvalPoint.java | 13 ++ .../apache/iotdb/db/query/simpiece/Visvalold.java | 203 +++++++++++++++++++++ 8 files changed, 679 insertions(+), 1 deletion(-) diff --git a/server/src/assembly/resources/conf/iotdb-engine.properties b/server/src/assembly/resources/conf/iotdb-engine.properties index b7a8c2130b6..696856331b7 100644 --- a/server/src/assembly/resources/conf/iotdb-engine.properties +++ b/server/src/assembly/resources/conf/iotdb-engine.properties @@ -19,7 +19,7 @@ #################### ### enable Tri #################### -# MinMax, MinMaxLTTB, M4, LTTB, ILTS, SimPiece, SC, FSW, Uniform +# MinMax, MinMaxLTTB, M4, LTTB, ILTS, SimPiece, SC, FSW, Uniform, Visval enable_Tri="" # segment error threshold for SimPiece, SC, FSW diff --git a/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/GroupByWithoutValueFilterDataSet.java b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/GroupByWithoutValueFilterDataSet.java index 97da407a4a3..32eccb2076b 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/GroupByWithoutValueFilterDataSet.java +++ b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/GroupByWithoutValueFilterDataSet.java @@ -459,6 +459,9 @@ public class GroupByWithoutValueFilterDataSet extends GroupByEngineDataSet { } else if (CONFIG.getEnableTri().equals("Uniform")) { return new LocalGroupByExecutorTri_Uniform( path, allSensors, dataType, context, timeFilter, fileFilter, ascending); + } else if (CONFIG.getEnableTri().equals("Visval")) { + return new LocalGroupByExecutorTri_Visval( + path, allSensors, dataType, context, timeFilter, fileFilter, ascending); } else { logger.info("No matched enable_tri!"); return new LocalGroupByExecutor( 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 new file mode 100644 index 00000000000..3cb801b70e7 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/dataset/groupby/LocalGroupByExecutorTri_Visval.java @@ -0,0 +1,160 @@ +/* + * 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.dataset.groupby; + +import org.apache.iotdb.db.conf.IoTDBConfig; +import org.apache.iotdb.db.conf.IoTDBDescriptor; +import org.apache.iotdb.db.engine.querycontext.QueryDataSource; +import org.apache.iotdb.db.exception.StorageEngineException; +import org.apache.iotdb.db.exception.query.QueryProcessException; +import org.apache.iotdb.db.metadata.PartialPath; +import org.apache.iotdb.db.query.aggregation.AggregateResult; +import org.apache.iotdb.db.query.aggregation.impl.MinValueAggrResult; +import org.apache.iotdb.db.query.context.QueryContext; +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.VisvalPoint; +import org.apache.iotdb.tsfile.file.metadata.enums.TSDataType; +import org.apache.iotdb.tsfile.file.metadata.statistics.MinMaxInfo; +import org.apache.iotdb.tsfile.read.common.ChunkSuit4Tri; +import org.apache.iotdb.tsfile.read.filter.GroupByFilter; +import org.apache.iotdb.tsfile.read.filter.basic.Filter; +import org.apache.iotdb.tsfile.utils.Pair; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.Comparator; +import java.util.List; +import java.util.Set; + +public class LocalGroupByExecutorTri_Visval implements GroupByExecutor { + + private static final IoTDBConfig CONFIG = IoTDBDescriptor.getInstance().getConfig(); + + // Aggregate result buffer of this path + private final List<AggregateResult> results = new ArrayList<>(); + + List<VisvalPoint> points; + + private final int m; + + public LocalGroupByExecutorTri_Visval( + PartialPath path, + Set<String> allSensors, + TSDataType dataType, + QueryContext context, + Filter timeFilter, + TsFileFilter fileFilter, + boolean ascending) + throws StorageEngineException, QueryProcessException { + // long start = System.nanoTime(); + + // get all data sources + QueryDataSource queryDataSource = + QueryResourceManager.getInstance().getQueryDataSource(path, context, timeFilter); + + // update filter by TTL + // this.timeFilter = queryDataSource.updateFilterUsingTTL(timeFilter); + + SeriesReader seriesReader = + new SeriesReader( + path, + allSensors, + // fix bug: here use the aggregation type as the series data type, + // not using pageReader.getAllSatisfiedPageData is ok + dataType, + context, + queryDataSource, + timeFilter, + null, + fileFilter, + ascending); + + try { + // : this might be bad to load all chunk metadata at first + List<ChunkSuit4Tri> futureChunkList = new ArrayList<>(); + futureChunkList.addAll(seriesReader.getAllChunkMetadatas4Tri()); + // order futureChunkList by chunk startTime + futureChunkList.sort( + new Comparator<ChunkSuit4Tri>() { + public int compare(ChunkSuit4Tri o1, ChunkSuit4Tri o2) { + return ((Comparable) (o1.chunkMetadata.getStartTime())) + .compareTo(o2.chunkMetadata.getStartTime()); + } + }); + + GroupByFilter groupByFilter = (GroupByFilter) timeFilter; + long startTime = groupByFilter.getStartTime(); + long endTime = groupByFilter.getEndTime(); + long interval = groupByFilter.getInterval(); + m = (int) Math.floor((endTime * 1.0 - startTime) / interval); + + points = TimeSeriesReader.getTimeSeriesFromTsFilesVisval(futureChunkList, startTime, endTime); + + } catch (IOException e) { + throw new QueryProcessException(e.getMessage()); + } + } + + @Override + public void addAggregateResult(AggregateResult aggrResult) { + results.add(aggrResult); + } + + @Override + public List<AggregateResult> calcResult( + long curStartTime, long curEndTime, long startTime, long endTime, long interval) + throws IOException { + // group by curStartTime and curEndTime are not used in Sim-Piece segmentation + + StringBuilder series = new StringBuilder(); + + // clear result cache + for (AggregateResult result : results) { + result.reset(); + } + + // Visval + List<VisvalPoint> reducedPoints = Visval.reducePoints(points, m); + + for (VisvalPoint p : reducedPoints) { + series.append(p.y).append("[").append(p.x).append("]").append(","); + } + + MinValueAggrResult minValueAggrResult = (MinValueAggrResult) results.get(0); + minValueAggrResult.updateResult(new MinMaxInfo<>(series.toString(), 0)); + return results; + } + + @Override + public Pair<Long, Object> peekNextNotNullValue(long nextStartTime, long nextEndTime) + throws IOException { + throw new IOException("no implemented"); + } + + @Override + public List<AggregateResult> calcResult(long curStartTime, long curEndTime) + throws IOException, QueryProcessException { + throw new IOException("no implemented"); + } +} diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_visval.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_visval.java new file mode 100644 index 00000000000..1ed02baba7c --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/MySample_visval.java @@ -0,0 +1,94 @@ +// * 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. +// */ +// Sim-Piece code forked from https://github.com/xkitsios/Sim-Piece.git + +package org.apache.iotdb.db.query.simpiece; + +import java.io.FileInputStream; +import java.io.FileWriter; +import java.io.PrintWriter; +import java.util.List; + +public class MySample_visval { + + public static void main(String[] args) { + String fileDir = "D:\\desktop\\NISTPV\\"; + String[] datasetNameList = + new String[] { + "NISTPV-Ground-2015-Qloss_Ah", + // "NISTPV-Ground-2015-Pyra1_Wm2", + // "NISTPV-Ground-2015-RTD_C_3" + }; + + int[] noutList = new int[] {2400000}; + + double[] r = new double[] {0.1, 0.5, 1.3}; + for (int y = 0; y < datasetNameList.length; y++) { + String datasetName = datasetNameList[y]; + int start = (int) (10000000 / 2 - 2500000 * r[y]); // 从0开始计数 + int end = (int) (10000000 / 2 + 2500000 * (1 - r[y])); + int N = end - start; // -1 for all + // + // int start = 0; + // int end = 100000; + // int N = end - start; + + for (int nout : noutList) { + // apply Sim-Piece on the input file, outputting nout points saved in csvFile + boolean hasHeader = false; + try (FileInputStream inputStream = new FileInputStream(fileDir + datasetName + ".csv")) { + String delimiter = ","; + List<VisvalPoint> points = + TimeSeriesReader.getMyTimeSeriesVisval( + inputStream, delimiter, false, N, start, hasHeader, false); + System.out.println(points.size()); + System.out.println(nout); + + List<VisvalPoint> reducedPoints = Visval.reducePoints(points, nout); + try (PrintWriter writer = + new PrintWriter( + new FileWriter( + datasetName + "-" + N + "-" + reducedPoints.size() + "-visval.csv"))) { + for (VisvalPoint p : reducedPoints) { + writer.println(p.x + "," + p.y); + } + } + System.out.println(reducedPoints.size()); + } catch (Exception e) { + e.printStackTrace(); + } + } + } + } + + // List<Point> points = new ArrayList<>(); + // points.add(new Point(1, 10)); + // points.add(new Point(2, 20)); + // points.add(new Point(3, 15)); + // points.add(new Point(4, 10)); + // points.add(new Point(5, 30)); + // points.add(new Point(6, 25)); + // points.add(new Point(7, 20)); + // int m = 4; + // List<Point> reducedPoints = Visval.reducePoints(points, m); + // System.out.println("Reduced points:"); + // for (Point point : reducedPoints) { + // System.out.println("Timestamp: " + point.getTimestamp() + ", Value: " + + // point.getValue()); + // } +} diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/TimeSeriesReader.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/TimeSeriesReader.java index 129baeefeda..65b828cb1b1 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/TimeSeriesReader.java +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/TimeSeriesReader.java @@ -80,6 +80,46 @@ public class TimeSeriesReader { return new TimeSeries(ts, max - min); } + public static List<VisvalPoint> getTimeSeriesFromTsFilesVisval( + List<ChunkSuit4Tri> chunkSuit4TriList, long startTime, long endTime) throws IOException { + // assume chunkSuit4TriList already sorted in increasing time order + ArrayList<VisvalPoint> ts = new ArrayList<>(); + double max = Double.MIN_VALUE; + double min = Double.MAX_VALUE; + + for (ChunkSuit4Tri chunkSuit4Tri : chunkSuit4TriList) { + ChunkMetadata chunkMetadata = chunkSuit4Tri.chunkMetadata; + long chunkMinTime = chunkMetadata.getStartTime(); + long chunkMaxTime = chunkMetadata.getEndTime(); + if (chunkMaxTime < startTime) { + continue; + } else if (chunkMinTime >= endTime) { + break; + } else { + PageReader pageReader = + FileLoaderUtils.loadPageReaderList4CPV( + chunkSuit4Tri.chunkMetadata, + null); // note do not assign to chunkSuit4Tri.pageReader + for (int j = 0; j < chunkSuit4Tri.chunkMetadata.getStatistics().getCount(); j++) { + IOMonitor2.DCP_D_getAllSatisfiedPageData_traversedPointNum++; + long timestamp = pageReader.timeBuffer.getLong(j * 8); + if (timestamp < startTime) { + continue; + } else if (timestamp >= endTime) { + break; + } else { // rightStartTime<=t<rightEndTime + ByteBuffer valueBuffer = pageReader.valueBuffer; + double value = valueBuffer.getDouble(pageReader.timeBufferLength + j * 8); + ts.add(new VisvalPoint(timestamp, value)); + max = Math.max(max, value); + min = Math.min(min, value); + } + } + } + } + return ts; + } + public static TimeSeries getTimeSeries(InputStream inputStream, String delimiter, boolean gzip) { ArrayList<Point> ts = new ArrayList<>(); double max = Double.MIN_VALUE; @@ -163,4 +203,58 @@ public class TimeSeriesReader { return new TimeSeries(ts, max - min); } + + public static List<VisvalPoint> getMyTimeSeriesVisval( + InputStream inputStream, + String delimiter, + boolean gzip, + int N, + int startRow, + boolean hasHeader, + boolean seriesTimeColumn) { + // N<0 means read all lines + + ArrayList<VisvalPoint> ts = new ArrayList<>(); + double max = Double.MIN_VALUE; + double min = Double.MAX_VALUE; + + try { + if (gzip) { + inputStream = new GZIPInputStream(inputStream); + } + Reader decoder = new InputStreamReader(inputStream, StandardCharsets.UTF_8); + BufferedReader bufferedReader = new BufferedReader(decoder); + + String line; + if (hasHeader) { + bufferedReader.readLine(); + } + int startCnt = 0; + while (startCnt < startRow && (line = bufferedReader.readLine()) != null) { + startCnt++; + } + if (startCnt < startRow) { + throw new IOException("not enough rows!"); + } + int cnt = 0; + while ((cnt < N || N < 0) && (line = bufferedReader.readLine()) != null) { + String[] elements = line.split(delimiter); + long timestamp; + if (!seriesTimeColumn) { + timestamp = (long) Double.parseDouble(elements[0]); + } else { + timestamp = cnt + 1; + } + double value = Double.parseDouble(elements[1]); + ts.add(new VisvalPoint(timestamp, value)); + + max = Math.max(max, value); + min = Math.min(min, value); + cnt++; + } + } catch (IOException e) { + e.printStackTrace(); + } + return ts; + } } 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/Visval.java new file mode 100644 index 00000000000..d4b54d3adc1 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval.java @@ -0,0 +1,111 @@ +/* + * 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.simpiece; + +import java.util.List; +import java.util.concurrent.ConcurrentSkipListMap; + +public class Visval { + + public static List<VisvalPoint> reducePoints(List<VisvalPoint> points, int targetCount) { + if (points.size() <= targetCount) { + return points; + } + + ConcurrentSkipListMap<Double, VisvalPoint> minHeap = new ConcurrentSkipListMap<>(); + // 初始化双向链表和优先队列 + for (int i = 1; i < points.size() - 1; i++) { + VisvalPoint p = points.get(i); + p.prev = points.get(i - 1); + p.next = points.get(i + 1); + p.area = calculateArea(p.prev, p, p.next); + minHeap.put(p.area, p); + } + + while (points.size() > targetCount) { + // 移除面积最小的点 + VisvalPoint p = minHeap.pollFirstEntry().getValue(); + if (p == null) { + return points; + } + // 移除点 p + VisvalPoint prev = p.prev; + VisvalPoint next = p.next; + prev.next = next; + next.prev = prev; + + // 更新相邻点的三角形面积 + if (prev.prev != null) { + minHeap.remove(prev.area); + prev.area = calculateArea(prev.prev, prev, next); + minHeap.put(prev.area, prev); + } + if (next.next != null) { + minHeap.remove(next.area); + next.area = calculateArea(prev, next, next.next); + minHeap.put(next.area, next); + } + points.remove(p); + } + + return points; + } + + 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<>(); + // List<Point> pointsold = new ArrayList<>(); + // // 添加点到列表 points 100万数据 + // Random rand = new Random(); + // + // int targetCount = 10; + // for (int i = 0; i < 10000; i++) { + // int v = rand.nextInt(1000); + // points.add(new VisvalPoint(i, v)); + // pointsold.add(new Point(i, v)); + // } + // + //// int targetCount = 9000000; + //// for (int i = 0; i < 10000000; i++) { + //// points.add(new VisvalPoint(i, rand.nextInt(1000))); + //// } + // + // // 计算运行时间 + // long startTime = System.currentTimeMillis(); + // + // List<VisvalPoint> reducedPoints = Visval.reducePoints(points, targetCount); + // for (VisvalPoint point : reducedPoints) { + // System.out.println("Timestamp: " + point.x + ", Value: " + point.y); + // } + // List<Point> reducedPointsold = Visvalold.reducePoints(pointsold, targetCount); + // for (Point point : reducedPointsold) { + // System.out.println("Timestamp: " + point.getTimestamp() + ", Value: " + + // point.getValue()); + // } + // // 输出结果 + // 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/VisvalPoint.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/VisvalPoint.java new file mode 100644 index 00000000000..ef29bc30c09 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/VisvalPoint.java @@ -0,0 +1,13 @@ +package org.apache.iotdb.db.query.simpiece; + +public class VisvalPoint { + + public double x, y; + public VisvalPoint prev, next; // 双向链表中的前驱和后继 + public double area; // 与相邻点形成的三角形面积 + + VisvalPoint(double x, double y) { + this.x = x; + this.y = y; + } +} diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visvalold.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visvalold.java new file mode 100644 index 00000000000..2592d042c3c --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visvalold.java @@ -0,0 +1,203 @@ +// * 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.simpiece; + +import java.util.ArrayList; +import java.util.List; +import java.util.stream.IntStream; + +// Visvalingam-Whyatt method of poly-line vertex reduction +// +// Visvalingam, M and Whyatt J D (1993) +// "Line Generalisation by Repeated Elimination of Points", Cartographic J., 30 (1), 46 - 51 +// +// Described here: +// +// http://web.archive.org/web/20100428020453/http://www2.dcs.hull.ac.uk/CISRG/publications/DPs/DP10/DP10.html +// +// ========================================= +// +// The MIT License (MIT) +// +// Copyright (c) 2014 Elliot Hallmark +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to deal +// in the Software without restriction, including without limitation the rights +// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in all +// copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +// SOFTWARE. +// +// ================================ +public class Visvalold { + + private static class Triangle implements Comparable<Triangle> { + + int index; + double area; + + Triangle(int index, double area) { + this.index = index; + this.area = area; + } + + @Override + public int compareTo(Triangle other) { + return Double.compare(this.area, other.area); + } + } + + public static List<Point> reducePoints(List<Point> points, int m) { + if (points.size() <= m) { + return points; + } + + // areas and remainIdx: records the dominating areas and indexes of remaining points during + // bottom-up elimination + // through remainIdx we can know the adjacency of remaining points easily. + // TreeMap<Double, Integer> areasMap = new TreeMap<>();// for speedup + List<Double> areas = triangleAreaList(points); + List<Integer> remainIdx = new ArrayList<>(); + IntStream.range(0, points.size()).forEach(remainIdx::add); + + int minIndex = 0; + for (int i = 1; i < areas.size(); i++) { + if (areas.get(i) < areas.get(minIndex)) { + minIndex = i; + } + } + // AtomicInteger minIndexTmp = new AtomicInteger(0); + // IntStream.range(0, areas.size()).parallel().forEach(i -> { + // if (areas.get(i) < areas.get(minIndexTmp.get())) { + // minIndexTmp.set(i); + // } + // }); + // int minIndex = minIndexTmp.get(); + double this_area = areas.get(minIndex); + areas.remove(minIndex); + remainIdx.remove(minIndex); + + while (remainIdx.size() > m) { + boolean skip = + false; // false mean next round needs to argmin globally, otherwise use recentMinIdx + int recentMinIdx = -1; + + // update right new triangle area + double right_area = Double.POSITIVE_INFINITY; + if (minIndex <= remainIdx.size() - 2) { + // note that now i already pop out min_vert + right_area = + calculateTriangleArea( + points.get(remainIdx.get(minIndex - 1)), + points.get(remainIdx.get(minIndex)), + points.get(remainIdx.get(minIndex + 1))); + if (right_area <= this_area) { + // so next round does not need argmin globally + skip = true; + recentMinIdx = minIndex; // note that now i already pop out min_vert + } + areas.set(minIndex, right_area); + } + + // update left new triangle area + if (minIndex >= 2) { + // note that now i already pop out min_vert + double left_area = + calculateTriangleArea( + points.get(remainIdx.get(minIndex - 2)), + points.get(remainIdx.get(minIndex - 1)), + points.get(remainIdx.get(minIndex))); + if (left_area <= this_area) { + if (skip) { // means right point area is smaller than this_area, then compare left and + // right + if (left_area <= right_area) { + recentMinIdx = minIndex - 1; + } + // otherwise keep skip right point + } else { // means right point area is larger than this_area, while left is smaller than + skip = true; // so next round does not need argmin globally + recentMinIdx = minIndex - 1; + } + } + areas.set(minIndex - 1, left_area); + } + + if (!skip) { // left and right new triangle both larger than this_area, needs to argmin + // globally + minIndex = 0; + for (int i = 1; i < areas.size(); i++) { + if (areas.get(i) < areas.get(minIndex)) { + minIndex = i; + } + } + // AtomicInteger minIndexTmp2 = new AtomicInteger(0); + // IntStream.range(0, areas.size()).parallel().forEach(i -> { + // if (areas.get(i) < areas.get(minIndexTmp2.get())) { + // minIndexTmp2.set(i); + // } + // }); + // minIndex = minIndexTmp2.get(); + } else { + minIndex = recentMinIdx; + } + this_area = areas.get(minIndex); + areas.remove(minIndex); + remainIdx.remove(minIndex); + } + + List<Point> result = new ArrayList<>(); + for (int i : remainIdx) { + result.add(points.get(i)); + } + return result; + } + + private static List<Double> triangleAreaList(List<Point> points) { + List<Double> result = new ArrayList<>(); + result.add(Double.POSITIVE_INFINITY); // first + for (int i = 1; i < points.size() - 1; i++) { + double area = calculateTriangleArea(points.get(i - 1), points.get(i), points.get(i + 1)); + result.add(area); + } + result.add(Double.POSITIVE_INFINITY); // last + return result; + } + + private static double calculateTriangleArea(Point a, Point b, Point c) { + double x1 = a.getTimestamp(); + double y1 = a.getValue(); + double x2 = b.getTimestamp(); + double y2 = b.getValue(); + double x3 = c.getTimestamp(); + double y3 = c.getValue(); + + return Math.abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0); + } +}
