Split a string of line segments into several other line segments

Question

I have written a code to extend "n" points, constituting "n-1" lines ,to constitute more lines so you can map "m" data to "m" lines with m > n-1.

This is the function I wrote : https://github.com/embeddedmz/split_a_string_of_2d_line_segments/blob/d4137c087d0c2df1917f3b57170db96d81aca3b9/mainwindow.cpp#L137 It was really hard to write, I did it in 2019 with the VTK framework (coloring lines on a map background with data, there was not enough GeoJSON points) and I want to improve the code (the dot added towards the end is not precise).

Has anyone ever coded something like this ?

In my french blog post (you can translate it), I briefly describe what the algorithm is supposed to do: https://mmzoughi.wordpress.com/2022/08/22/decouper-une-chaine-de-segments-de-ligne-en-plusieurs-autres-segments-de-ligne/

Update : the extended points with my function are the green points and the black points are the ones created with lightxbulb function (notice a black point at 0,0 that's a bug) :

Answer 1

Here is some pseudo-code for an arc-length parametrization (would work for any dimension if you replace vec2 with vecD):

vec2 p[n]; /* initial points */
vec2 q[m]; /* array for output points */

/* cumulative distances */
float dists[n]; 
dists[0] = 0;
for (int i=1; i<n; ++i)
    dists[i] = dists[i-1] + length(p[i]-p[i-1]);

/* step size */
float step = dists[n-1] / (m-1);
q[0] = p[0];
float total_dist = 0;
int segment_idx = 1;
for (int i=1; i<m; ++i)
{
    total_dist = total_dist + step;
    while (total_dist>dists[segment_idx])
    {
         ++segment_idx;
         if (segment_idx==n)
             goto end;
    }
    float t = (total_dist - dists[segment_idx-1]) / (dists[segment_idx]-dists[segment_idx-1]);
    q[i] = (1-t) * p[segment_idx-1] + t * p[segment_idx];
}
end:
q[m-1] = p[n-1];

For the above to work you should not have degenerate cases such as length(p[i]-p[i-1])==0 or you have to write extra code to handle those.

Edit: Here is how the vec2 struct may look like:

struct vec2
{
    float e[2];
    vec2() : e{0,0} {}
    vec2(float e0, float e1) : e{e0,e1} {}
    const float& operator[](int i) const {return e[i];}
    float& operator[](int i) {return e[i];}
};

vec2 operator+(const vec2& l, const vec2& r)
{
    return vec2(l[0]+r[0], l[1]+r[1]);
}

vec2 operator-(const vec2& l, const vec2& r)
{
    return vec2(l[0]-r[0], l[1]-r[1]);  
}

vec2 operator*(float l, const vec2& r)
{
    return vec2(l*r[0], l*r[1]);
}

float dot(const vec2& l, const vec2& r)
{
    return l[0]*r[0]+l[1]*r[1];
}

float length(const vec2& v)
{
    return sqrtf(dot(v,v));
}
```