使用C ++将曲线重新采样为等长段

Question

使用C ++将曲线重新采样为等长段

8

如何使用C++将曲线重新采样为等长段？我有一组表示2D曲线的点。在下面的示例中，我有一个带有x和y分量的点结构体和一个包含测试位置的点向量。每对点表示曲线上的一个段落。重新采样曲线的示例如下所示。红色圆圈是原始位置，绿色圆圈是重新采样后的目标位置。

struct Point
{
    float x, y;
};


std::vector<Point> Points;
int numPoints = 5;

float positions[] = {
0.0350462,  -0.0589667,
0.0688311,  0.240896,
0.067369,   0.557199,
-0.024258,  0.715255,
0.0533231,  0.948694,
};

// Add points
int offset = 2;
for (int i =0; i < numPoints; i++)
{
    offset = i * 2;
    Point pt;
    pt.x = positions[offset];
    pt.y = positions[offset+1];
    Points.push_back(pt);

}

- sabotage3d

执行插值的最佳方法取决于您的数据性质以及您需要多么精确。我建议从谷歌搜索线性插值和样条插值开始，看看它们是否能满足您的需求。 - RyanP

你正在使用哪本关于计算机图形学的书来学习这个主题？ - Lightness Races in Orbit

如果我按边缘重新采样，只需将当前点位移或lerp到下一个点就很容易了。我想不出如何对整个曲线执行此操作。 - sabotage3d

你可以使用b样条或Bézier曲线，例如。 - Bob__

它不是样条曲线或贝塞尔曲线，仍然是多边形曲线。我添加了图片以更好地描述问题。 - sabotage3d

2

在这些图像中，重新采样的连续点似乎沿着源的线性插值以相同的距离分隔，然而这些点之间的欧几里得距离却不同，因为源中更“弯曲”的部分会产生结果中较短的线段。你是要求这个吗？还是希望结果中所有连续点等距分布？ - Christopher Oicles

2个回答

1

对于沿着折线等距分布的绿色点：

第一次运行：遍历点列表，计算每个线段的长度和当前点之前的累积长度。伪代码：

cumlen[0] = 0;
for (int i=1; i < numPoints; i++) {
   len = Sqrt((Point[i].x - Point[i-1].x)^2 + (Point[i].y - Point [i-1].y)^2)
   cumlen[i] = cumlen[i-1] + len; 
}

现在找到每个新片段的长度。

plen = cumlen[numpoints-1] / numpieces;

现在进行第二次运行 - 遍历点列表并将新点插入到适当的段中。

i = 0;
for (ip=0; ip<numpieces; ip++) {
   curr = plen * ip;
   while cumlen[i+1] < curr
     i++;
   P[ip].x = Points[i].x + (curr - cumlen[i]) * (Points[i+1].x - Points[i].x) / 
                            (cumlen[i+1] - cumlen[i]);
    ..the same for y
}

numpieces > numPoints和numpieces <= numPoints的实际输出示例

- MBo

伪代码中有些问题，我无法使其正常工作。如果我们想要减少原始段的数量，这种方法是否可行？ - sabotage3d

将代码更改为 while cumlen[i+1]。如果 numpieces<numPoints，则该方法应该有效。 - MBo

抱歉，我不理解最后一句话。在我的实现中，新的点（圆）位于旧线段上。 - MBo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Christopher Oicles · Accepted Answer

看看这个是否适合你。重新采样的点在源向量点的线性插值上彼此等距。

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>

struct Point {
    double x, y;
};

// Distance gives the Euclidean distance between two Points
double Distance(const Point& a, const Point& b) {
    const double dx = b.x - a.x;
    const double dy = b.y - a.y;
    const double lsq = dx*dx + dy*dy;
    return std::sqrt(lsq);
}

// LinearCurveLength calculates the total length of the linear
// interpolation through a vector of Points.  It is the sum of
// the Euclidean distances between all consecutive points in
// the vector.
double LinearCurveLength(std::vector<Point> const &points) {
    auto start = points.begin();
    if(start == points.end()) return 0;
    auto finish = start + 1;
    double sum = 0;
    while(finish != points.end()) {
        sum += Distance(*start, *finish);
        start = finish++;
    }
    return sum;
}

// Gives a vector of Points which are sampled as equally-spaced segments
// taken along the linear interpolation between points in the source.
// In general, consecutive points in the result will not be equidistant,
// because of a corner-cutting effect.
std::vector<Point> UniformLinearInterpolation(std::vector<Point> const &source, std::size_t target_count) {
    std::vector<Point> result;
    if(source.size() < 2 || target_count < 2) {
        // degenerate source vector or target_count value
        // for simplicity, this returns an empty result
        // but special cases may be handled when appropriate for the application
        return result;
    }
    // total_length is the total length along a linear interpolation
    // of the source points.
    const double total_length = LinearCurveLength(source);

    // segment_length is the length between result points, taken as
    // distance traveled between these points on a linear interpolation
    // of the source points.  The actual Euclidean distance between
    // points in the result vector can vary, and is always less than
    // or equal to segment_length.
    const double segment_length = total_length / (target_count - 1);

    // start and finish are the current source segment's endpoints
    auto start = source.begin();
    auto finish = start + 1;

    // src_segment_offset is the distance along a linear interpolation
    // of the source curve from its first point to the start of the current
    // source segment.
    double src_segment_offset = 0;

    // src_segment_length is the length of a line connecting the current
    // source segment's start and finish points.
    double src_segment_length = Distance(*start, *finish);

    // The first point in the result is the same as the first point
    // in the source.
    result.push_back(*start);

    for(std::size_t i=1; i<target_count-1; ++i) {
        // next_offset is the distance along a linear interpolation
        // of the source curve from its beginning to the location
        // of the i'th point in the result.
        // segment_length is multiplied by i here because iteratively
        // adding segment_length could accumulate error.
        const double next_offset = segment_length * i;

        // Check if next_offset lies inside the current source segment.
        // If not, move to the next source segment and update the
        // source segment offset and length variables.
        while(src_segment_offset + src_segment_length < next_offset) {
            src_segment_offset += src_segment_length;
            start = finish++;
            src_segment_length = Distance(*start, *finish);
        }
        // part_offset is the distance into the current source segment
        // associated with the i'th point's offset.
        const double part_offset = next_offset - src_segment_offset;

        // part_ratio is part_offset's normalized distance into the 
        // source segment. Its value is between 0 and 1,
        // where 0 locates the next point at "start" and 1
        // locates it at "finish".  In-between values represent a
        // weighted location between these two extremes.
        const double part_ratio = part_offset / src_segment_length;

        // Use part_ratio to calculate the next point's components
        // as weighted averages of components of the current
        // source segment's points.
        result.push_back({
            start->x + part_ratio * (finish->x - start->x),
            start->y + part_ratio * (finish->y - start->y)
        });
    }

    // The first and last points of the result are exactly
    // the same as the first and last points from the input,
    // so the iterated calculation above skips calculating
    // the last point in the result, which is instead copied
    // directly from the source vector here.
    result.push_back(source.back());
    return result;
}

int main() {
    std::vector<Point> points = {
        { 0.0350462,  -0.0589667},
        { 0.0688311,   0.240896 },
        { 0.067369,    0.557199 },
        {-0.024258,    0.715255 },
        { 0.0533231,   0.948694 }
    };

    std::cout << "Source Points:\n";
    for(const auto& point : points) {
        std::cout << std::setw(14) << point.x << "    " << std::setw(14) << point.y << '\n';
    }
    std::cout << '\n';
    auto interpolated = UniformLinearInterpolation(points, 7);
    std::cout << "Interpolated Points:\n";
    for(const auto& point : interpolated) {
        std::cout << std::setw(14) << point.x << "    " << std::setw(14) << point.y << '\n';
    }
    std::cout << '\n';
    std::cout << "Source linear interpolated length:           " << LinearCurveLength(points) << '\n';
    std::cout << "Interpolation's linear interpolated length:  " << LinearCurveLength(interpolated) << '\n';
}