3

I have 2 points X,Y (for example [5,10] and [20,30]) and I need to interpolate points between these 2 points in order that all this points are spaced by 1 measurement unit.

Let's pretend I am using cm (as my measurement unit) and I have a point at [5,10] and another at [20,30]. How can I know the first point in this interpolation so it's spaced only 1cm from [5,10]? Walking 1cm each step, I would like to know every coordinate of points till I reach the last point [20,30].

Amanda Novaes
  • 33
  • Do you know what kind of interpolation it is? Is it linear or not? – Jam Sep 08 '16 at 01:54
  • Sure, it's linear. I want equally spaced points in the straight line between 2 points – Amanda Novaes Sep 08 '16 at 01:58
  • In your example, the points $X$ and $Y$ are exactly $25$ units apart so it is possible to interpolate $24$ points between them at exactly $1$ unit between each pair of points. But if $X=(5,10)$ and $Y=(25,30)$ then the distance between $X$ and $Y$ is $20\sqrt2$, which cannot be divided into intervals of exactly $1$ unit. What do you want to do then? – David K Sep 08 '16 at 02:06
  • @David K in that case I would like that the first and N-1 points get spaced by maximum of 1 unit. The last two poinsts can be spaced in less than 1 unit, no problem. I just would like to know how to know the next point from [5,10] that is 1 unit spaced from it and is inside the line that connects the first and last point. – Amanda Novaes Sep 08 '16 at 02:08
  • That's a clear and consistent statement of the problem, so I have based an answer on it. – David K Sep 08 '16 at 02:27

3 Answers3

3

Given two points $A$ and $B$, this answer will put points on the line segment between $A$ and $B$ so that the first point is $1$ unit from $A$, the second point is $2$ units from $A$, and so forth until the last point, which is a whole number of units from $A$ and one unit or less from $B$.

Suppose the Cartesian $(x,y)$ coordinates of the points are $A = (x_A, y_A)$ and $B = (x_B, y_B)$. Let $d$ be the distance between these two points; by the Pythagorean Theorem, $$d = \sqrt{(x_A - x_B)^2 + (y_A - y_B)^2}.$$

Since $B$ is at a distance $d$ from $A$, to move $d$ units from $A$ toward $B$ we add $x_B - x_A$ to $x_A$ and $y_B - y_A$ to $y_A$ to get the new $(x,y)$ coordinates. To move just $1$ unit we want to move $\frac1d$ times as far, that is, the point $1$ unit from $A$ is $(x_1,y_1)$ where \begin{align} x_1 = x_A + \frac1d(x_B - x_A),\\ y_1 = y_A + \frac1d(y_B - y_A). \end{align} The next point is at $\frac2d$ of the distance from $A$ to $B$, the next at $\frac3d$ the distance, and so forth. In general the $n$th point that we place along the segment from $A$ to $B$ should be at coordinates $(x_n,y_n)$ where \begin{align} x_n = x_A + \frac nd(x_B - x_A),\\ y_n = y_A + \frac nd(y_B - y_A). \end{align} We do this for each integer $n$ such that $1 \leq n < d$.

David K
  • 98,388
0

The line between $(5,10)$ and $(20,30)$ is $y=\frac{10-30}{5-20}(x-5)+10$ and the distance between the points is $\sqrt{(5-20)^2+(10-30)^2}=25$, so your problem reduces to putting points on the line at $1$ point per unit for $25$ units. Clearly this means putting down $24$ points.

I'll show you how you can find the first point. Since it's $1$ unit away from $(5,10)$, we can call it $(x,y)$ and say $\sqrt{(x-5)^2+(y-10)^2}=1$. We can then use our equation for the line and substitute to say $\sqrt{(x-5)^2+\left[(\frac{4}{3}(x-5)+10)-10)^2\right]}=1$, which you can easily solve for $x$ with a bit of algebra. I'm sure you can do the rest by yourself.

Jam
  • 10,325
  • I appreciate your attention and your method is good but I only accepted the other answer cause it shows me how to how the Nth point more easily with a single line of equation. Thank you man! – Amanda Novaes Sep 08 '16 at 02:31
0

The other answers are fine but I prefer to use more affine formalism.

In an affine space, we can see a point as the result of the external operation point + vector = point. The points you are searching are the chain of results starting from A and adding a vector colinear to XY and , as stated, of length 1.

Then, here, we have to compute the vector XY and to divide it by its norm to get a length of one unit. For convenience, let's rename X and Y : A and B.

$\vec {AB} = \vec {( B_x - A_x, B_y - A_y )}$

vector $norm(\vec {AB} ) = (( B_x - A_x )^2 + ( B_y - A_y )^2)^{1/2}$

Then our unit vector on the line is

$\vec u = \vec {( \frac{B_x - A_x}{(( B_x - A_x )^2 + ( B_y - A_y )^2)^{1/2}}, \frac{B_y - A_y}{(( B_x - A_x )^2 + ( B_y - A_y )^2)^{1/2}} )}$

To get the next point from the current point , you add $\vec u$ until you stop on or else after the target.

Remains a last question : will the target be in these steps or between 2 stop points ? Merely, its depends of the length of AB ( the original XY ) : it will be fine only if the length may be expressed by an integer times the length unit.

Finally, the searched points are $ P_0 = A$ , $P_1 = A + \vec u$ , $P_{12} = A + 12 * \vec u$ , etc

Application with $A_x=5 , Ay=10 , B_x = 20$ and $B_y = 30$ :

  • $norm(\vec {AB} ) = (( B_x - A_x )^2 + ( B_y - A_y )^2)^{1/2} = (( 20 - 5 )^2 + ( 30 - 10 )^2)^{1/2} = 25$ which is an integer. Fine, the target will be reached exactly.

  • $\vec u = \vec {( \frac{B_x - A_x}{25}, \frac{B_y - A_y}{25} )} = \vec {( \frac{15}{25}, \frac{20}{25} )} = \vec {( \frac{3}{5}, \frac{4}{5} )}$

  • and finaly compute the points with the point + vector operation. For example $P_{12} = A + 12 * \vec u = (5,10) + \vec {( \frac{12 \times 3}{5}, \frac{12 \times 4}{5} )} = (5+\frac{12 \times 3}{5},10+\frac{12 \times 4}{5}) $