Sign in to follow this  
Charles Leverett

Finding a point on a line Segment, 2D

Recommended Posts

Ok I think I got a simple question. Please keep in mind I am very rusty at math, I haven't had geometry since high school (10 years ago), no pre calc, no calc. I have 2 points, A,B and C,D. I need to know how to find a 3rd point between those points X distance From A,B. This is in 2D. Basically what I'm doing is I got 2 (space)ships, and I want ship A to move closer to ship B. I actually have an algorithm to do this, but I don't think its as accurate as it could be. Also I figure I could just keep dividing the line segment by its midpoint until I find the midpoint that is X distance from A,B, but it seems that would take too long if you have more players beyond 2. So basically I'm trying to figure out if there is a formula that I can use to figure this out.

Share this post


Link to post
Share on other sites
Quote:
Original post by Charles Leverett
Ok I think I got a simple question.
Please keep in mind I am very rusty at math, I haven't had geometry since high school (10 years ago), no pre calc, no calc.

I have 2 points, A,B and C,D.
I need to know how to find a 3rd point between those points X distance From A,B.
This is in 2D.

Basically what I'm doing is I got 2 (space)ships, and I want ship A to move closer to ship B. I actually have an algorithm to do this, but I don't think its as accurate as it could be. Also I figure I could just keep dividing the line segment by its midpoint until I find the midpoint that is X distance from A,B, but it seems that would take too long if you have more players beyond 2.
So basically I'm trying to figure out if there is a formula that I can use to figure this out.
The first step is to build a normalized (unit-length) vector pointing from (A, B) to (C, D). Once you have this vector, scale it by the desired distance and add it to the starting point - this will give you the point you're looking for.

In pseudocode (where 'p1' is the first point, 'p2' is the second point, and 'distance' is the desired distance):
// Note that this assumes that p1 and p2 are not coincident or nearly coincident:
vector p = p1 + distance * normalize(p2 - p1);

Share this post


Link to post
Share on other sites
Ok I've never dealt with vectors in a none data container way (I assume it isn't the list container we're talking about), but I've seen them mentioned many times before.

Is there a web resource I can check out on this topic?

Also I'm using PhP (web game) if that makes any difference.

Share this post


Link to post
Share on other sites
Quote:
Ok I've never dealt with vectors in a none data container way (I assume it isn't the list container we're talking about), but I've seen them mentioned many times before.
Right, in this case we're talking about a user-defined type of some sort that represents a geometric vector (e.g. x, y or x, y, z).
Quote:
Is there a web resource I can check out on this topic?
Sure, just Google 'vector math tutorial' and you should get plenty of hits.
Quote:
Also I'm using PhP (web game) if that makes any difference.
I'm not familiar enough with PhP to comment on that aspect of things specifically, but a quick look around online indicates that there are math libraries of various sorts available for PhP, so again, you might Google around a bit and see what you can find.

Share this post


Link to post
Share on other sites
Wikipedia Vectors

You can have two positions A,B and C,D but lets call them p1 and p2 that are both represented by (x, y). So point1.x corresponds to the x component of the vector. Basically normalization does (x, y) / length((x, y)) which makes the vector a length of 1 where length is sqrt(x * x + y * y). So when jyk said:

vector p = p1 + distance * normalize(p2 - p1);

What he's saying in an expanded form would be p2 - p1 is the vector starting at p1 going to p2.

vector p3;
p3.x = p2.x - p1.x;
p3.y = p2.y - p1.y;
So when subtracting vectors you simply subtract the components separately. So now we have
vector p = p1 + distance * normalize(p3);
and we know what normalize does so we can write:
vector p4;
float length = sqrt(p3.x * p3.x + p3.y * p3.y);
p4.x = p3.x / length;
p4.y = p3.y / length;
or substitute p2 - p1 into p3 and you get:
float length = sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
p4.x = (p2.x - p1.x) / length;
p4.y = (p2.y - p1.y) / length;

So you have:
vector p = p1 + distance * p4;
and a scalar * vector just multiplies each component by the scalar. So:
vector p5;
p5.x = distance * p4.x;
p5.y = distance * p4.y;
and so:
vector p = p1 + p5;
p.x = p1.x + p5.x;
p.y = p1.y + p5.y;
or if you expand everything without using tempories:

float length = sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
p.x = p1.x + distance * (p2.x - p1.x) / length;
p.y = p1.y + distance * (p2.y - p1.y) / length;

Most math libraries will simplify this problem for you by overloading operators on a class allowing you to multiply vectors and such like you would with a primitive type.

// edit yeah as JYK said there's probably a math library.

Share this post


Link to post
Share on other sites
Ok thanks for the reply guys, I think this may really help, I'll have to look it over though, but right now I need sleep. I'll let you know how it turns out.

I also found this nice little site to help explain vectors- http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1.

Once again thanks, this has been simplified to where I can understand it. I know I could probably find a math library, but I sorta like learning by building my own code so I understand what I'm doing.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this