Given two points (x1,y1) (x2,y2), how can I compute N different points evenly lying on the line between the given points

Question

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++?

Answer 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.