I need to find a way to determine if a ray is pointing at a line.

[tetch]

Hi everybody,

I need to find a way to determine if a ray is pointing at a line.
I have a line defined by two points [(x,y),(x,y)]. The line continues infinitely in both directions.
I have a startPoint (x,y) as the start of the ray and an endPoint which is just a point on the ray.
How can I determine if the ray is pointing at the line?

I will give more context to the question:
It is for a program I'm writing.
The line represents a wall, startPoint is a point where a robot is starting to move from and endPoint is where the robot is currently at.
I want to know if by continuing on the same path as created between the points will the robot eventually reach the wall.
true for will reach the wall.
false for will not reach the wall.

some examples:

for a line [{ x: 200, y: 100 },{ x: 450, y: 100 }]
startPoint { x: 300, y: 150 }, endPoint { x: 500, y: 150 } - expected false
startPoint { x: 300, y: 150 }, endPoint {x: 400, y: 250 } - expected false
startPoint { x: 400, y: 250 }, endPoint {x: 300, y: 150 } - expected true

for a line [{ x: 200, y: 100 },{ x: 200, y: 400 }]
startPoint { x: 300, y: 150 }, endPoint {x: 400, y: 250 } - expected false
startPoint { x: 500, y: 150 }, endPoint {x: 300, y: 150 } - expected true


for a line [{ x: 450, y: 400 },{ x: 550, y: 200 }]
startPoint { x: 300, y: 150 }, endPoint {x: 400, y: 250 } - expected true
startPoint { x: 300, y: 150 }, endPoint { x: 500, y: 150 } - expected true

I need help with the right equations for this problem.

Thanks

 

[Steven G]

Hi everybody,

I need to find a way to determine if a ray is pointing at a line.
I have a line defined by two points [(x,y),(x,y)]. The line continues infinitely in both directions.
I have a startPoint (x,y) as the start of the ray and an endPoint which is just a point on the ray.
How can I determine if the ray is pointing at the line?

You should give a definition of what it means for a ray to point to a line.
Have you drawn rays that point to a given line and rays that do not point to a given line. Can you see why some rays to the line and others do not point to the line?

 

[tetch]

Hi thanks for your response.
Im attaching an image that explain what I mean.

The line is infinite so the ray doesn't need to point at the segment to be pointing to the line

 

[Dr.Peterson]

Hi thanks for your response.
Im attaching an image that explain what I mean.
View attachment 35378
The line is infinite so the ray doesn't need to point at the segment to be pointing to the line

So, what you mean is, does the ray intersect the line. Right?

One approach would be to parametrize the ray, solve for an intersection, and determine whether the parameter is positive.

Or you could use vectors. How much do you know about them? I can think of several approaches you might take.

 

[tetch]

I know some about vectors but Im whilling to learn whatever is necessary.
Intersection was the way I initialy tried. The problem is I don't know how to check for intersection only one one side of the ray.

 

[The Highlander]

Hi everybody,

I need to find a way to determine if a ray is pointing at a line.
I have a line defined by two points [(x,y),(x,y)]. The line continues infinitely in both directions.
I have a startPoint (x,y) as the start of the ray and an endPoint which is just a point on the ray.
How can I determine if the ray is pointing at the line?

I will give more context to the question:
It is for a program I'm writing.
The line represents a wall, startPoint is a point where a robot is starting to move from and endPoint is where the robot is currently at.
I want to know if by continuing on the same path as created between the points will the robot eventually reach the wall.
true for will reach the wall.
false for will not reach the wall.

some examples:

for a line [{ x: 200, y: 100 },{ x: 450, y: 100 }]
startPoint { x: 300, y: 150 }, endPoint { x: 500, y: 150 } - expected false
startPoint { x: 300, y: 150 }, endPoint {x: 400, y: 250 } - expected false
startPoint { x: 400, y: 250 }, endPoint {x: 300, y: 150 } - expected true

for a line [{ x: 200, y: 100 },{ x: 200, y: 400 }]
startPoint { x: 300, y: 150 }, endPoint {x: 400, y: 250 } - expected false
startPoint { x: 500, y: 150 }, endPoint {x: 300, y: 150 } - expected true


for a line [{ x: 450, y: 400 },{ x: 550, y: 200 }]
startPoint { x: 300, y: 150 }, endPoint {x: 400, y: 250 } - expected true
startPoint { x: 300, y: 150 }, endPoint { x: 500, y: 150 } - expected true

I need help with the right equations for this problem.

Thanks

Hi @tetch,

You should start by using the two points you have for the wall to produce an equation that describes the ‘path’ that the wall ‘lies’ on in the form \(\displaystyle y=mx+c\) or \(\displaystyle y=ax+b\) or whatever other ‘preference’ you have or have been taught.

If you are unsure about how to do that you can find details on it here.

Then you should do the same for the ‘path’ of your robot using the two points you have for it.

Once you have those two equations, if they have the same gradient ie; m (or a) is the same for both lines, then the robot will never reach the wall because their paths are parallel. If, however, both equations are exactly the same, ie: not only m (or a) but also c (or b) is the same for both lines, then your robot is walking along the wall!

If neither of those situations has arisen then you simply need to find the point of intersection of your two lines and that is done by equating the two equations to solve for the x-value of the point where they intersect, then substituting that value into one or other of the equations to get the corresponding y-value of the point where they intersect. Further information/instruction on that can be found here.

Hope that helps.

 

[blamocur]

for a line [{ x: 200, y: 100 },{ x: 450, y: 100 }]
startPoint { x: 300, y: 150 }, endPoint { x: 500, y: 150 } - expected false
startPoint { x: 300, y: 150 }, endPoint {x: 400, y: 250 } - expected false
startPoint { x: 400, y: 250 }, endPoint {x: 300, y: 150 } - expected true

I believe the ray in the marked up line above intersects the wall at (250,100), which means that 'true' should be expected.

 

[tetch]

Hi @tetch,

You should start by using the two points you have for the wall to produce an equation that describes the ‘path’ that the wall ‘lies’ on in the form \(\displaystyle y=mx+c\) or \(\displaystyle y=ax+b\) or whatever other ‘preference’ you have or have been taught.

If you are unsure about how to do that you can find details on it here.

Then you should do the same for the ‘path’ of your robot using the two points you have for it.

Once you have those two equations, if they have the same gradient ie; m (or a) is the same for both lines, then the robot will never reach the wall because their paths are parallel. If, however, both equations are exactly the same, ie: not only m (or a) but also c (or b) is the same for both lines, then your robot is walking along the wall!

If neither of those situations has arisen then you simply need to find the point of intersection of your two lines and that is done by equating the two equations to solve for the x-value of the point where they intersect, then substituting that value into one or other of the equations to get the corresponding y-value of the point where they intersect. Further information/instruction on that can be found here.

Hope that helps.

Thank you for responding.

I know how to solve intersetiong lines, but that's not what I meant.
If a robot starts moving in any direction and you'll draw a line from the point he started from to the point he stopped at, check for intersection between that line the wall they will always intersect, unless the robot is moving parallel to the wall. That does'nt mean that the robot is moving towards the wall, it can move away from the wall and still have a line equestion that intersects with the wall.

 

[The Highlander]

I know some about vectors but Im whilling to learn whatever is necessary.
Intersection was the way I initialy tried. The problem is I don't know how to check for intersection only one one side of the ray.

Thank you for responding.

I know how to solve intersetiong lines, but that's not what I meant.
If a robot starts moving in any direction and you'll draw a line from the point he started from to the point he stopped at, check for intersection between that line the wall they will always intersect, unless the robot is moving parallel to the wall. That does'nt mean that the robot is moving towards the wall, it can move away from the wall and still have a line equestion that intersects with the wall.

Once you have found the point of intersection of the two lines (that of the wall and that of the robot's path), if the point of intersection is the same the robot's current (x, y) point then it is currently on (or inside or under) the wall or if it's the same as the robot's starting (x, y) point then it was on the wall and is now walking away from it.
Otherwise, if the (magnitudes of the) coordinates of the point of intersection are greater than those of the robot's current (x, y) position then the robot is walking towards the wall and should eventually reach it, however, if the (magnitudes of the) coordinates of the point of intersection are smaller than those of the robot's starting (x, y) position, then it is walking away from the wall; otherwise it has gone through the wall and it now walking away from it.
Hmmm, not even sure if that's right myself now (no doubt @Otis will tell us, lol) ?
Too tired to think about it any further, I'm sure someone else will sort it out if that's wrong. ?

 

[tetch]

I believe the ray in the marked up line above intersects the wall at (250,100), which means that 'true' should be expected.

No. that is not correct.
it started at (300,150) and ended at (400,250), which is in a direction away from the wall . therefore will not intersect.

 

[blamocur]

If, in vector notation, [imath]\mathbf p_1, \mathbf p_2[/imath] are points on the wall, [imath]\mathbf q_1[/imath] is the starting point of the robot and [imath]\mathbf q_2[/imath] its current point, and if the corresponding lines intersect then for some scalars [imath]u[/imath] and [imath]v[/imath] we'll have
[math]u\mathbf p_1 + (1-u) \mathbf p_2 = v \mathbf q_1 + (1-v) \mathbf q_2[/math]Note that because the above is vector equation we'll actually have a system of two equations for [imath]u,v[/imath], i.e., one for x-component and one for y-component of the vector equation. Once you solve the equation you will have to look at the value of [imath]v[/imath]:

• [imath]v < 0[/imath] means that the robot is moving toward the wall;
• [imath]v = 0[/imath] means the robot is at the wall at the current time;
• [imath]0 < v < 1[/imath] means that the robot have crossed the wall sometime between the starting and the current time;
• [imath]v = 1[/imath] means the robot started at the wall and is moving away;
• [imath]v > 1[/imath] means that the robot has been moving away from the wall since the start;

I believe the above is correct (because I never make mistakes), but I encourage you to double-check it.

 

[blamocur]

No. that is not correct.
it started at (300,150) and ended at (400,250), which is in a direction away from the wall . therefore will not intersect.View attachment 35379

You are right and I am wrong -- I did not pay attention to the direction of the segment.

 

[tetch]

Once you have found the point of intersection of the two lines (that of the wall and that of the robot's path), if the point of intersection is the same the robot's current (x, y) point then it is currently on (or inside or under) the wall or if it's the same as the robot's starting (x, y) point then it was on the wall and is now walking away from it.
Otherwise, if the (magnitudes of the) coordinates of the point of intersection are greater than those of the robot's current (x, y) position then the robot is walking towards the wall and should eventually reach it, however, if the (magnitudes of the) coordinates of the point of intersection are smaller than those of the robot's starting (x, y) position, then it is walking away from the wall; otherwise it has gone through the wall and it now walking away from it.
Hmmm, not even sure if that's right myself now (no doubt @Otis will tell us, lol) ?
Too tired to think about it any further, I'm sure someone else will sort it out if that's wrong. ?

No that is not right.
The wall can be anywhere in relation to he robot. The value of the intersection point can't give away the direction just by if it's bigger or smaller then the points on the robot's path.

In example A, the value of the intersection is smaller then both points. in example B the value is bigger.
The wall also dosen't have to be vertical or horizontal it can be in any angle.

 

[blamocur]

No that is not right.
The wall can be anywhere in relation to he robot. The value of the intersection point can't give away the direction just by if it's bigger or smaller then the points on the robot's path.
View attachment 35382
In example A, the value of the intersection is smaller then both points. in example B the value is bigger.
The wall also dosen't have to be vertical or horizontal it can be in any angle.

What are the values of [imath]v[/imath] in your examples ?

 

[Dr.Peterson]

I know some about vectors but Im willing to learn whatever is necessary.
Intersection was the way I initialy tried. The problem is I don't know how to check for intersection only one one side of the ray.

You're getting several very different approaches. and adding more may just increase the confusion; but I'll give some more details on my two main ideas.

When I suggested parametrizing the ray, which I'll call [imath]\overrightarrow{AB}[/imath], that means something like [imath]\left<x,y\right> = \left<x_a+t(x_b-x_a), y_a+t(y_b-y_a)\right>[/imath], so that [imath]t=0[/imath] puts you at point A, [imath]t=1[/imath] puts you at point B, and any positive value for t represents a point on the ray.

Put those expressions for x and y into an equation for the line, and solve for t. If [imath]t > 0[/imath], then the ray intersects the line.

As for vectors, one approach would be to project point A perpendicularly onto the line (using vectors), resulting in point P. The dot product of vectors [imath]\overrightarrow{AB}[/imath] and [imath]\overrightarrow{AP}[/imath] will be positive if the ray [imath]\overrightarrow{AB}[/imath] will meet the line (that is, the angle between the two vectors is acute).

 

[tetch]

You're getting several very different approaches. and adding more may just increase the confusion; but I'll give some more details on my two main ideas.

When I suggested parametrizing the ray, which I'll call [imath]\overrightarrow{AB}[/imath], that means something like [imath]\left<x,y\right> = \left<x_a+t(x_b-x_a), y_a+t(y_b-y_a)\right>[/imath], so that [imath]t=0[/imath] puts you at point A, [imath]t=1[/imath] puts you at point B, and any positive value for t represents a point on the ray.

Put those expressions for x and y into an equation for the line, and solve for t. If [imath]t > 0[/imath], then the ray intersects the line.

As for vectors, one approach would be to project point A perpendicularly onto the line (using vectors), resulting in point P. The dot product of vectors [imath]\overrightarrow{AB}[/imath] and [imath]\overrightarrow{AP}[/imath] will be positive if the ray [imath]\overrightarrow{AB}[/imath] will meet the line (that is, the angle between the two vectors is acute).

Thank you!!!
I used your second suggestion. It works just as I needed!