Sign in to follow this  
gondar

Locating points on rays given distance bw them

Recommended Posts

I have three rays defined by an origin point O and three direction vectors Va, Vb, Vc. There are three points A, B and C, each one is located somewhere on a separate ray. I know distance between points A, B and C and I have to find exact position of points A, B and C. |Va| = |Vb| = |Vc| = 1 T1 = |OA| T2 = |OB| T3 = |OC| I'm unable to find a solution thus far. [Edited by - gondar on September 13, 2009 7:41:50 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by szecs
Yes, the problem is over or under constrained.
If the rays are given too, then it's over, if not, under.
It can be solved, if two rays, and the three sides are given.
Or 3 rays, and two sides -> so 5 params need to be given.

If 3 rays and 3 sides, the problem is solvable only in special cases, in general cases, no, because 5 params will define the geometry perfectly, and in general, the 6th will be in conflict with the others.


The variables marked as blue are given:
1. Distance between points A, B, C is known
2. Origin point O for the rays is known
3. Direction vectors for rays are known

If problem is either over or under constrained, can you prove it?

Share this post


Link to post
Share on other sites
If I have understood correctly its not too hard. Lets take triangle OAB. We know all inner angles and |AB|. We know the angles becase we know vectors, so we just need to take dot product to obtain angles. Than just take sine law and calculate remaining distances |OA| and |OB|. Than make your vectors unit vectors and multiply them with distances |OA| and |OB| to obtain points A and B.
For point C calculate the point between A and B, lets call it D. Since you also know all the angles in triangle ABC and all the distances its easy to find point C. Now just add point C to D and u have real C.

Share this post


Link to post
Share on other sites
I hope it makes sense without a drawing:

'a','b','c' is the angle at A,B,C points
'x' is the angle of O-B-A, 'y': O-A-B (middle is the "corner").
't' is angle between Va-Vb rays.

equations:

(180-(180-b-x)-x) + (180-(180-a-y)-y) + c =180
t+x+y=180

solve this, and you'll have 'x' and 'y', so you are able to calculate all angles in the geometry.
Then let O-A length be 1, calculate one side, it will be for example 'G1_mod'.
You have to scale with G1_mod/G1, and you got the real O-A distance.

Finding an easier solution, well, I'm not capable of that.

Some help to draw it: draw a line that goes through C and parallel to A-B.
EDIT2: (180-b-x) is the angle between B-C and Vb, (180-a-y) between A-C and Va.

This works only for the situation, you have drawn (Va,Vb,Vc in this order, and C is outside the O-A-B triangle).

EDIT: findig a general solution is f. hard, maybe easier to simply handle all the possible situations.
BTW, there are 2 solutions to the problem (C is inside or outside)



EDITX: Sorry doesn't work,
(180-(180-b-x)-x) + (180-(180-a-y)-y) + c =180 becomes a+b+c=180, so no extra info, (was a nice try anyway...)
SORRY!

[Edited by - szecs on September 13, 2009 7:50:04 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by ryt
If I have understood correctly its not too hard. Lets take triangle OAB. We know all inner angles and |AB|. We know the angles becase we know vectors, so we just need to take dot product to obtain angles. Than just take sine law and calculate remaining distances |OA| and |OB|. Than make your vectors unit vectors and multiply them with distances |OA| and |OB| to obtain points A and B.
For point C calculate the point between A and B, lets call it D. Since you also know all the angles in triangle ABC and all the distances its easy to find point C. Now just add point C to D and u have real C.


Triangle OAB is not necessarily a right-angled one.

While we clearly can find angle <AOB, since we know normalized OA and OB vectors (the ray direction vectors Va, Vb), it doesnt seem apparent that we know all the inner angles of OAB and thus we can't use the law of sines here.

Please elaborate.

Share this post


Link to post
Share on other sites
Quote:
Original post by szecs
I hope it makes sense without a drawing:

'a','b','c' is the angle at A,B,C points
'x' is the angle of O-B-A, 'y': O-A-B (middle is the "corner").
't' is angle between Va-Vb rays.

equations:

(180-(180-b-x)-x) + (180-(180-a-y)-y) + c =180
t+x+y=180

solve this, and you'll have 'x' and 'y', so you are able to calculate all angles in the geometry.
Then let O-A length be 1, calculate one side, it will be for example 'G1_mod'.
You have to scale with G1_mod/G1, and you got the real O-A distance.

Finding an easier solution, well, I'm not capable of that.

Some help to draw it: draw a line that goes through C and parallel to A-B.
EDIT2: (180-b-x) is the angle between B-C and Vb, (180-a-y) between A-C and Va.

This works only for the situation, you have drawn (Va,Vb,Vc in this order, and C is outside the O-A-B triangle).

EDIT: findig a general solution is f. hard, maybe easier to simply handle all the possible situations.
BTW, there are 2 solutions to the problem (C is inside or outside)


What do you mean by angle a, b, c? Do you mean <CAB <ABC <ACB?

Alright, we can indeed find angles <CAB <ABC <ACB by using law of cosines.

But that's when i lose the thread.

You're in effect saying that 180 - <ABC - <OBA = <OBC? Or in other words <ABC + <OBA + <OBC = 180? Is that correct? It doesn't seem right to me though. Please elaborate.

----
It's true that there are two correct solutions, but in this case we can easily assume that T1 > 0, T2 > 0, T3 > 0.

Share this post


Link to post
Share on other sites
Last idea: if you don't have to calculate it precisely, or in real time, you could use iteration:
Assume the C point, then shoot 2 rays from it (their angle should be 'c', the angle in the C point in the triangle), then calculate the A'-C' and B'-C' sides of the triangle, if their ratios A'C'/B'C' differ from the ratios of the given triangle AC/BC, you have to shoot another rays and repeat the procedure again and again, until the difference reaches a small, acceptable value.
For example, if AB'/BC' greater than the given AC/BC, you have to rotate the rays (from C) clockwise, if less, counterclockwise, if equal, than quit the iteration.

You have to rotate the rays with a decreasing absolute value in the new iteration steps, to avoid infinite loops. Meaning new angle of rays=old angle of rays + increment or decrement value

This way, you will have all the angles in the geometry.

To get O-A distance, let O-A' be 1 long. Calculate A'C', then the real O-A = AC/A'C'.
The same for the other distances.

Share this post


Link to post
Share on other sites
From the constraints I think I can only deduce that we know the length of the sides of the triangles and the fact that three rays come from the origin. The fact that |Va| etc are one don't seem to supply any information since you multiply by OA (so in the end we have the unknown lengths OA OC and OB

If I move point C to lie on line O + Vb*T2 (as an extreme example). I still have the same constraints but point A would be different then I would for instance have point C on line O + Va * T1 (while keeping the shape of the triangle the same).

So there seems to be more than one solution possible (but I might be wrong :-) ).

Share this post


Link to post
Share on other sites
Quote:
Original post by Ron AF Greve
The fact that |Va| etc are one don't seem to supply any information since you multiply by OA (so in the end we have the unknown lengths OA OC and OB


Normalization of ray direction vectors doesnt supply additional information, but it does simplify some equations later on if you're trying this problem as a system of equations.

Share this post


Link to post
Share on other sites
But I don't think it is solvable to one solution (see my previous post) Besides that if I move the origin along the axe OC I still seem to meet all constraints so as far as I can see there are two reasons why there are multiple solutions (unless you express the solutions in line segments OA, OC and OB (still the fact that I can move C around means there is not one solution).

Share this post


Link to post
Share on other sites
Quote:
Original post by gondar
Quote:
Original post by ryt
If I have understood correctly its not too hard. Lets take triangle OAB. We know all inner angles and |AB|. We know the angles becase we know vectors, so we just need to take dot product to obtain angles. Than just take sine law and calculate remaining distances |OA| and |OB|. Than make your vectors unit vectors and multiply them with distances |OA| and |OB| to obtain points A and B.
For point C calculate the point between A and B, lets call it D. Since you also know all the angles in triangle ABC and all the distances its easy to find point C. Now just add point C to D and u have real C.


Triangle OAB is not necessarily a right-angled one.

While we clearly can find angle <AOB, since we know normalized OA and OB vectors (the ray direction vectors Va, Vb), it doesnt seem apparent that we know all the inner angles of OAB and thus we can't use the law of sines here.

Please elaborate.


Yea sorry for that.

Share this post


Link to post
Share on other sites
I think it's solvable:
Consider the 3 rays. If you put the A-B section of line on it, you are able to move it, but only one way, because the position of A determines the position of B.
So you have only one degree of freedom.
If you put C on the middle ray, you lock this freedom, so you have completely locked the triangle (it will be locked, because the movement of C point -before the locking- isn't collinear with the middle ray). Since you can place the C point in two ways (C is inside O-A-B, or outside), you have 2 solutions. This may only be truth in the situation, that the Original Poster has drawn (O-A, O-B, and O-C are positive numbers.)

Why is the iteration a bad idea BTW?

EDIT: maybe there are four solutions, because if we move A, then B can be 2 places (just consider a circle, it intersects a ray two times). But I'm not sure about this one. Maybe it depends on which side C is, so there will be 2 solutions after all.

Share this post


Link to post
Share on other sites
Why does the A position determine the B position. The only thing I know is that it would move around in a circle around A same for C (since we only know the length A-B and A-C).

Lets assume we know the solution; You got three points forming a triangle you know the three sides (put three things on the floor) now where would the origin be? Seems to me you can't answer that question. The fact that lines intersect at one point on the triangle and the other in the origin doesn't help that is true whereever the origin is.

Share this post


Link to post
Share on other sites
Maybe this is the way to solve it!
You can generate the equation of the curve, that C sweeps, if it's variable parameter is the O-A distance. So the curve is a function of O-A distance. The other parameters (the given things) will be it's constant parameters.
If you have the curve's and the middle ray's equation, intersect the 2 equations, and you will have the O-A distance.
To generate the equation, well that's the hard part. (I won't do it, I have spent way too much time with this problem already)
I hope that helps.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ron AF Greve
Why does the A position determine the B position.
Because the circle intersects the Vb ray (in two points, that's why there is 2 solutions).
Because the rays are given (the angle between them), the A-B distance is given and if we fix the A point, (So O-A is given too), that's 3 parameters, which define the triangle completely, so B will be determined. If we move A, B will move to, But it can be only 2 places again(on the Vb ray). So the A-B section can only move in one mode/way.

Share this post


Link to post
Share on other sites
Let's define `a', `b' and `c' by
A = a*Va
B = b*Vb
C = c*Vc

The fact that the distance between A and B is known can be expressed as
|a*Va - v*Vb| = G1
(a*Va - b*Vb).(a*Va - b*Vb) = G1^2
a^2*Va^2 + b^2*Vb^2 - 2ab*(Va.Vb) = G1^2
a^2 + b^2 - 2ab*(Va.Vb) = G1^2

Similarly
b^2 + c^2 - 2bc*(Vb.Vc) = G2^2
c^2 + a^2 - 2ca*(Vc.Va) = G3^2

I am not sure how the resulting system of [quadratic] equations would be solved. It can be done numerically, or perhaps you can use Gröbner bases to solve it (I know this is possible but the details are hairy).

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Let's define `a', `b' and `c' by
A = a*Va
B = b*Vb
C = c*Vc

The fact that the distance between A and B is known can be expressed as
|a*Va - v*Vb| = G1
(a*Va - b*Vb).(a*Va - b*Vb) = G1^2
a^2*Va^2 + b^2*Vb^2 - 2ab*(Va.Vb) = G1^2
a^2 + b^2 - 2ab*(Va.Vb) = G1^2

Similarly
b^2 + c^2 - 2bc*(Vb.Vc) = G2^2
c^2 + a^2 - 2ca*(Vc.Va) = G3^2

I am not sure how the resulting system of [quadratic] equations would be solved. It can be done numerically, or perhaps you can use Gröbner bases to solve it (I know this is possible but the details are hairy).

Yeah, i've derived the same system of equations, but i don't know how to solve them.

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