4 ms·

Interesting approach. Recently (in SwiftUI) I did something similar using Ramer–Douglas–Peucker to retain only significant points. Not as sophisticated, but too

Interesting approach. Recently (in SwiftUI) I did something similar using Ramer–Douglas–Peucker to retain only significant points. Not as sophisticated, but took about half a day to implement. Render lag went from annoying to barely noticeable.

nikonp 3y ago
Cool! I don’t know Ramer-Douglas-Pecker, how did that work?
- nauful 3y ago
  It's a simplification algorithm for a series of points. Briefly, if you have a group of several points relatively close to a straight line between the first and last point in the group, all of the middle points may be removed. Given a first and last point, it finds the point furthest away from a straight line connection, then recursively divides down the pairs of (first, furthest) and (last, furthest) only if the furthest point is above a minimum threshold distance from a straight line connection.
  - justjust 3y ago
    It seems a similar idea would be to adjust a linear model to a sequence of points and just maintain those that are outliers and other two that are end points on the linear model.
abey79 3y ago
(Rerun engineer here.) That's actually pretty good idea for egui_plots itself (the lib we use to render the plots), as it would be of general usefulness. The aggregation described in the article is somewhat specific to time-series. I'm not super-familiar with the Ramer–Douglas–Peucker algorithm itself but I've used implementations of it, and, from the looks of it, its CPU cost would largely be offset by the savings in triangulation done by egui's renderer (also done on CPU currently).
- abey79 3y ago
  FWIW, I opened an issue: https://github.com/emilk/egui/issues/4046 https://github.com/emilk/egui/issues/4046
- deleted 3y ago
  [deleted]
tda 3y ago
Yep, that trusty simple algorithm always works. I have some grafana dashboards that plot a lot of 3D data (x,y,z lines coloured by some sensor readings) using a plotly plugin. I can't pre-aggregate too much in the database, or I'll loose too much detail. So I ended up adding a little ad-hoc js implementation to reduce my number of points by a factor ten on the fly for plotting, works great. I was just about to write down that it would be too difficult to de RDP simplification in the (ClickHouse) database, but then I recalled PostGIS has it built in and low and behold, there is also something in ClickHouse for this [0]. Back to the drawing board. [0] https://clickhouse.com/codebrowser/ClickHouse/contrib/boost/boost/geometry/strategies/agnostic/simplify_douglas_peucker.hpp.html https://clickhouse.com/codebrowser/ClickHouse/contrib/boost/...

nikonp 3y ago

Cool! I don’t know Ramer-Douglas-Pecker, how did that work?

nauful 3y ago
It's a simplification algorithm for a series of points. Briefly, if you have a group of several points relatively close to a straight line between the first and last point in the group, all of the middle points may be removed. Given a first and last point, it finds the point furthest away from a straight line connection, then recursively divides down the pairs of (first, furthest) and (last, furthest) only if the furthest point is above a minimum threshold distance from a straight line connection.
- justjust 3y ago
  It seems a similar idea would be to adjust a linear model to a sequence of points and just maintain those that are outliers and other two that are end points on the linear model.

abey79 3y ago

(Rerun engineer here.) That's actually pretty good idea for egui_plots itself (the lib we use to render the plots), as it would be of general usefulness. The aggregation described in the article is somewhat specific to time-series. I'm not super-familiar with the Ramer–Douglas–Peucker algorithm itself but I've used implementations of it, and, from the looks of it, its CPU cost would largely be offset by the savings in triangulation done by egui's renderer (also done on CPU currently).

abey79 3y ago
FWIW, I opened an issue: https://github.com/emilk/egui/issues/4046 https://github.com/emilk/egui/issues/4046
deleted 3y ago
[deleted]

tda 3y ago

Yep, that trusty simple algorithm always works. I have some grafana dashboards that plot a lot of 3D data (x,y,z lines coloured by some sensor readings) using a plotly plugin. I can't pre-aggregate too much in the database, or I'll loose too much detail. So I ended up adding a little ad-hoc js implementation to reduce my number of points by a factor ten on the fly for plotting, works great. I was just about to write down that it would be too difficult to de RDP simplification in the (ClickHouse) database, but then I recalled PostGIS has it built in and low and behold, there is also something in ClickHouse for this [0]. Back to the drawing board. [0] https://clickhouse.com/codebrowser/ClickHouse/contrib/boost/boost/geometry/strategies/agnostic/simplify_douglas_peucker.hpp.html https://clickhouse.com/codebrowser/ClickHouse/contrib/boost/...