Finding equally spaced points given a set of points with line segments in between

Question

I'm currently programming a map, and am trying to split street segments into equal parts. If a street segment is straight it's a simple matter of dividing the length of the street segment by whatever factor you want. However, curvy streets are much harder to divide into equal parts, as they are made up of multiple segments. What I want to do is figure out a way to divide a street segment into equal points, regardless of how curvy it is, or how long each segment is. I tried parameterising the curve to get this to work, but it still doesn't work. To see what I mean by parameterizing, check this out.

At the moment, this is how I am currently implementing it.

        //street_seg_length is length of the ith street segment
        for (double j = 0.0; j < street_seg_length[i]; j+=inc) { 
        
        double rem = j - int(j);
        //A street segment can be split up into multiple curve points. 
        //The more curve points, the curvier a road is
        LatLon from = curve_points_pos[i][int(j)];
        LatLon to = curve_points_pos[i][int(j)+1];
        //Returns cartesian coordinates from latitude and longitude of nth and n+1th curve point
        double x1 = x_from_lon(from.longitude());
        double y1 = y_from_lat(from.latitude());
        double x2 = x_from_lon(to.longitude());
        double y2 = y_from_lat(to.latitude());
        //arrowX, arrowY are supposed to be the coordinates of a point between 2 curve points
        double arrowX = (1 - rem)*x1 + rem*x2;
        double arrowY = (1 - rem) * y1 + rem * y2;
        
         
         
        }
        
    }

rem is the remainder discussed in the above post, j is the same value as t in the above post, p is the nth point and q is the n+1th point discussed in the above post.

Can someone explain what I can do to achieve this or what I'm doing wrong? I want to find equally spaced points across a street segment regardless of how curvy it is. Am I following the algorithm in the linked post correctly? I believe I am but clearly the algorithm is wrong or I haven't implemented it correctly, the latter being more probable.

Answer 1

Your resulting path + will have equidistant points, but your original path o has segments of different length. You have two different things to deal with:

• the indices curr and next of the start and end points of the current segment and
• the interpolation variable t for that segment.

Here's an example of curr / next values:

o    +        0 / 1       t = 0.0
|    |
|    +        0 / 1       t = 0.667
o    |
|    +        1 / 2       t = 0.2
|    |
|    +        1 / 2       t = 0.6
|    |
o    +        1 / 2       t = 1.0

So your algorithm goes like this:

• find the overall and accumulated segment lengths;
• start with curr = 0 and next = 1.
• loop over the n equidistant points:
  • determine the overall running length z of that point
  • adjust curr and next, so that curr ≤ z ≤ next.
  • determine t and interpolate

Here's an implementation that splits a path seg into n segments of the same length. (It's not in C++, but in Javascript and it deals with (x, y) coordinates directly instead of lon/lat, but I hink you can understand it.)

function split(seg, n) {
    let acc = [];               // n + 1 accumulated lengths
    let len = 0;                // overall length
    let p = seg[0];              
    
    let res = [];               // array of n + 1 result points
    
    // find segemnt and overall lengths
    
    for (let i = 0; i < seg.length; i++) {
        let q = seg[i];
        len += Math.hypot(q.x - p.x, q.y - p.y);
        acc.push(len);

        p = q;
    }
    
    acc.push(2 * len);          // sentinel

    let curr = 0;
    let next = 1;
    
    // create equidistant result points
    
    for (let i = 0; i < n; i++) {
        let z = len * i / n;        // running length of point i
        
        // advance to current segment
        
        while (z > acc[next]) {
            curr++;
            next++;
        }
        
        // interpolate in segment
                
        let p = seg[curr];
        let q = seg[next];
        
        let t = (z - acc[curr]) / (acc[next] - acc[curr]);
        
        res.push(new Point(p.x * (1 - t) + q.x * t,
                           p.y * (1 - t) + q.y * t));
    }
    
    // push end point (leave out when joining consecutive segments.)
    
    res.push(seg[seg.length - 1]);
    
    return res;
}