0
$\begingroup$

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

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) :

enter image description here

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – lightxbulb
    Aug 23, 2022 at 18:47
  • $\begingroup$ @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. $\endgroup$
    – Aminos
    Aug 24, 2022 at 15:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Aug 24, 2022 at 17:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Aug 24, 2022 at 17:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Aug 25, 2022 at 11:08

1 Answer 1

1
$\begingroup$

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));
}
```
$\endgroup$
10
  • $\begingroup$ Is length(p[i]-p[i-1]); => length(p[i], p[i-1]); ? $\endgroup$
    – Aminos
    Aug 25, 2022 at 10:28
  • $\begingroup$ I mean what should it return ? $\endgroup$
    – Aminos
    Aug 25, 2022 at 10:40
  • 1
    $\begingroup$ @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). $\endgroup$
    – lightxbulb
    Aug 25, 2022 at 10:58
  • $\begingroup$ 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) $\endgroup$
    – Aminos
    Aug 26, 2022 at 16:32
  • $\begingroup$ this is the github repo github.com/embeddedmz/split_a_string_of_2d_line_segments $\endgroup$
    – Aminos
    Aug 26, 2022 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.