Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Finding the Normal of a Line Segment

This thread is locked; no one can reply to it. rss feed Print
 1   2 
Finding the Normal of a Line Segment
Anomie
Member #9,403
January 2008
avatar

I've been looking around, trying to find out how to get the normal of a line segment. This has caused me quite a lot of trouble.

Every single time I've come across this stuff, I get something like:

Line1 = vector(x,y) (yes, because lines are usually defined by a single point)
Line1.normal = vector(-y,x) (again, the normal [which I've always seen represented as a ray or line perpendicular to the original line segment] defined magically by a single vector)

This all seems to be perfectly normal to everyone but me...so I fear I'm just being a massively dense dunderbum, but I can't find anything suggesting that this isn't how it appears.

Sorry if I sound a little frustrated, but I am. I guess it's just because it seems so incredibly simple, and yet fundamentally takes a neat little origami-crap on what I know of geometry. ( an origami-crap juuust big enough to keep me from doing what I need to do )

I really, really didn't want to resort to asking this here, but I'm about to flip my wig. Quick and easy answer? Anyone?

Thanks in advance.

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

FrankyR
Member #243
April 2000
avatar

A vector can be visualized as the line connecting the origin (0,0) and the co-ordinates specified by the vector.

So, if you have a line segment, then you need to use the 'slope' of the segment to calculate the normal. A normal is a single vector because its position doesn't matter; only its direction matters. If you want to draw the normal (N), choose any starting point you want, say P, and draw a line from P to P+N.

(I hope that made sense)

Anomie
Member #9,403
January 2008
avatar

Oooo that makes sense!

But the only way I know of to find slope is:
slope = deltaY/deltaX

Which gives me a single number, making normal = (-y,x) Not really applicable.

Is there a different way I should be getting the slope, leaving me with a vector?

[edit]Unless I should just be using deltaX and deltaY as my (x,y) for the line?

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

FrankyR
Member #243
April 2000
avatar

Quote:

But the only way I know of to find slope is:
slope = deltaY/deltaX

I guess by slope I meant (deltaX, deltaY), so your normal is (-deltaY, deltaX)

Anomie
Member #9,403
January 2008
avatar

Alright, cool.

I thought this would fix my problems, but it hasn't... I think my problem is that I need the dot product of N (normal) and V (movement vector of a point colliding with the line segment), but the issue is that I'm not using vectors for anything. Can I do this with normal floats?

[edit]I'm working from the bottom of this page. All of the (simple) math is using vectors, and I'm having a hard time working through them with floats.

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

Indeterminatus
Member #737
November 2000
avatar

This seems to be a problem you have with vector math in general, right? The page you linked would have left me totally blank, hadn't I already known all the vector stuff, so there's no need to reference to yourself as "massively dense dunderbum". I recommend catching up to the basics of vector math before even trying to understand the article. When you've got the basics down, return to it.

_______________________________
Indeterminatus. [Atomic Butcher]
si tacuisses, philosophus mansisses

Anomie
Member #9,403
January 2008
avatar

I'm not sure it's a problem with vector math that I have, so much as a problem implementing vector math without vectors...

Unless vectors are treated differently than two pair'd numbers?

Would I be wrong saying something like... Vector1(4,6) + Vector2(2,1) = (6,7)?

[edit] Before, I didn't mean that I had trouble figuring out how to get the dot product...I know how to get it, but it's giving me crazy values if I work through it without vectors.

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

SiegeLord
Member #7,827
October 2006
avatar

Quote:

Unless vectors are treated differently than two pair'd numbers?

They are not, because that is what vectors are. The operations you do on them a well defined.

Quote:

Would I be wrong saying something like... Vector1(4,6) + Vector2(2,1) = (6,7)?

That would be correct.

Quote:

I'm not using vectors for anything. Can I do this with normal floats?

Remedy this situation. If you are using vector math and you are using C++, you should not be implementing your vector math as naked floats.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Anomie
Member #9,403
January 2008
avatar

Alright...maybe I should just throw some code up then.

The Vn = [N.V]N is the part I'm having trouble with.

  float norm_x = (end->y - start->y) * -1;
  float norm_y = end->x - start->x;

//  This bit's iffy...  I need a vector for the normal veloctiy, found with [N.V]N
  float norm_x_vel = (norm_x*(pnt.x_vel/2) + norm_y*(pnt.y_vel/2)) * norm_x;
  float norm_y_vel = (norm_x*(pnt.x_vel/2) + norm_y*(pnt.y_vel/2)) * norm_y;

  float tan_x_vel = (pnt.x_vel/2) - norm_x_vel;
  float tan_y_vel = (pnt.y_vel/2) - norm_y_vel;

  float res = 1.0f;

  pnt.x_vel = (tan_x_vel - res*norm_x_vel);
  pnt.y_vel = (tan_y_vel - res*norm_y_vel);

I'm getting values of ~750 from norm_x_vel/norm_y_vel. But this is closer than what I had before. (sometimes as high as ~70,000)

[edit] As soon as this is done, I'll have accomplished what I set out to accomplish, and I'll need no more vector math. (until I start something new, o' course)

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

SiegeLord
Member #7,827
October 2006
avatar

The normal vector is by definition of length = 1.

Put this after your calculate norm_x and norm_y:

float norm_x = (end->y - start->y) * -1;
float norm_y = end->x - start->x;

float norm_length = sqrt(norm_x * norm_x + norm_y * norm_y);

//probably do a check to see that normal vector is not of length = 0

//normalize the normal vector
norm_x /= norm_length;
norm_y /= norm_length;

//the rest of your code...

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

gnolam
Member #2,030
March 2002
avatar

SiegeLord said:

The normal vector is by definition of length = 1.

No. That's a normalized vector, not a normal vector. Not the same thing. It's often handy to keep your normals normalized, but they don't have to be.

--
Move to the Democratic People's Republic of Vivendi Universal (formerly known as Sweden) - officially democracy- and privacy-free since 2008-06-18!

Anomie
Member #9,403
January 2008
avatar

Good to know! That helped a lot. It's still acting a bit funny though... Is the rest of my math right?

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

SiegeLord
Member #7,827
October 2006
avatar

Quote:

No. That's a normalized vector, not a normal vector. Not the same thing. It's often handy to keep your normals normalized, but they don't have to be.

I stand corrected.

The website you are using, Anomie, is wrong (they never mentioned what type of a normal vector they seek directly) so technically it wasn't your mistake... but still if you knew how vectors work you'd see this error rather quickly.

Quote:

It's still acting a bit funny though... Is the rest of my math right?

It looks okay to me...

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

james_lohr
Member #1,947
February 2002

Quote:

// This bit's iffy... I need a vector for the normal veloctiy, found with [N.V]N
float norm_x_vel = (norm_x*(pnt.x_vel/2) + norm_y*(pnt.y_vel/2)) * norm_x;
float norm_y_vel = (norm_x*(pnt.x_vel/2) + norm_y*(pnt.y_vel/2)) * norm_y;

I'm not sure what you are trying to do here.

With regards to collisions, there are two totally different ways of modeling them:

The first is with a single instantaneous contact. You determine when and where the collision happened, and you place the point accordingly with its velocity reflected about the surface normal. You can make this more realistic by artificially adding a contact time, friction, spin etc. This is probably the wrong method for your purposes if you're attempting what I think you are...

The second method (which I consider far more elegant) is to model the collision as an acceleration of the point along the normal of the line segment. You're effectively creating a little spring during the contact time. The beauty of this approach is that rebound (reflection about the normal) is a natural consequence of the fact that you're only accelerating the point in the direction of the normal. The difficulty, however, is that if you're using a point (instead of a circle), the point will have to pass through the line segment (imagine the line segment is elastic, and the point stretches it a bit before rebounding). You can set the acceleration to something like <math>-kx^3</math> if you want the line segment to be a hard surface (where x is the displacement of the point from the line along the line segment normal).

I did write a little demo many years ago which might be handy for you if I could just find it...

[edit]

Hehe, that's cute. I couldn't find it, but it seems someone cloned it for me, which is definitely a good thing if you knew what my code looked like back then ;D SnookerClone.

Anomie
Member #9,403
January 2008
avatar

Quote:

I'm not sure what you are trying to do here.

I'm trying to do the 'Vn = [N.V]N' part of what's on that Gamasutra page, without any vectors. The idea was to break it into x_vel and y_vel...but I sure wouldn't bet money that I'm doing it right.

I'm all about elegance. The Gamasutra article was the only information I could find on collision response that wasn't specific to polygons or spheres, so I went with it. So how would I go about implementing your second method there? (all of my line segments are totally rigid, when it comes to collision)

[edit]Waithuh... Accelerate the particle by some degree in the direction of the normal... Of course!
[edit2] Okay...not as simple as I thought... Help?

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

james_lohr
Member #1,947
February 2002

Quote:

I'm trying to do the 'Vn = [N.V]N' part of what's on that Gamasutra page, without any vectors. The idea was to break it into x_vel and y_vel...but I sure wouldn't bet money that I'm doing it right.

The article is describing my first solution, but the formula is just plain wrong a bit misleading because it doesn't point out that the normal is normalized. You could do it something like this:

1 
2u.x = line_seg.x2-line_seg.x1;
3u.y = line_seg.y2-line_seg.y1;
4 
5u.unit_vect(); //u is the unit vector in the direction of the line
6 
7v.x = -u.y; //v is the unit vector perpendicular to the line segment (i.e. normalized normal)
8v.y = u.x;
9 
10 
11 
12Vu = dot_product(point_velocity,u); //resolve point velocity along line
13Vv = dot_product(point_velocity,v); //resolve point velocity along normal
14 
15point_velocity.x = Vu * u.x - Kr * Vv * v.x; //sum components, reversing component along the normal
16point_velocity.y = Vu * u.y - Kr * Vv * v.y; //Kr = coefficient of rest.

note: my functions are just pseudo code, but you should get the idea.

SiegeLord
Member #7,827
October 2006
avatar

Aside from their normal vector gaffe, their formulas are fine (although I do agree that your second method is much better).

Get the unit normal vector to the line: N

Resolve the velocity along this normal vector: Vn = (V dot N) * N

Get the tangential velocity: Vt = V - Vn

Final velocity = Vt - Vn * K

Quote:

Vu = dot_product(point_velocity,u);


Since when does a dot product return a vector? Pseudo-code or not, that is completely wrong.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Anomie
Member #9,403
January 2008
avatar

Looking at it now, I think my problems might be from my collision detection stuff... As the particle's velocity decreases, it's more and more likely to pass through the line segment. (which is the problem I'm having, sorry for not mentioning that before)

Attached Win32 binary, for your viewing pleasure.

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

james_lohr
Member #1,947
February 2002

Quote:

Since when does a dot product return a vector? Pseudo-code or not, that is completely wrong.

They are not vectors, they are the magnitude of the vectors resolved in the directions u and v (sorry, there was an error in my code).

Quote:

Aside from their normal vector gaffe, their formulas are fine

Yeah true, "The relative velocity of the two bodies is checked by calculating N • V" was a bit misleading though, but I suppose the wording is actually correct since it's referring to a plane and not a line segment (relative velocity of a point with a stationary line segment would just be the magnitude of the velocity of the point). So yeah, it's exactly the same as my code, except that I waste time calculating two dot products (more intuitive) instead of one.

[edit]

Quote:

Looking at it now, I think my problems might be from my collision detection stuff... As the particle's velocity decreases, it's more and more likely to pass through the line segment. (which is the problem I'm having, sorry for not mentioning that before)

Are you applying gravity before or after the collision? - because if you're doing the collisions first, then eventually it's going to fall through.

Otherwise you can just make it impossible for the point to ever cross the line: if it does, place it on the line (you should know how to check if it has crossed the line).

Anomie
Member #9,403
January 2008
avatar

I'm applying gravity before the collision stuff, but...I think it's important that I work out what's wrong, rather than brute-force my way around the problem... All I'm doing is your direction test, and if it changes sign, register a collision. (also making sure the point lies within the area of the line)

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

james_lohr
Member #1,947
February 2002

Quote:

All I'm doing is your direction test, and if it changes sign, register a collision.

So, before moving a point, you are checking if its new location cases a sign change. If it does, you're not moving it forward but instead registering a collision?

Quote:

I think it's important that I work out what's wrong

You're trying to find the equilibrium of a point (infinitely small) resting on a line (infinitely thin) - it's not exactly the most robust thing for a numerical integrator to model. Think about when the point is exactly on the line and stationary (this is what it's going to tend towards not counting floating point errors and the application of gravity with each step). As it reaches this equilibrium, it just needs a tiny floating point rounding error for the point to end up on the wrong side of the line.

You'll need to build in some sort of robustness yourself, or change what you are modeling (a circle colliding with a line, or a point colliding with a polygon).

Trezker
Member #1,739
December 2001
avatar

Here comes a little function I cooked up. I think it works as it should.
It should return the vector that should be added to the colliding object's velocity if it doesn't loose any in the bounce.

Who has a better function?

1/*
2s1, e1 = endpoints of traveling object
3s2, e2 = endpoints of static line
4*/
5Vector Project_collision_vector(const Vector& s1, const Vector& e1, const Vector& s2, const Vector& e2)
6{
7 Vector line_direction = e2-s2;
8 Vector line_normal(-line_direction.Y(), line_direction.X());
9 line_normal.Normalize();
10 Vector hypotenuse = e1-s1;
11 float hypotenuse_length = hypotenuse.Length();
12 hypotenuse.Normalize();
13
14 float angle = acos(hypotenuse.Dotproduct(line_normal));
15 
16 float length = cos(angle) * hypotenuse_length;
17 
18 Vector force;
19 force-=line_normal;
20 return force*length*2;
21}

Slartibartfast
Member #8,789
June 2007
avatar

james_lohr
Member #1,947
February 2002

Quote:

float angle = acos(hypotenuse.Dotproduct(line_normal));

float length = cos(angle) * hypotenuse_length;

::) - I'll let you spot the redundancy :P

Trezker
Member #1,739
December 2001
avatar

float length = hypotenuse.Dotproduct(line_normal) * hypotenuse_length;

Do I get a gold star?

Anything else? Maybe a completely different approach that's faster even?

 1   2 


Go to: