Maths vector problem

It's been a while since I've done this sort of thing, and I'm struggling.

In 2D, I want to detect when a point (p3) is on the wrong side of a line/ray (p1-p2) and move it 'n' units into the 'correct' side of the line. See the diagram below:


I suspect it will need the 2D equivalent of the plane equation, and maybe an intersection point.

Anyone have any code to do this? Any help much appreciated.

I could do this if I knew exactly what is wanted.

We need one unambiguous example. Put p1 at the origin, so p1 = (0,0).
Put p2 somewhere on the positive x-axis, let's say p2 = (5,0).

For p3 we can use ( +3,0 ) or ( -3,0 ). One of them is on the 'wrong' side. Which one?

Now tell me what 'n units' means and where p3 will be after moving it.

http://blitzmax.com/codearcs/codearcs.php?code=471

This code tells you if two line segments intersect, and if so, where.

Assuming P3 is moving, and P4 is the location it's trying to move to, then your two line segments are P1-P2 and P3-P4.


http://blitzmax.com/codearcs/codearcs.php?code=450

This code calculates the "normal" of a line. Multiply the two components of this normal by N and add the result to the position of the intersection you calculated above, and you've moved P3's intersection point back to the correct side of the line by N units.


Lastly, you want to determine if P3 is on the correct side of the line.

You have the normal of the line, N1, which you calculated above.

Now, calculate a normal which points from P1 to P3, or P2 to P3. Either one, doesn't matter:

Calculate vector/unnormalized normal:
N2x# = P3x#-P1x#
N2y# = P3y#-P1y#

Calculate length of vector:
D# = Sqr(N2x#*N2x# + N2y#*N2y#)

Normalize normal (make its length 1):
N2x# = N2x# / D#
N2y# = N2y# / D#


Now, all you have to do is do a 2D dot product between the normal of the line, and the normal from P1 to P3:

Dot# = N1x#*N2x# + N1y#*N2y#


The Dot Product will be 1 if the normals point in the same direction, 0 if they point 90 degrees off from one another, and -1 if they point in exact opposite directions. (And any number in between if they're only roughly the same.)

In other words, if P3 lay in the line P1-P2, then the normal from either of those points would be pointing along the line, and would be 90 degrees off of the line's normal which points perpendicular to the line, and the dot product would be 0. But if it were positioned where the red dot is in the example above, then the normal pointing at it, and the line's normal would be pointing roughly in the same direction and the dot product would be greater than 0.


And I think that's all you need to do. :-)

You don't need to normalise the vector p1->p3, which will save you a bit of calculation. A dot product of anything less than zero means p3 is on the wrong side of the line.

In fact, this is the kind of thing that needs pictures to understand properly, so here are some:



This is your drawing with the addition of a point p3B, which is where p3 ends up, and its initial position is now called p3A.



To see if p3B is on the right side of the line, we just need to get the dot product of the vector (p1 -> p3B) with the normal vector n. If the dot product is less than zero, p3B is on the wrong side.



Then all we need to do is 'project' p3B onto the line. We need a unit vector v along the line, which we can get by taking the vector (p1 -> p2) and dividing each of its component by the vector's length.
The vector l here is just the vector (p1 -> p3B).

Now, simply taking the dot product of v and l will give us the distance along the line of the point we want.

Finally, multiplying v by the dot product and adding it to p1 will give us exactly the co-ordinates of the final position of p3.

I would've gone into more detail, but I have to get ready for a lecture in 20 minutes!

"You don't need to normalise the vector p1->p3, which will save you a bit of calculation."


True, but I find working with normals makes things easier to understand. :-) Plus I doubt what he's doing requires him to worry about that square root there.

"You don't need to normalise the vector p1->p3, which will save you a bit of calculation."

You have to do this eventually. It's not needed for deciding which half-plane the point is in.
But then there is the 'move by n units' part of the problem. The normalized vector is one unit.

I suppose this could be avoided if you are actually calculating a point of intersection for two lines. But that must be more complicated than the vector approach to the problem.

Instead I get the unit vector along p1->p2, which can be precalculated if the line doesn't move.

Thanks for all your help. I already had the the first part of the problem (ie. finding out which side the point was on), but had a brain block on the 2nd part. Certainly helped. So, thanks.

I always wondered what hats on letters meant: unit vector. Useful to know.

It amazes me that I've forgotten so much of this. I did after all write one of the first (if not the first) 3D physics systems in Blitz, and a fairly complex moving convex hull collision/response system! But, I supposed back then I was much more inclined to follow hunches and intuitions about these things without actually having much of a grasp of the math, or the proper way to proceed.