I don't know how helpful I'm being here, but I think my suggestion is pretty much the same as before, which is, essentially:

- You almost certainly don't need to change the RDP code significantly in order to preserve the time values. So if that's the reason you're rewriting/modifying the code, then I'd say the changes you're making aren't necessary.

- Based on the code you posted earlier, I think all you need to do is make RDPpoint a struct/class of your own creation, with 'first' and 'second' fields of type double, and a field for time as well. (It's possible other changes might be required, depending, but they should be minor.) After making these changes, the output should include the time values.

If what I'm suggesting doesn't seem suitable or adequate for some reason, maybe you could clarify why that is (that way I or someone else can maybe provide other, more useful feedback).

@Zakwayda The reason i try to modify the RDP function is

1. I have to copy the xy data from my struct to an std::vector<RDPpoint> PLin; point list to be able to feed the function (RDPpoint is a pair<double,double>)

2. Then in reverse i copy the result of the RDP function back to std::vector<RDPpoint> PLOut; And then again clear/update my struct with PLOut.

I mean thats not very efficient. It works,yes. Its fast enough, but its "dirty", haha.

3. I just realized that i should actually pass my struct instead of an sf::VertexArray only, or else i dont get the time into the function...

typedef std::pair<double, double> RDPpoint;

std::vector<RDPpoint> PLin;	// Pointlist In  for Reduction
std::vector<RDPpoint> PLOut;	// Pointlist Out for Reduction
  

//---------------------------------------------------------------------------------------------------------
// Reduction - RamerDouglasPeucker
//---------------------------------------------------------------------------------------------------------

VCount1 = PenSmoot[LineNR - 1].vertices.getVertexCount();
				
PLin.clear();
PLin.shrink_to_fit();

for (int i = 0; i < VCount1; i++)
{
	PLin.emplace_back(RDPpoint(PenSmoot[LineNR - 1].vertices[i].position.x, PenSmoot[LineNR - 1].vertices[i].position.y));
}

RamerDouglasPeucker(PLin, 3.0, PLOut);
VCount2 = PLOut.size();							// Vertex count
PenSmoot[LineNR - 1].vertices.resize(VCount2);

for (int i = 0; i < VCount2; i++)
{
	PenSmoot[LineNR - 1].vertices[i].position.x = PLOut[i].first;
	PenSmoot[LineNR - 1].vertices[i].position.y = PLOut[i].second;
	PenSmoot[LineNR - 1].vertices[i].color      = Color;
}

The problem I'm trying to help you solve at the moment is how to get the RDP code to preserve the time values between input and output. Optimization and elegance are separate problems. It sort of seems like you're trying to solve all these problems at once, which may be making things more complicated than they need to be.

If I were you I'd focus solely and exclusively on solving the time value problem (which is the topic of the thread), and then tackle performance, optimization, cleanliness, elegance, etc. separately. To that end, my suggestion remains the same. Make RDPpoint a struct/class that includes a time value. Then in this code:

VCount1 = PenSmoot[LineNR - 1].vertices.getVertexCount();
                
PLin.clear();
PLin.shrink_to_fit();

for (int i = 0; i < VCount1; i++)
{
    PLin.emplace_back(RDPpoint(PenSmoot[LineNR - 1].vertices[i].position.x, PenSmoot[LineNR - 1].vertices[i].position.y));
}

RamerDouglasPeucker(PLin, 3.0, PLOut);
VCount2 = PLOut.size();                                                // Vertex count
PenSmoot[LineNR - 1].vertices.resize(VCount2);

for (int i = 0; i < VCount2; i++)
{
    PenSmoot[LineNR - 1].vertices[i].position.x = PLOut[i].first;
    PenSmoot[LineNR - 1].vertices[i].position.y = PLOut[i].second;
    PenSmoot[LineNR - 1].vertices[i].color      = Color;
}

When you create the RDPpoint instances, include the time values, and when you copy the results back out, include the time values there as well. (As I mentioned before, there might be other minor changes involved, but I'd have to see all the code to be specific about that.)

I think your original problem is probably fairly straightforward to solve, and and if I can help with that I'm happy to do so ? However, it seems like we're sort of skating around the actual problem here. So again, I suggest focusing on the original problem, as stated, and saving any other concerns for later.

If the issue here is that it's not clear what I'm suggesting, let me know and I'll be happy to try and clarify.

So my idea was to have the original input curve which holds all the data then make a copy of it manipulate the copy, which worked really very well so far.

So i have now 1 question:

Why do you think that its necessary to include the time into the smoothing process versus processing the time after the smoothing process?

I know. You said because we get lesser time points. And something about intersections. But why should there be intersections when the vector is anyway just a list ?

The issue here is: Me. Because i have no idea what iam doing, haha! ?‍♂️

Okay. However. I will concentrate now to get my struct into this function.

Thank you!

I'm not sure if I correctly understand the problem, but I suspect you want to store the input data as vectors instead of points. Then you can always compute a local velocity. Basically what Zakwayda said.

The problem of this thread is that i need to transfer time deltas or absolute time from an handdrawn curve which holds all the data (xy,time) to a smoothed version of this curve which holds only xy data and has a different point count/size(). 

24 minutes ago, C3D_ said:

@ZakwaydaThe issue here is: Me. Because i have no idea what iam doing, haha! ?‍♂️

Haha, no worries That's what discussion forums like this one are for.

Quote

I didnt even mention the pen pressure value that is also part of the struct and needs to be interpolated as well.

That's an additional consideration, but any solution that properly interpolates the original time values should be able to handle the pressure values as well, so I don't think it complicates things much.

Quote

And something about intersections. But why should there be intersections when the vector is anyway just a list?

When I say 'intersections' I'm talking about geometric intersections - that is, the path 'crossing' itself. An example of this in the video you posted is where the path crosses itself after you draw the first rectangular shape. It also crosses, connects with, and backtracks on itself multiple times after that. (As I mentioned earlier I do wonder if the smoothing algorithms you're using are robust and reliable with respect to arbitrary complex paths like the one in the video, but for the sake of discussion we'll assume they are.)

Quote

Why do you think that its necessary to include the time into the smoothing process versus processing the time after the smoothing process?

I've tried to think of a post-processing solution that could handle arbitrary, possibly self-intersecting paths, but I haven't been able to think of one. We're pretty deep into the thread, so there may not be many other eyes on this at this point, but maybe someone else can suggest a post-processing solution. But it seems like a difficult problem to me. I think my original solution would probably work for paths that don't self-intersect or pass very close to themselves, but without modification it would be vulnerable to failure given a path like that in your video.

Also, given that you're interested in performance and optimization, doing this via post-processing will almost certainly be considerably more expensive than doing it as part of the smoothing process, because the necessary information is already available during the smoothing process, but a separate post-processing process would have to reconstruct that information somehow.

So I think I can sum up why doing this as part of the smoothing is preferable as follows:

- It's not obvious (to me at least) how to do the interpolation robustly and reliably via post-processing.

- Even if such a solution were available, it would likely be more expensive than doing it as part of the path smoothing.

- Based on what I know of the algorithms you're using, doing the interpolation as part of the path smoothing should be relatively straightforward, so I don't see any reason to shy away from it. I understand though that if you're not particularly comfortable with C++ and/or the algorithms in question, even making fairly simple changes might be daunting.

Quote

Okay. However. I will concentrate now to get my struct into this function.

If by this you mean modifying the smoothing code to work directly with your own data structures rather than with e.g. std::pair, then in essence, yes, that's exactly what I'm recommending. Basically, everywhere the original code copies/moves/creates position values, you want to instead copy/move/create instances of your data structure (the one that includes time, pressure, etc.), and everywhere the original code interpolates positions, you also want to interpolate time and pressure values as well.

The last thing I'll say for the moment is that earlier I see this code:

struct Pencil 
{
    sf::VertexArray vertices;
    std::vector<int> pressure;
    std::vector<sf::Int32> timeAbslt;
    std::vector<sf::Int32> timeDelta;
};

Which is an 'SoA' ('structure of arrays'). Although your smoothing code could be modified to work with this, it would probably be easier to use an array of structures instead, so that the smoothing code has to deal with fewer arrays and can deal with pencil point instances as single units. (You can read more about SoA vs AoS here.)

Quote

The problem of this thread is that i need to transfer time deltas or absolute time from an handdrawn curve which holds all the data (xy,time) to a smoothed version of this curve which holds only xy data and has a different point count/size().

You posted this while I was writing the above, but just to be clear, it seems to me that the goal is for the smoothed curve to include more information than just xy data - it should include interpolated time and pressure as well. If that assumption is wrong, it might be worth clarifying that.

I don't understand it either. It seems logical that you need a place to store that extra data if you want more than just a position. Do you have some hard restrictions on your data model? Otherwise you could perhaps store that information separately.

I just found some time to work on this. The code ended up being a bit less clear than I was hoping for. I could probably make it cleaner, but it's getting late. No guarantees, but give it a try.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cassert>

struct Point {
  double x, y;
};

double distance(Point p1, Point p2) {
  return std::pow(p1.x - p2.x, 2) + std::pow(p1.y - p2.y, 2);
}

struct TimedPoint {
  double time;
  Point point;
};

Point time_interpolation(std::vector<TimedPoint> const &timed_curve, double time) {
  auto upper = std::upper_bound(timed_curve.begin(), timed_curve.end(), time, [](double t, TimedPoint const &p){return t < p.time;});
  if (upper == timed_curve.end())
    return timed_curve.back().point;
  if (upper == timed_curve.begin())
    return timed_curve.front().point;
  auto lower = upper - 1;
  double lambda = (time - lower->time) / (upper->time - lower->time);
  return Point{(1.0 - lambda) * lower->point.x + lambda * upper->point.x, (1.0 - lambda) * lower->point.y + lambda * upper->point.y};
}

std::vector<double> retime_curve(std::vector<TimedPoint> const &original, std::vector<Point> const &smoothed, unsigned resolution) {
  assert(smoothed.size() <= resolution);
  double total_time = original.back().time;
  std::vector<std::vector<double>> fit_quality(smoothed.size(), std::vector<double>(resolution+1));
  std::vector<std::vector<unsigned>> time_of_previous_point(smoothed.size(), std::vector<unsigned>(resolution+1));
  
  for (unsigned last_time = 0; last_time <= resolution; ++last_time)
    fit_quality[0][last_time] = distance(smoothed[0], time_interpolation(original, total_time * ((double)last_time / resolution)));
  
  for (size_t last_point = 1; last_point < smoothed.size(); ++last_point) {
    for (unsigned last_time = 0; last_time <= resolution; ++last_time) {
      double error = distance(smoothed[last_point], time_interpolation(original, total_time * ((double)last_time / resolution)));
      if (last_time > 0) {
	double min_error_in_previous_points = 1e20;
	for (unsigned prev_time = 0; prev_time < last_time; ++prev_time) {
	  double error_in_previous_points = fit_quality[last_point - 1][prev_time];
	  if (error_in_previous_points < min_error_in_previous_points) {
	    min_error_in_previous_points = error_in_previous_points;
	    time_of_previous_point[last_point][last_time] = prev_time;
	  }
	}
	error += min_error_in_previous_points;
      }
      fit_quality[last_point][last_time] = error;
    }
  }

  std::vector<double> result(smoothed.size());
  
  unsigned time = resolution;
  for (size_t alternative_final_time = smoothed.size(); alternative_final_time < resolution; ++alternative_final_time) {
    if (fit_quality[smoothed.size()-1][alternative_final_time] < fit_quality[smoothed.size()-1][time])
      time = alternative_final_time;
  }
  for (size_t last_point = smoothed.size(); last_point-->0;) {
    result[last_point] = total_time * ((double)time / resolution);
    time = time_of_previous_point[last_point][time];
  }

  return result;
}

int main() {
  std::vector<TimedPoint> curve;
  curve.push_back(TimedPoint{1.0, Point{1.0, 1.0}});
  curve.push_back(TimedPoint{2.0, Point{1.1, 1.2}});
  curve.push_back(TimedPoint{3.0, Point{1.3, 1.69}});
  curve.push_back(TimedPoint{4.0, Point{2.0, 4.0}});
  curve.push_back(TimedPoint{5.0, Point{3.0, 9.0}});
  
  std::vector<Point> smoothed;
  smoothed.push_back(Point{1.2, 1.44});
  smoothed.push_back(Point{2.0, 4.0});
  smoothed.push_back(Point{3.2, 10.24});
  
  for (auto t : retime_curve(curve, smoothed, 1000))
    std::cout << t << '\n';
}