<p>Here is some pseudo-code for an arc-length parametrization (would work for any dimension if you replace <code>vec2</code> with <code>vecD</code>):</p>
<pre class="lang-cpp prettyprint-override"><code>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&lt;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&lt;m; ++i)
{
    total_dist = total_dist + step;
    while (total_dist&gt;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];
</code></pre>
<p>For the above to work you should not have degenerate cases such as <code>length(p[i]-p[i-1])==0</code> or you have to write extra code to handle those.</p>
<p>Edit:
Here is how the <code>vec2</code> struct may look like:</p>
<pre><code>struct vec2
{
    float e[2];
    vec2() : e{0,0} {}
    vec2(float e0, float e1) : e{e0,e1} {}
    const float&amp; operator[](int i) const {return e[i];}
    float&amp; operator[](int i) {return e[i];}
};

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

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

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

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

float length(const vec2&amp; v)
{
    return sqrtf(dot(v,v));
}
<span class="math-container">```</span>
</code></pre>

CC BY-SA 4.0
2022-08-25T10:28:17.120Z
Is length(p[i]-p[i-1]); => length(p[i], p[i-1]); ?
Aminos
CC BY-SA 4.0
2022-08-25T10:40:31.863Z
I mean what should it return ?
Aminos
CC BY-SA 4.0
2022-08-25T10:58:16.200Z
@Aminos `length(v) = sqrt(dot(v,v))`, mathematically: $\|v\| = \sqrt{(v\cdot v)}$, the `length` function here takes one vector, not two. You can instead define a distance function such that `dist(u,v) = length(u-v)=length(v-u)`.
lightxbulb
CC BY-SA 4.0
2022-08-26T16:32:14.707Z
it works really well, but there's a bug : the second last point is set to (0, 0), you can take a look at my code. I added a screenshot to my question but it doesn't include the point at (0, 0)
Aminos
CC BY-SA 4.0
2022-08-26T16:38:30.523Z
this is the github repo https://github.com/embeddedmz/split_a_string_of_2d_line_segments
Aminos
CC BY-SA 4.0
2022-08-26T16:42:57.757Z
@Aminos I didn't quite get what the bug is. What did you expect to happen and what happened instead? I saw the screenshot but that didn't really help. I don't know where (0,0) is in your image either, as there's no point of reference (e.g. coordinate system center and axes, ideally a grid).
lightxbulb
CC BY-SA 4.0
2022-08-26T21:23:25.330Z
if the output points array size is 32, the point at index 30 is (0, 0)
Aminos
CC BY-SA 4.0
2022-08-26T21:56:55.813Z
@Aminos You can try to output the elements of `q[i] = (1-t) * p[segment_idx-1] + t * p[segment_idx];` whenever this happens. That is print out `segment_idx`, `total_dist`, `dists[segment_idx-1]`, `dists[segment_idx]`, `t`, `p[segment_idx-1]`, `p[segment_idx-1]`. That should give you a clue whether this is a bug or not. And if it's a bug it should give you a clue what goes wrong.
lightxbulb
CC BY-SA 4.0
2022-08-27T22:46:32.973Z
when we reach the second last point and execute goto end; we will insert a final point at the end of the array q at the position m-1 but the position m-2 wasn't updated at all hence the (0,0) value. So, like I did with my code based on dot product, it's better to fill m - 2 with the the last input array point and then go beyond that point to fill the index m - 1. I think this issue is related to float computations.
Aminos
CC BY-SA 4.0
2022-08-27T23:11:41.137Z
this is how I fixed the issue, please look at lines 40 (declaring int outside the for loop) and the "end" label located at line 53: https://github.com/embeddedmz/split_a_string_of_2d_line_segments/blob/master/mainwindow.cpp
Aminos
CC BY-SA 4.0
2022-08-23T19:28:14.493Z
2022-08-25T11:04:59.410Z
2022-08-25T11:04:59.410Z
lightxbulb
<p>I have written a code to extend &quot;n&quot; points, constituting &quot;n-1&quot; lines ,to constitute more lines so you can map &quot;m&quot; data to &quot;m&quot; lines with m &gt; n-1.</p>
<p>This is the function I wrote : <a href="https://github.com/embeddedmz/split_a_string_of_2d_line_segments/blob/d4137c087d0c2df1917f3b57170db96d81aca3b9/mainwindow.cpp#L137" rel="nofollow noreferrer">https://github.com/embeddedmz/split_a_string_of_2d_line_segments/blob/d4137c087d0c2df1917f3b57170db96d81aca3b9/mainwindow.cpp#L137</a> 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).</p>
<p>Has anyone ever coded something like this ?</p>
<p>In my french blog post (you can translate it), I briefly describe what the algorithm is supposed to do: <a href="https://mmzoughi.wordpress.com/2022/08/22/decouper-une-chaine-de-segments-de-ligne-en-plusieurs-autres-segments-de-ligne/" rel="nofollow noreferrer">https://mmzoughi.wordpress.com/2022/08/22/decouper-une-chaine-de-segments-de-ligne-en-plusieurs-autres-segments-de-ligne/</a></p>
<p><a href="https://i.sstatic.net/kSdRo.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/kSdRo.png" alt="enter image description here" /></a></p>
<p>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) :</p>
<p><a href="https://i.sstatic.net/vO54R.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/vO54R.png" alt="enter image description here" /></a></p>

CC BY-SA 4.0
2022-08-23T18:47:17.583Z
I am not quite sure what the goal of the refinement in your blog post is. You have some sines and cosines and so on. Are you trying to refine the segments using an arc-length parametrization? What do you do about the previous points you had (the red ones)? Do the new (green) points have to coincide with the red ones sometimes, or is it enough that they have the same distance between themselves?
lightxbulb
CC BY-SA 4.0
2022-08-24T15:45:34.223Z
@lightxbulb I don't know what arc-length parametrization is. For example If I have 32 data points (colors) and only 5 line segments, I need to create 32 segments to represent all 32 data points on the path. The 5 line segments can represent a pipeline while the 32 data points correspond to 32 positions (same spacing) of this pipeline. So yes, the new green points have to coincide with the red ones. Red points can represent geo coords taken near the pipeline and collected during a survey. With the green points we will create the 32 lines of data which is the final goal. I hope I'm clear.
Aminos
CC BY-SA 4.0
2022-08-24T16:34:28.060Z
and I have corrected some incorrect information in the blog post.
Aminos
CC BY-SA 4.0
2022-08-24T17:13:59.473Z
Have you tried the code in my answer? I don't think there's a way to both have the green points be equidistant (on the line segments) and coincide with the red points, except for very specific configurations. In fact even in your example this doesn't seem to be the case: see the 4th red point and its green counterparts, they have actually flattened the corner there. On an unrelated note: arc-length here means that the green points would be equidistant on the line.
lightxbulb
CC BY-SA 4.0
2022-08-24T17:20:23.917Z
@lightxbulb I will convert your code into C++/Qt and see what it looks like. I will superimpose the two sets of points when drawing them to see the differences.
Aminos
CC BY-SA 4.0
2022-08-24T17:33:23.267Z
The code is already C++, you just need to define a struct vec2 and define vector addition, subtraction (by overloading the operators), scalar-vector multiplication, and a vector length/magnitude function.
lightxbulb
CC BY-SA 4.0
2022-08-25T10:37:48.033Z
@lightxbulb the green points will not coincide with the red points but they will be placed on the line segments formed by these red points and this is what I want. I didn't noticed it was C++, but I ll use Qt classes.
Aminos
CC BY-SA 4.0
2022-08-25T11:08:03.250Z
Sure in the code I wrote they will be placed on the line segments. This is guaranteed by the linear interpolation part `q[i] = (1-t) * p[segment_idx-1] + t * p[segment_idx];` where `t` is always in `[0,1]`. The previous expression is known as a convex linear combination in mathematics and it results in points only on the line segment with endpoints `p[segment_idx-1]` and `p[segment_idx]`. The first and last point are also placed to coincide with the red first and last ones as you wanted in your blog.
lightxbulb
<c++><2d><vectors><line><point>
Split a string of line segments into several other line segments
Aminos
# Split a string of line segments into several other line segments

(Asked by: username_0 on 2022-08-23)

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/>

[![enter image description here](https://i.sstatic.net/kSdRo.png)](https://i.sstatic.net/kSdRo.png)

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

[![enter image description here](https://i.sstatic.net/vO54R.png)](https://i.sstatic.net/vO54R.png)

**Tags:** c++, 2d, vectors, line, point

> **Comments:**
> **username_1**: I am not quite sure what the goal of the refinement in your blog post is. You have some sines and cosines and so on. Are you trying to refine the segments using an arc-length parametrization? What do you do about the previous points you had (the red ones)? Do the new (green) points have to coincide with the red ones sometimes, or is it enough that they have the same distance between themselves?  
> **username_0**: @username_1 I don't know what arc-length parametrization is. For example If I have 32 data points (colors) and only 5 line segments, I need to create 32 segments to represent all 32 data points on the path. The 5 line segments can represent a pipeline while the 32 data points correspond to 32 positions (same spacing) of this pipeline. So yes, the new green points have to coincide with the red ones. Red points can represent geo coords taken near the pipeline and collected during a survey. With the green points we will create the 32 lines of data which is the final goal. I hope I'm clear.  
> **username_0**: and I have corrected some incorrect information in the blog post.  
> **username_1**: Have you tried the code in my answer? I don't think there's a way to both have the green points be equidistant (on the line segments) and coincide with the red points, except for very specific configurations. In fact even in your example this doesn't seem to be the case: see the 4th red point and its green counterparts, they have actually flattened the corner there. On an unrelated note: arc-length here means that the green points would be equidistant on the line.  
> **username_0**: @username_1 I will convert your code into C++/Qt and see what it looks like. I will superimpose the two sets of points when drawing them to see the differences.  
> **username_1**: The code is already C++, you just need to define a struct vec2 and define vector addition, subtraction (by overloading the operators), scalar-vector multiplication, and a vector length/magnitude function.  
> **username_0**: @username_1 the green points will not coincide with the red points but they will be placed on the line segments formed by these red points and this is what I want. I didn't noticed it was C++, but I ll use Qt classes.  
> **username_1**: Sure in the code I wrote they will be placed on the line segments. This is guaranteed by the linear interpolation part `q[i] = (1-t) * p[segment_idx-1] + t * p[segment_idx];` where `t` is always in `[0,1]`. The previous expression is known as a convex linear combination in mathematics and it results in points only on the line segment with endpoints `p[segment_idx-1]` and `p[segment_idx]`. The first and last point are also placed to coincide with the red first and last ones as you wanted in your blog.  

---

## 1 answers

### Answer by username_1 on 2022-08-23. Score: 1 | Accepted answer

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

```cpp
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));
}
```

```

> **Comments:**
> **username_0**: Is length(p[i]-p[i-1]); => length(p[i], p[i-1]); ?  
> **username_0**: I mean what should it return ?  
> **username_1**: @username_0 `length(v) = sqrt(dot(v,v))`, mathematically: $\|v\| = \sqrt{(v\cdot v)}$, the `length` function here takes one vector, not two. You can instead define a distance function such that `dist(u,v) = length(u-v)=length(v-u)`.  
> **username_0**: it works really well, but there's a bug : the second last point is set to (0, 0), you can take a look at my code. I added a screenshot to my question but it doesn't include the point at (0, 0)  
> **username_0**: this is the github repo https://github.com/embeddedmz/split_a_string_of_2d_line_segments  
> **username_1**: @username_0 I didn't quite get what the bug is. What did you expect to happen and what happened instead? I saw the screenshot but that didn't really help. I don't know where (0,0) is in your image either, as there's no point of reference (e.g. coordinate system center and axes, ideally a grid).  
> **username_0**: if the output points array size is 32, the point at index 30 is (0, 0)  
> **username_1**: @username_0 You can try to output the elements of `q[i] = (1-t) * p[segment_idx-1] + t * p[segment_idx];` whenever this happens. That is print out `segment_idx`, `total_dist`, `dists[segment_idx-1]`, `dists[segment_idx]`, `t`, `p[segment_idx-1]`, `p[segment_idx-1]`. That should give you a clue whether this is a bug or not. And if it's a bug it should give you a clue what goes wrong.  
> **username_0**: when we reach the second last point and execute goto end; we will insert a final point at the end of the array q at the position m-1 but the position m-2 wasn't updated at all hence the (0,0) value. So, like I did with my code based on dot product, it's better to fill m - 2 with the the last input array point and then go beyond that point to fill the index m - 1. I think this issue is related to float computations.  
> **username_0**: this is how I fixed the issue, please look at lines 40 (declaring int outside the for loop) and the "end" label located at line 53: https://github.com/embeddedmz/split_a_string_of_2d_line_segments/blob/master/mainwindow.cpp  

---

