PDA

View Full Version : Finding a point (x,y) between two other points.



cutting_crew
08-21-2008, 09:20 AM
i would like to find out what is the general formula of finding a point in between(and not necessarily in the middle) of 2 other random points.

i am using this to test for 2D line intersections and need this.

lets say i have a point (3.5, -1) and the next point i have is (1, 3), moving clockwise.

i know that the line crossed at the y-axis at 0 at some point. what i need to find out is what the x value at this point should be.

point x1:(3.5, -1)

point x3:(???, 0) what is the value of x?

point x2(1, 3)


thanks!!

PaladinOfKaos
08-21-2008, 09:45 AM
You can find the slope of the line between x1 and x2, then use that to calculate the X value of x3 based on the given Y value.

(I'm gonna use A,B,C to represent your x1, x2, and x3, to avoid confusion in the code)


slope = (B.y - A.y) / (B.x - A.x);
delta_y = C.y - A.y;
delta_x = delta_y / slope;
C.x = A.x + delta_x;


Optimizing to get rid of a division (we find the inverse slope rather than the slope, so we can multiply instead of divide later):


inv_slope = (B.x - A.x) / (B.y - A.y);
delta_y = C.y - A.y;
delta_x = delta_y * inv_slope
C.x = A.x + delta_x;


There may be more optimizations you can do to make it run faster, but that's the basic algorithm.

cutting_crew
08-21-2008, 10:44 AM
You can find the slope of the line between x1 and x2, then use that to calculate the X value of x3 based on the given Y value.

(I'm gonna use A,B,C to represent your x1, x2, and x3, to avoid confusion in the code)


slope = (B.y - A.y) / (B.x - A.x);
delta_y = C.y - A.y;
delta_x = delta_y / slope;
C.x = A.x + delta_x;


Optimizing to get rid of a division (we find the inverse slope rather than the slope, so we can multiply instead of divide later):


inv_slope = (B.x - A.x) / (B.y - A.y);
delta_y = C.y - A.y;
delta_x = delta_y * inv_slope
C.x = A.x + delta_x;


There may be more optimizations you can do to make it run faster, but that's the basic algorithm.

thanks for the quick response. in contrast, if you know the x value and you need to get the Y value it would be:



inv_slope = (B.y - A.y) / (B.x - A.x);
delta_x = C.x - A.x;
delta_y = delta_x * inv_slope
C.y = A.y + delta_y;


does this look correct???

PaladinOfKaos
08-21-2008, 10:54 AM
your math is correct, but when finding Y the first thing you compute is the slope rather than the inverse slope. Your variable is named wrong. It won't affect program execution, but it could cause confusion later on in life.

cutting_crew
08-21-2008, 10:59 AM
your math is correct, but when finding Y the first thing you compute is the slope rather than the inverse slope. Your variable is named wrong. It won't affect program execution, but it could cause confusion later on in life.

ok so just compute -> inv_slope = (B.x - A.x) / (B.y - A.y);

this way whether finding x or y yes?

PaladinOfKaos
08-21-2008, 11:05 AM
For X:

inv_slope = (B.x - A.x) / (B.y - A.y);
delta_y = C.y - A.y;
delta_x = delta_y * inv_slope;
C.x = delta_x + A.x;

For Y:

slope = (B.y - A.y) / (B.x - A.x);
delta_x = C.x - A.x;
delta_y = delta_x * slope;
C.y = delta_y + A.y

In the X version of the algorithm, you calculate the inverse slope - that is 1/slope, or dX/dY. Hence the variable is named "inv_slope". In the Y version, you find the slope (dY/dX), so it's simply samed "slope". The wikipedia article on Slope might be a bit more descriptive than I'm being: http://en.wikipedia.org/wiki/Slope

cutting_crew
08-21-2008, 11:27 AM
For X:

inv_slope = (B.x - A.x) / (B.y - A.y);
delta_y = C.y - A.y;
delta_x = delta_y * inv_slope;
C.x = delta_x + A.x;

For Y:

slope = (B.y - A.y) / (B.x - A.x);
delta_x = C.x - A.x;
delta_y = delta_x * slope;
C.y = delta_y + A.y

In the X version of the algorithm, you calculate the inverse slope - that is 1/slope, or dX/dY. Hence the variable is named "inv_slope". In the Y version, you find the slope (dY/dX), so it's simply samed "slope". The wikipedia article on Slope might be a bit more descriptive than I'm being: http://en.wikipedia.org/wiki/Slope

ok thanks! sorry for the confusion. ive worked it out onpaper and it seems to work :)

Rosario Leonardi
08-25-2008, 01:22 PM
another algorithm can be the linear interpolation.

in vec2 A;
in vec2 B;

float alpha;

// for X
alpha = (C.x-A.x)/(B.x-A.x)
// for Y
alpha = (C.y-A.y)/(B.y-A.y)

vec2 C = A + alpha * (B - A)

Remember to check that the input point should be inside the bound [A, B].
Remember to handle the two special cases slope = infinite and slope = 0 (B.x == A.x and B.y == B.a)