Hi there,
There are a several ways to answer this question, so I will give you
one of the simplest.
I actually had to research problems like this (in 2D though) for the
programming contests at http://www.topcoder.com not long ago.
We are given two points P1 and P2 in Euclidean three-dimensional space
at coordinates (x1,y1,z1) and (x2,y2,z2) and we want to find the angle
between the rays O-P1 and O-P2 where O is the origin.
Let theta be this angle.
Then it is a theorem that the inner product of P1 and P2, see
http://mathworld.wolfram.com/DotProduct.html, that
P1 dot P2
has value
|P1| |P2| cos theta
The inner product of P1 and P2 is:
x1 x2 + y1 y2 + z1 z2
And the norm of a vector is the square root of the sum of the squares
of its coordinates (this works also in any number of dimensions)
Thus, here is how one might solve this in pseudocode
double angle (double[] P1, double[] P2){ //compute angle between P1
and P2
double P1norm=0; // |P1|
double P2norm=0; // |P2|
for (int i=0;i<3;i++)P1norm+=P1[i]*P1[i];
P1norm=sqrt(P1norm); // Get P1norm
for (int i=0;i<3;i++) P2norm+=P2[i]*P2[i];
P2norm=sqrt(P2norm); //Get P2norm
double epsilon=.000000000000001 //some very small positive value,
depending on machine precision and application details
if (P1norm<epsilon && P2norm<epsilon) {ERROR UNDEFINED;} //Both
points are at origin (or very close to it)
else if (P1norm<epsilon) return 0;
else if (P2norm<epsilon) return 0;
else {
double inner=0;
for (int i=0;i<3;i++)inner+=P1[i]*P2[i]; //Get the inner product
return arcCosine(inner/(P1norm*P2norm)); Take the arc cosine
}
Explanation: the only subtlety here is checking for roundouff error
and underflow.
Suppose the two points were BOTH at (0,0,0). Then the angle between
them would be undefined. But because of roundoff error, sometimes if
both points are extremely close to 0, we also want to return
"undefined". Exactly how you want to handle this is up to you and
depends on the application.
Similarly, we think of any point "sufficiently close" to 0,0,0 as
being "at" 0,0,0.
There are also numerous directories of code for other computational
geometry questions, for example,
http://compgeom.cs.uiuc.edu/~jeffe/compgeom/ , and
http://compgeom.cs.uiuc.edu/~jeffe/compgeom/code.html#prims
Java itself has various computational geometry primitives built in to
the java.awt.geom package.
I personally find that the chapter in the Cormen, Leiserson, Rivest,
and Stein book at:
http://theory.lcs.mit.edu/~clr/
is the best way to start with computational geometry questions. It is
a good introduction.
Search Strategy:
inner product
dot product
angle inner product
Cormen, Leiserson, Rivest
computational geometry
Please let me know if you would like additional clarification on this
problem. |
Request for Answer Clarification by
startrekdude-ga
on
15 Sep 2002 14:56 PDT
I will try to clarify what I am looking for better.I make will
startrek like.
object 1 is enterprise d.it is located at x1, y1, z1.
object 2 is Romulan warbird that just decloaked inside federation
space. it is located at x2,y2,z2
The enterprise d wants to move toward the romulan warbird.The helmsman
needs to know the following angles:
1 the angle that how left or right
|
Request for Answer Clarification by
startrekdude-ga
on
15 Sep 2002 15:21 PDT
I will try to clear up what I am looking for.I will startrek like.
object 1 is enterprise d. it located at x1, y1, z2
object 2 is romulan warbird in federation space.it is located at
x2,y2,z3
of course the enterprise d want to go to the romulan warbird.The
helmsman needs the following info.
1 the angle saying how left or right enterprise d needs to be go to
strait toward the romulan warbird.
2 the angle saying how up or down the enterprise d needs to go strait
toward the romulan warbird.
Ps the weapons officer may need the info also.
Since I am darkbasic for the programming language it does not appear
to have inverse sin or inverse tan.They have the following math
commands.
SQRT() will return the square root of an expression
ABS() will return the positive equivalent of an expression
INT() will return the largest integer before the decimal point
RND() will return a random number within a given range
EXP() will return a number, raised to the power of a value
COS() will return the cosine of a value
SIN() will return the sine of a value
TAN() will return the tangent of the a value
ACOS() will return the arccosine of a value
ASIN() will return the arcsine of a value
ATAN() will return the tangent of a value
ATANFULL() will return the angle between points
HCOS() will return the hyperbolic cosine of a value
HSIN() will return the hyperbolic sine of a value
HTAN() will return the hyperbolic tangent of a value
|
Clarification of Answer by
rbnn-ga
on
15 Sep 2002 20:40 PDT
First, the arc cosine, ACOS, is the same function as "inverse cosine".
These are just different terms for the same thing.
Second, in all these computations I am going to assume that the
objects reside in Euclidean 3-dimensional space. In fact the topology
of the universe may be different from Euclidean three-space (it might
be a Riemannian manifold) in which case the computations become more
complex because the meaning of "straight line" changes (by analogy,
think of a ship on the surface of the Earth trying to go from point A
to point B: the ship cannot simply "point towards" A and B, since it
must travel along geodesics, great circles.)
Third, I am going to assume that both objects are at rest relative to
one another. If Object 2 is moving at some rate then the Enterprise
may wish to aim at a location such that the Enterprise arrives to
where the object is at the time the Enterprise arrives; but I will
neglect this. Similarly, if the Enterprise is moving at some rate then
I will neglect the time it takes the Enterprise to change its
orientation and momentum vector.
Fourth, there is not quite enough information given to solve the
problem. Specifically, you will need the orientation of the
Enterprise.
Let me explain. Suppose the Enterprise is at (0,0,0) and the other
ship is at (1,0,0). Then if the Enterprise is already pointing in the
direction of (1,0,0) then clearly the Enterprise does not need to turn
at all. On the other hand, if the Enterprise is facing opposite to
(1,0,0) then the Enterprise must perform a 180-degree rotation about,
for example, the z-axis.
Now suppose we idealize the Enterprise is a small directed line
segment from endpoint P1_a to P1_b representing the stern and the bow
of the Enterprise. One might think that this would be sufficient to
solve the problem, since one could determine how much to rotate the
line segment about lines parallel to the coordinate axes and throught
the center of mass of the Enterprise. However, remember that
(presumably) the coordinate system used by the helmsman of the
Enterprise will be the natural coordinate system given by the
Enterprise itself; that is, the helmsman can rotate about axes
perpindicular to the line segment through Captain Picard, if Picard
were standing straight up and facing forward.
There are several ways one can use to denote the orientation of the
Enterprise. If you like, you can tell me how you plan to represent
this orientation, or I can choose some one and then give you the
answer from that representation. Which would you prefer?
|
Request for Answer Clarification by
startrekdude-ga
on
16 Sep 2002 11:48 PDT
Well think I got it right.Well I plugged some numbers in it looked
about what I think it should be.For example x1 ,y1, z1 where all 1 and
x2,y2,z2 where all 2 and both angles showed up as 45 which I believe
is correct.Below is source code I made for it.Does it look right to
you?
xdif = x2 -x1
ydif = y2 - y1
zdif = z2 - z1
if ydif > 0 then xyangle = atan(xdif/ydif)
if ydif < 0 then xyangle = atan(xdif/ydif) + 180
h = sqrt( (xdif)^2 + (ydif)^2 )
if h > 0 then zangle = atan(zdif/h)
if h < 0 then zangle = atan(zdif/h) + 180
|
Clarification of Answer by
rbnn-ga
on
16 Sep 2002 15:13 PDT
We are actually discussing three separate issues here:
1. How does one usefully mathematically model the angular navigation
commands of the Enterprise?
2. Given a mathematical definition of the problem in 1, how does one
solve for the angles required?
3. Given a mathematical solution in 2, how do we actually code it?
Regarding 1, one resource I used is:
Star Trek: The Next Generation Technical Manual by Rick Sternbach and
Michael Okuda (Pocket Books, 1991).
Section 3.4 of that book discusses flight control. Pages 36-37 discuss
navigation methods specifically. Six input modes for Conn are given:
1. Destination planet or star system.
2. Destination sector.
3. Spacecraft intercept (only when the target spacecraft has a
tactical sensor lock).
4. Relative bearing. The flight vector is specified as
azimuth/elevation relative to the current orientation of the
Enterprise.
5. Absolute heading. Flight vector is specified as azimuth/elevation
relative to the center of the galaxy
6. Galactic coordinates (XYZ).
Presumably you are most interested in input modes 4 and 5 for the
purposes of this question.
As I pointed out in my previous answer clarification, however, in
order to implement mode 4 you will need to keep track of the spatial
orientation of the Enterprise: which way it is pointed and how much it
is twisted about its axis.
6. This implementation would require a lot of additional information
and would require some linear algebra to do, so you may not want to
implement input mode 4.
Input mode 5 does suggest that you can use absolute angles and so you
do not need to keep track of the orientation of the Enterprise.
My recommendation if you choose to use input mode 5 would be to
convert both the Enterprise P1 and the target P2 into spherical
coordinates. (see http://mathworld.wolfram.com/SphericalCoordinates.html
) .
The spherical coordinates of a point [x,y,z], assuming the sphere has
origin at the galactic center, is given by:
r = sqrt(x^2 + y^2 + z^2)
theta = ATAN(y/x)
phi = ACOS (z/r)
Here, theta is the "azimuthal angle", the angle in the xy-plane from
the x axis, and phi is the "polar angle", the angle from the z-axis,
formed by the ray O-[x,y,z].
The picture at the above URL is clearer than I can draw here as well.
Anyway, get the azimuth and polar angles for the Enterprise at P1, say
phi_1 and theta_1
Next, get the azimuth and polar angles for the target, say the Romulan
warbird, at
phi_2 and theta_2
using the above formulas.
Now, the angles you need to rotate the enterprise are given by the XY
rotation, the azimuthal rotation, of:
theta_2 - theta_1 = A
and the elevation angle, given by:
phi_2 - phi_1 = E
Thus, the instruction would be A mark E, where A and E are defined
above.
Finally, I will answer your specific request for clarification:
You write:
"For example x1 ,y1, z1 where all 1 and
x2,y2,z2 where all 2 and both angles showed up as 45"
I'm afraid I do not understand why in this case, in which P1, P2, and
the origin are all collinear, that "both angles should show up as 45
degrees".
Either you are using relative bearing or absolute heading (input modes
4 and 5 above).
If you are using relative bearing, then the amount to rotate the
Enterprise depends not only on x1,x2,x3 but also on the orientation of
the Enterprise. Since you do not specify the orientation of the
Enterprise, there is no way to know what its orientation is, hence,
there is no way to know how much to rotate it. Your answer would be
correct, however, if you are using relative bearing AND if the natural
coordinate system defined by the Enterprise was parallel to the
galactic coordinate system, but this is not necessarily the case (and
doesn't make sense, since the Enterprise is going to turn around as
soon as it executes the mark order anyway; that is to say, the
Enterprise is going to be turning all the time).
On the other hand, if you are using absolute bearing, then the
Enterpise need not change its mark at all: it does not need to perform
any azimuthal or elevation rotation, since its polar and azimuthal
angles are identical to that of the target.
Thus, since it remains uspecified what it is that your code intends to
compute so I cannot comment on it (well, of course, h is never
negative and you do not need to check for that case)
|
Clarification of Answer by
rbnn-ga
on
17 Sep 2002 03:24 PDT
I just wanted to add a couple of other comments.
You can find additional information on Star Trek cartography at
http://www.stdimension.de/int/Cartography/IntroTools.htm . This pretty
much agrees with my suggestion to use spherical coordinates with the
origin at the galaxy center, which was taken from the Star Trek Next
Generation Technical manual (op cit.) . This site has some additional
detail on Star Trek cartography, including coordinates for numerous
stars.
For implementation, you might consider first writing a routine to
convert galactic coordinates to spherical coordinates. For example,
the point (1,1,1) should have spherical coordinates of r=sqrt(3), and
azimuthal and polar angles each equal to 45 degrees, using the
formulae in my previous clarification.
Finally, one suggestion that you might consider, if you have not
already done so, is first to build your system working for simplified
2-D Star Trek, and only then to add in the third dimension. I
personally find it useful when developing programs to get some simple
prototypes up first before tackling the full problem; I don't really
have a reference for you on that, maybe
http:///www.extremeprogramming.org .
|
Sheesh this is getting to be a long comment. And just like most long
winded nerds I put the interesting stuff at the end. Feel free to
jump down there and take a look at my nifty ascii art graphs.
rbnn-ga you're math looks very impressive. I think the problem is
you're thinking on a level that is just too far above what star trek
dude needs.
I'm Sorry my line "Solving object 1 to go to object 2, that is, to
point towards it" seems so vague. I was trying to put it in terms
similar to the ones startrek dude was using.
Hmm I just noticed I made a dumb mistake. I make object 2 the new
origin when I meant to make object 1 the new origin. Silly me. I'll
fix all this further down in this post.
Anyway, what I meant by "point towards it" means to solve for the two
angles needed to reorient object 2 to point towards object 1. Or if
you prefer, to draw a line that intersects object 1 and object 2. The
problem could be stated as: Find a line that intersects object 1 and
object 2 and define it using only object 1's position and two angles.
However, I can see by you're Clarification of Answer (on 15 Sep 2002
20:40 PDT) that you have realized this is what startrek dude was
after. But you seem reluctant to solve it since ambiguity still
abounds in the problem. This could easily be rectified simply by
stating and clearly defining some assumptions.
Like I mentioned before if you tell a math geek to turn 90 degrees he
turns to the left (counter clockwise) where a pilot would turn to the
right (clockwise). Too resolve this ambiguity I suggest you do a
search on a web for an explanation of what they do on Star Trek: The
Next Generation. I remember clearly that there was one episode where
they explained what all the 90 mark 10 stuff meant too someone in the
show. So this could actually be found on a site that has transcripts
of the show. Maybe someone has the captioning. This is Star Trek
after all. SOMEONE out there has posted this :)
Bring it down and agree on some conventions and I think you'll find
the answer.
Now, to clarify the assumptions in my own answer (14 Sep 2002 22:22
PDT).
I'll admit I was a bit lazy with the way I stated this. I'll state
all the assumptions one must make for my solution to work properly.
Indeed I am assuming simple boring old Euclidean 3-dimensional space.
Lines move in straight lines.
I am also assuming that the beginning orientation (the direction
object 1 is pointing in before we point it at object 2) is the same as
along the positive side of the X axis. I do this because it makes the
math so simple. Since the orientation of object 1 is not given in
anyway there is no reason not to assume it has the same orientation.
This could become a problem with successive solutions, which would
mean I have keep the X axis pointed the same way while object 1 points
to different places as it chases a dodging object 2. This should be
possible to compensate for, but let me solve one problem at a time.
I am assuming that 90 mark 0 would just mean turn left. This is
because I'm a math geek. If this turns out to be wrong after looking
through some star trek fan sites I recommend you just apply a negative
1 to correct it.
I am also assuming that 0 mark 10 means to raise the nose of object 1
up. This also assumes that the positive z axis is pointing in the
same direction that picard thinks is up. This can be justified the
same way I justified being oriented towards the positive x axis. And
has the same problem with successive solutions.
So you only need to know the orientation of the enterprise for
successive solutions if you're axis must be fixed through all
successions. If it's a one shot problem (as stated) or you don't care
if you shift the axis around to match object 1's orientation each time
then my solution holds as stated.
Now to deal with a fixed axis that point in one absolute direction
through all maneuvers. This could be thought of as analogous to a
gyroscope that they have onboard that always points in the same
direction.
Actually this is so simple I feel silly that it took me all this
typing to get around to it.
Let Gxy be object 1's starting orientation relative too our gyroscope
IN the xy plane
Let Gz be object 1's starting orientation relative too our gyroscope
FROM the xy plane
We can still SHIFT the origin to object 1's position even with a fixed
orientation so:
x'1 = 0
y'1 = 0
z'1 = 0
x'2 = x2 - x1
y'2 = y2 - y1
z'2 = z2 - z1
(Here I am correcting my earlier mistake of making object 2 the
origin)
There is also some other compensation that must be done that I left
out before. For example an arctan only goes from 0-180. You will
have to write code that will compensate for this. that is:
if y'l > 0 A = inverse tan(x'1/y'1)
if y'l < 0 A = inverse tan(x'1/y'1) + 180
if h'l > 0 B = inverse tan(z'1/h'1)
if h'l < 0 B = inverse tan(z'1/h'1) + 180
Now as if that wasn't confusing enough for you let my try to graph
this in ascii art (hope you've using a fixed point font or this will
look very messy):
(Z)
|
| (Y)
| / . obj2
| / |
| / |
| / |
| / |
| / |
| / |
| 5/__________| . obj1
| / / |
| 3/ _________/________|
| / / /
| / / /
|/ / /
----|--------------------------> (X)
/| 10 20
/ |
/ |
/ |
Object 1 and 2 in 3 dimensions. Note how in this case obj2 is 5 higher
then obj1.
So in this case object 1 has x = 20, y = 3, z = 2. (This looks out of
proportion because fonts typically are not square)
And object 2 has x = 10, y = 5, z = 7.
Now our job is to find a line that connects obj1 to obj2. We must
define this line using only obj1's x, y, z position and two angles. I
show this line in the graph below using dots.
. obj2
|.
| .
| .
| .
| .
| .
_______| . obj
/ |
_____/________|
/ /
/ /
/ /
-----------------> (X)
10 20
Now I'd like to show exactly how angles A and B are oriented. Two do
that I'll zoom in. Wish me luck.
. obj 2
|.
| .
| .
| .
| .
| .
| .
| .
| .
| .
| .
| ___.
| ,' .
| (B) .
| ' .
| ' .
|. ' .
x2,y2 | . .
__________|. . .
/ . . .
/ . . obj 1 -->
/ . |
______/________________________|
/ / . ,(A),
/ / x1,y1 . , ' ' ,
/ / . ,'
',
/ / .
'
/ / .
'
--------------------------------------------------------------.---------->
(X)
10 20
Ok A is the angle IN the xy plane. That is, it is defined as the
angle from the X axis to the x1,y1-x2,y2 line.
And B is the angle FROM the xy plane. That is, if is defined as the
angle from the x1,y1-x2,y2 line to the obj 1-obj 2 line.
I hope this clears things up because it's 3am here and I gotta be up
tomorrow. I must say this has been an interesting exercise in
technical writing. Hope you like the ascii art. Remember use a fixed
font! If you need any more clarifications just post. I'll be
monitoring for reaction to this. But for now. BED!
Warner |
