I have been doing some (not very extensive) research on line decimation (polyline simplification or curve approximation in some literature). My understanding of the current algorithm for vtkDecimatePolylineFilter is as follows:
- For every node (not including the initial and terminal nodes) calculate the error between the straight line distance between it’s neighbours and itself (using a strategy that is defaulted to PolylineAngleStrategy). Add this edge to a min-heap where the key is the error calculated.
- Pop the heap until enough points have been discarded or the error of the top of the heap is too large.
My understanding is that this heuristic does not guarantee an either the min-# or the min-epsilon solution for the decimation.
My proposal is to include alternatives for users that would like the guaranteed optimal solutions–using the algorithm described by Barequet, Chen and Daescu, 2002 (Efficiently Approximating Polygonal Paths in Three and Higher Dimensions). That runs in O(n^2 log(n)) and O(n^2 log^3 n) time for the min-# and min-eps problems respectively.
With some emphasis on alternative as the current algorithm runs in O(n log n)? So they only need reach for this proposed algorithm if they need an optimal result.
I know that the mesh decimation module has much more work done on it and that may be a result of line decimation being unnecessary in medical imaging applications.