给定一组点，中间有线段，求相等间隔的点

Question

我目前正在编写地图，并试图将街道段分成相等的部分。如果一段街道是直的，很简单，就是用街道的长度除以任何你想要的因子。然而，弯曲的街道很难划分成相等的部分，因为它们由多个部分组成。我想要做的是找出一种方法，把一段街道分成相等的点，不管它有多弯曲，也不管每段有多长。我试着对曲线进行参数化，但还是不行。要了解我所说的参数化是什么意思，请查看以下内容。

目前，这是我目前如何实现它。

//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为上文中讨论的余数，j与上文中讨论的t相同，p为第n个点，q为上文中讨论的第n+1个点。

有人能解释一下我能做些什么来实现这个目标，或者我做错了什么吗?我想在街道上找到等间隔的点不管它有多弯曲。我在链接的帖子正确遵循算法吗?我相信我是，但很明显，算法是错误的，或者我没有正确地实现它，后者更有可能。

Answer 1

结果路径+将具有等距点，但原始路径o具有不同长度的段。您有两件不同的事情要处理:

• 当前段起始点和结束点的curr和next指数和
• 该段的插值变量t。

下面是curr / next值的一个示例:

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

你的算法是这样的:

• 查找总长度和累计长度;
• 从curr = 0和next = 1开始
• 在n个等距点上循环:
  • 确定该点的总运行长度z
  • 调整curr和next，使curr ≤ z ≤ next.
  • 确定t并插入

这是一个将路径seg拆分为相同长度的n段的实现。(它不是在c++中，而是在Javascript中，它直接处理(x, y)坐标而不是lon/lat，但我认为你可以理解它。)

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