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

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

- determine the overall running length

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