Given two points (x1,y1) (x2,y2), how can I comput

问题:

I have two points and I would like to compute n evenly distributed points on top of the line created by the given line. How could I perform this in c++?

回答1:

Linear interpolation (affectionately called lerp by the Graphics community) is what you want. Given the end points it can generate the points lying in between with a parameter t.

Let the end points be A (Ax, Ay) and B (Bx, By). The vector spanning from A to B would be given by

V = B − A = <Vx, Vy>
L(t) = A + tV

This essentially means that starting from the point A, we scale the vector V with the scalar t; the point A is displaced by this scaled vector and thus the point we get depends on the value of t, the parameter. When t = 0, we get back A, if t = 1 we get B, if it's 0.5 we get the point midway between A and B.

line A----|----|----|----B
   t 0    ¼    ½    ¾    1

It works for any line (slope doesn't matter). Now coming to your problem of N stops. If you need N to be 10, then you'd have t vary by 1/N, so t = i/10, where i would be the loop iterator.

i = 0, t = 0
i = 1, t = 0.1
i = 2, t = 0.2
  ⋮
i = 9, t = 0.9
i = 10, t = 1.0

Here's one way to implement it:

#include <iostream>

struct Point {
    float x, y;
};

Point operator+ (Point const &pt1, Point const &pt2) {
    return { pt1.x + pt2.x, pt1.y + pt2.y };
}

Point operator- (Point const &pt1, Point const &pt2) {
    return { pt1.x - pt2.x, pt1.y - pt2.y };
}

Point scale(Point const &pt, float t) {
    return { pt.x * t, pt.y * t };
}

std::ostream& operator<<(std::ostream &os, Point const &pt) {
    return os << '(' << pt.x << ", " << pt.y << ')';
}

void lerp(Point const &pt1, Point const &pt2, float stops) {
    Point const v = pt2 - pt1;
    float t = 0.0f;
    for (float i = 0.0f; i <= stops; ++i) {
        t = i / stops;
        Point const p = pt1 + scale(v, t);
        std::cout << p << '\n';
    }
}

int main() {
    lerp({0.0, 0.0}, {5.0f, 5.0f}, 5.0f);
}

Output

(0, 0)
(1, 1)
(2, 2)
(3, 3)
(4, 4)
(5, 5)

Aside

Notice that on every iteration t gets incremented by Δt = 1 / N. Thus another way to update t in a loop would be

t₀ = 0
t₁ = t₀ + Δt
t₂ = t₁ + Δt
  ⋮
t₉ = t₈ + Δt
t₁₀ = t₉ + Δt

However, this isn't very parallelizable since every iteration of the loop would depend on the previous iteration.

回答2:

You can use the following give_uniform_points_between(M, N, num_points) which gives a number of #num_points points between M and N. I assume here that the line is not vertical (see below if the line can be vertical).

std::vector<Point> give_uniform_points_between(const Point& M, const Point& N, const unsigned num_points) {
   std::vector<Point> result;
   // get equation y = ax + b
    float a = (N.y - M.y) / (N.x - M.x);
    float b = N.y - a * N.x;
    float step = std::fabs(M.x - N.x) / num_points;
    for (float x = std::min(M.x, N.x); x < std::max(M.x, N.x); x += step) {
        float y = a*x+b;
        result.push_back(Point{x,y});
    }
    return result;
}

Demo : Live on Coliru

and result is :

(-3,9);(-2.3,7.6);(-1.6,6.2);(-0.9,4.8);(-0.2,3.4);(0.5,2);(1.2,0.6);(1.9,-0.8);(2.6,-2.2);(3.3,-3.6);

Explanation

From two points (x1,y1) and (x2,y2) you can guess the line equation which pass through these points.

This equation takes the form a*x + b*y + c = 0 or simply y = a*x + b if you cannot have vertical line where a = (y2 - y1) / (x2 - x1) and you deduce b as shown in the code.

Then you can just vary x or y along your line starting for the point with a minimum value coordinate.

All these (x,y) points you find are on your line and should be uniformely distributed (thanks to the fixed step).

回答3:

View the line as (x1,y1) + λ(x2-x1,y2-y1), i.e. the first point, plus a multiple of the vector between them.

When λ=0 you have the first point and when λ=1 you have the second. So you just want to take n equally distributed values of λ between 0 and 1.

How you do this depends on what you mean by between: are the end points included or not?

For example you could take λ=0/(n-1), λ=1/(n-1), λ=2/(n-1), ... λ=(n-1)/(n-1). That would give n equally distributed points including the endpoints.

Or you could take λ=1/(n+1), λ=2/(n+1), ... λ=n/(n+1). That would give n equally distributed points not including the endpoints.

回答4:

Not so mcuh math though...

vector<Rect> Utils::createReactsOnLine(Point pt1, Point pt2, int numRects, int height, int width){

    float x1 = pt1.x;
    float y1 = pt1.y;
    float x2 = pt2.x;
    float y2 = pt2.y;

    float x_range = std::abs(x2 - x1);
    float y_range = std::abs(y2 - y1);

    // Find center points of rects on the line
    float x_step_size = x_range / (float)(numRects-1);
    float y_step_size = y_range / (float)(numRects-1);

    float x_min = std::min(x1,x2);
    float y_min = std::min(x1,x2);
    float x_max = std::max(x1,x2);
    float y_max = std::max(x1,x2);

    cout << numRects <<  endl;
    float next_x = x1;
    float next_y = y1;
    cout << "Next x, y: "<< next_x << "," <<  next_y <<  endl;
    for(int i = 0; i < numRects-1; i++){
        if (x1 < x2)
            next_x = next_x + x_step_size;
        else
            next_x = next_x - x_step_size;

        if (y1 < y2)
            next_y = next_y + y_step_size;
        else
            next_y = next_y - y_step_size;

        cout << "Next x, y: "<< next_x << "," <<  next_y <<  endl;
    }
    return vector<Rect>();
}