
This thread is locked; no one can reply to it. 
1
2

Finding the Normal of a Line Segment 
Anomie
Member #9,403
January 2008

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)} 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 origamicrap on what I know of geometry. ( an origamicrap 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. ______________ 
FrankyR
Member #243
April 2000

A vector can be visualized as the line connecting the origin (0,0) and the coordinates 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

Oooo that makes sense! But the only way I know of to find slope is: 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? ______________ 
FrankyR
Member #243
April 2000

Quote:
But the only way I know of to find slope is: I guess by slope I meant (deltaX, deltaY), so your normal is (deltaY, deltaX) 
Anomie
Member #9,403
January 2008

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. ______________ 
Indeterminatus
Member #737
November 2000

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. _______________________________ 
Anomie
Member #9,403
January 2008

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. ______________ 
SiegeLord
Member #7,827
October 2006

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 
Anomie
Member #9,403
January 2008

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) ______________ 
SiegeLord
Member #7,827
October 2006

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 
gnolam
Member #2,030
March 2002

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.  
Anomie
Member #9,403
January 2008

Good to know! That helped a lot. It's still acting a bit funny though... Is the rest of my math right? ______________ 
SiegeLord
Member #7,827
October 2006

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

Anomie
Member #9,403
January 2008

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! ______________ 
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
note: my functions are just pseudo code, but you should get the idea.

SiegeLord
Member #7,827
October 2006

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);
"For in much wisdom is much grief: and he that increases knowledge increases sorrow."Ecclesiastes 1:18 
Anomie
Member #9,403
January 2008

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. ______________ 
james_lohr
Member #1,947
February 2002

Quote: Since when does a dot product return a vector? Pseudocode 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

I'm applying gravity before the collision stuff, but...I think it's important that I work out what's wrong, rather than bruteforce 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) ______________ 
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

Here comes a little function I cooked up. I think it works as it should. Who has a better function?

Slartibartfast
Member #8,789
June 2007

(without reading all of the thread) Rotate by Pi/4?  
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

Trezker
Member #1,739
December 2001

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
