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

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.

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

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