By representing an orientation (or rotation) by a complex number instead of an explicit angle we can drop a fair number of expensive operations. So instead of storing angle 'a', we store complex number (cos(a), sin(a)).
Another potential advantage is the algebra framework (just manipulating algebra) and reasoning. Algebra's like complex number, vectors, quaternions, etc allow thinking in terms of relative information which can greatly simplify the process.
We will assume that standard mathematical convention of the X axis pointing the to right and the Y axis pointing up. Additionally we will assume that the reference orientation of objects is pointing straight right. Combining these together when thinking about some specific entity, we can think in terms of its center being at the origin and its facing straight down the X axis.
NOTE: Although angles are talked about, this is for understanding and thinking purposes and not computation.
Basic examples in code: Common definitions
Capital letter are complex number and small are scalars.
Complex number basics
Complex numbers are represented by two numbers, which we will denote as a pair (a,b)
. The first number we will call 'x' and the second 'y'.ConjugateX* = (a,b)* = (a,-b)R* = (cos(a),sin(a))* = (cos(a),-sin(a)) = (cos(-a),sin(-a))
So the conjugate reflects (wikipedia
) about the X axis, which is the same as negating the angular information. (SEE: Trig identities: Symmetry
X+Y = (a,b)+(c,d) = (a+c,b+d)
X-Y = (a,b)-(c,d) = (a-c,b-d)
Operation is component-wise. Can represent translation.Product
XY = (a,b)(c,d)
= (ac-bd, ad+bc)
RP = (cos(a), sin(a))(x,y)
= (x cos(a) - y sin(a), y cos(a) + x sin(a))
RS = (cos(a), sin(a))(cos(b), sin(b))
= (cos(a)cos(b) - sin(a)sin(b), cos(b)sin(a) + cos(a)sin(b))
= (cos(a+b), sin(a+b))
So the product sums the angular information of the two inputs. (SEE: Trig identities: angle sum
SEE: C2D.mul(C2D)Product combined with conjugate
X*Y = (a,b)*(c,d) = (a,-b)(c,d) = (ac+bd, ad-bc)
R*S = (cos(a),sin(a))*(cos(b),sin(b))
= (cos(a)cos(b)+sin(a)sin(b), -cos(b)sin(a)+cos(a)sin(b))
Since we can add angles with the product and can negate an angle with the conjugate, the two together allow us to subtract angles. (AKA get relative angular information)
SEE: C2D.mulc(C2D) & C2D.cmul(C2D)Magnitude (L2 norm)|X| = |XX*| = |(a,b)(a,-b)| = sqrt(a2+b2)
Notice that we're not calling this length. Complex numbers, vectors, etc do not have lengths (nor positions). What they represent in a give instance might have a length equal to its magnitude.Unit complex and trig form
Unit complex numbers have a magnitude of one and can be written in 'trig form': (cos(t),sin(t))
Since scale factors can be pulled out (see scalar product) all complex numbers can also be written in 'trig form': m(cos(t),sin(t))
.Scalar productsX = s(a,b) = (s,0)(a,b) = (sa, sb)
This can be reversed, so all scale factors can be pulled out.Inverse
1/X = X*/(XX*) = (a,-b)/(a2+b2)
1/R = (cos(-a),sin(-a))/(cos(a)2+sin(a)2)
The multiplicative inverse of a unit complex is the same as its conjugate.
SEE: C2D.inv()Counterclockwise rotation of point about the origin
Falls directly out of the product. Given rotation (R) and point (P), the point after rotation (P'):
P' = RP
= (cos(a), sin(a))(x,y)
= (x cos(a) - y sin(a), y cos(a) + x sin(a))
P = (3,3)
R = (cos(pi/4), sin(pi/4)) = (.707107, .707107)
P' = (3,3)(.707107, .707107)
= (0, 4.24264)How do I find rotation of A into B
Solve the above. Assuming A & B are unit vectors:
RA = B
R = B(1/A)
R = BA*
A = (0.809017, 0.587785)
B = (0.5, -0.866025)
R = BA*
= (0.5, -0.866025)(0.809017, 0.587785)*
= (0.5, -0.866025)(0.809017, -0.587785)
= (-0.104528, -0.994522)Counterclockwise rotation of point about arbitrary point
We can rotate about the origin, to rotate about an arbitrary point (C) translate the system to the origin, perform the rotation and then undo the translation.
P' = R(P-C)+C
where T = C(1-R)
. Look at the last line. It is telling you that the rotation R about point C is equivalent to a rotation about the origin R followed by a translation T. And C is recoverable from T & R: C = T/(1-R)
(assuming R isn't 1...or no rotation).Composition of rotations
Falls directly out of the product. Given rotation (R) followed by rotation (S):RS = (cos(a+b), sin(a+b))Orthogonal direction
To find a direction orthogonal in a right-handed sense is the same as rotating by pi/2 radians (90 degrees), which is to multiply by (cos[pi/2], sin[pi/2) = (0,1).ortho(X) = ortho((a,b)) = (a,b)(0,1) = (-b,a)Relation to dot and cross products
Falls directly from the product where one is conjugated:X*Y = (a,b)*(c,d) = (a,-b)(c,d) = (ac+bd, ad-bc)dot(X,Y) = ac+bdcross(X,Y) = ad-bc
The dot product is the parallel projection and the cross is the orthogonal projection. Cross product is related to dot product by: cross(X,Y) = dot(ortho(X),Y)
Basic geometryOn which side of a line is a point?
A line can be represented by a direction (L) and a point on the line (A). The simplest case is a line which coincides with the X axis, L=(1,0) & P=(0,0)
, in which case we can simply examine the 'y' value of a test point (P). If 'y' is positive, then it is above, zero on the line and if negative then it is below. Moreover the value is the orthogonal distance of the point from the line.
Next let's consider an arbitrary line through the origin with unit direction L. We can simply rotate the system such that the line coincides with the X axis as above and we're done. Our modified test point becomes: P'=PL*
. Now the 'y' of P' is exactly the same as above. To fully generalize we simply need to move the line to the origin which give us: P'=(P-A)L*
If we were to plug in symbolic values: P=(px,py), L=(lx,ly) & A=(ax,ay)
and expand we would see that we have unused intermediate values. This is because we are ultimately only examining a single component..we're only examining the orthogonal projection of the point into the line (SEE: cross product above).
Additionally the direction of the line does not need to be normalized if we're only interested in above, on or below line question. The reason is because we only care about the sign of the result to answer our question.
So the 'which side' question reduces to: cross(L,P-A)
, which expands to the following pseudo-code: return lx*(py-ay)-ly*(px-ax)
Aside: the previous can be expanded to cross(L,P)-cross(L,A) = cross(L,P)-m
. The scalar 'm' can be stored instead of the point 'A' to represent the line. This value 'm' is commonly called the 'moment about the origin'.
At the top we say we can represent an entity by its position and orientation and think about its center as being at the origin and facing straight down the X axis (the reason for this is because that's the entity's local coordinate frame).
Let's call it's position E and orientation F and we have some test point P. We can translate the system to the origin (P-E)
and then we can undo the rotation of the system by multiplying by F*
, which gives us: (P-E)F*
. So P in the reference frame of our entity is:P' = (P-E)F*
P = (100,100)
E = (200,200)
F = (.92388, .382683) <- Pi/8 or 22.5 degrees
P' = ((200,200)-(100,100))(.92388, -.382683)
= (130.656, 54.1196)
If you've ever worked with vectors, this should seem similar: find the delta distance and perform the dot and/or cross product. The above equation is finding the delta distance and then effectively computing both. (Obviously you only compute one if only need one). So the dot product is simply the 'x' coordinate in the local coordinate frame (parallel projection) and the cross is the 'y' coordinate (orthogonal projection).What's my unit direction vector?
It's pretending the unit complex number of the orientation is a unit vector. It has the same numeric values for 'x' & 'y'.Is it behind me?
As noted above the dot product is 'x' in the local coordinate frame, so the sign of the dot product. If negative it's behind the center point with respect to facing and positive if forward.Turn clockwise or counterclockwise?
As noted above the cross product is 'y' in the local coordinate frame, so the sign of the cross product. If positive the shortest turn is counter clockwise, if negative it's clockwise and if zero it's straight ahead. Turn toward point with constant angular velocity
Again, the sign of cross product tells the minimum direction. Take a constant angular velocity, store as a unit complex number 'A'. If the sign of the cross product is negative, we need to conjugate A (negate it's 'y' component). Multiply the current facing 'F' by the potentially modified 'A'. Take our new 'F' and cross again. If the sign has changed, we've overshot the target.Is point within field of view
Given an entity in its local coordinate frame: image some field of view (<= Pi or 180 degrees), which become a pair of line segments symmetric about the X-axis (or triangle or cone). We can immediately note a couple of things. The first is that if our x component of a test point P=(px,py) is negative that it cannot be inside. The second is that given the symmetry about the X-axis, P and P*
will always return the same results. Given the second we can form a new test point P'=(px,|py|). Now the problem is identical to on which side a point falls with respect to a line through the origin and we the first observation isn't required to compute the result. Since we're asking 'below' the line, we negate the result to convert into convention of positive is inside, yielding the following pseudo-code: return ly*px-lx*Math.abs(py);
As with the point to line test, our direction L does not need to be normalized and L is the half-angle of the field-of-view.Which unit direction forms the minimum angle with the local X axis.
Although related to point/line and field-of-view, this case reduces to simply the direction with the greatest x component.
This wiki entry has had 5 revisions with contributions from 1 members.