Algorithm for Vector Cross Product of N Dimensions

H

hobbes

i am wondering how to write a method that calculates the cross product
of two vectors. the algorithm i seek is one that can calculate the N-
Dimensional vector cross product with another N-Dimensional vector.
the solution should be mathematically correct. i am mostly concerned
with 3D and up and i am willing to enforce that the vectors be of
equal dimensions although i am not sure if that is a real mathematical
requirement. any advice?

(this question has nothing to do with java.util.Vector obviously).
 
G

GArlington

i am wondering how to write a method that calculates the cross product
of two vectors. the algorithm i seek is one that can calculate the N-
Dimensional vector cross product with another N-Dimensional vector.
the solution should be mathematically correct. i am mostly concerned
with 3D and up and i am willing to enforce that the vectors be of
equal dimensions although i am not sure if that is a real mathematical
requirement. any advice?

(this question has nothing to do with java.util.Vector obviously).

As far as I can see it is defined very well here http://en.wikipedia.org/wiki/Cross_product
and the formula is not dimensionally disadvantaged as long as you can
(and in Maths you can do it any time) add another dimension,
perpendicular to all others.
 
C

Christian

hobbes said:
i am wondering how to write a method that calculates the cross product
of two vectors. the algorithm i seek is one that can calculate the N-
Dimensional vector cross product with another N-Dimensional vector.
the solution should be mathematically correct. i am mostly concerned
with 3D and up and i am willing to enforce that the vectors be of
equal dimensions although i am not sure if that is a real mathematical
requirement. any advice?

(this question has nothing to do with java.util.Vector obviously).
If I remember correctly cross product is restricted to 3 diemnsional
Vectors.
And calcualting these should be quite simple. giyf
 
P

Patricia Shanahan

hobbes said:
i am wondering how to write a method that calculates the cross product
of two vectors. the algorithm i seek is one that can calculate the N-
Dimensional vector cross product with another N-Dimensional vector.
the solution should be mathematically correct. i am mostly concerned
with 3D and up and i am willing to enforce that the vectors be of
equal dimensions although i am not sure if that is a real mathematical
requirement. any advice?

Is the cross product of two vectors even defined if they are not both
length three?

What exactly do you mean by "mathematically correct", and what is the
data type of the input? The formula would be easiest to apply, in Java,
in double, but that would involve rounding error. If you choose one of
the representations that only involves addition, subtraction, and
multiplication you could do it exactly in BigDecimal.

Patricia
 
C

Chip Eastham

i am wondering how to write a method that calculates the cross product
of two vectors. the algorithm i seek is one that can calculate the N-
Dimensional vector cross product with another N-Dimensional vector.
the solution should be mathematically correct. i am mostly concerned
with 3D and up and i am willing to enforce that the vectors be of
equal dimensions although i am not sure if that is a real mathematical
requirement. any advice?

(this question has nothing to do with java.util.Vector obviously).

The cross product of two vectors is defined
only for dimension N = 3.

A formal expression for the cross product
between u = (a,b,c) and v = (p,r,q) is
u x v =
| X Y Z |
| a b c |
| p q r |
where unit vectors X = (1,0,0), Y = (0,1,0),
and Z = (0,0,1) are treated as commuting with
the scalars in this determinant formula.

Writing this out explicitly:

u x v = (br-cq,cp-ar,aq-bp)

The cross product u x v has the characteristic
of being orthogonal (perpendicular) to both u
and v. A higher dimensional analog can be
obtained from the formal expression above,
but it would require in N dimensions the input
of N-1 vectors. Hence only in three dimensions
is it the cross product of two vectors.

regards, chip
 
P

Patricia Shanahan

hobbes said:
i am wondering how to write a method that calculates the cross product
of two vectors. the algorithm i seek is one that can calculate the N-
Dimensional vector cross product with another N-Dimensional vector.
the solution should be mathematically correct. i am mostly concerned
with 3D and up and i am willing to enforce that the vectors be of
equal dimensions although i am not sure if that is a real mathematical
requirement. any advice?

(this question has nothing to do with java.util.Vector obviously).

Just in case. The outer product is defined for a pair of vectors of
arbitrary lengths, the cross product is not. Is it possible that you
meant "outer" rather than "cross"?

See http://en.wikipedia.org/wiki/Outer_product and
http://en.wikipedia.org/wiki/Cross_product

Patricia
 
H

hobbes

so just to clarify what i am doing, for reasons unknown i am making a
vector class in java and i want the vector object to be able to
perform all the operations that can be performed on a vector. the way
i am doing it now it could be possible to do this:

Vector v2d = new Vector(1, 2);
Vector v3d = new Vector(3, 4, 5);
Vector vx = v2d.cross(v3d);

i guess it should throw an exception here? i was looking for some
algorithm that could compute the cross product of vectors of arbitrary
length but it doesn't sound like i should be doing that in the first
place?

i also stumpled upon the java3d library and i think they are already
doing something like this but so far i dont like/understand the api
and it's kind of fun to do this anyway. but i notice their vector
classes inherit from tuple. is a vector a form of tuple and is the
cartesian product of a tuple the same as the cross product of a
vector? if so, can someone recommend an algorithm laid out somewhere i
can reference?

Patricia said:
What exactly do you mean by "mathematically correct", and what is the data type of the >input? The formula would be easiest to apply, in Java, in double, but that would involve >rounding error. If you choose one of the representations that only involves addition, >subtraction, and multiplication you could do it exactly in BigDecimal.

so the vector coordinates could be read as int, float, or double for
what i am doing and actually the coordinates are stored as an array of
Point2D objects so that I can store the initial and terminal points in
pairs, which on second thought should be tuples which contain pairs of
"Number" instead of primitives?


public Vector(double... c) {
this.coordinates = new Point2D[c.length];
for (int i = 0; i < c.length; i++)
this.coordinates = new Point2D.Double(0, c);
//overloaded constructors create Point for int, Point2D.Float for
float
}//constructor

the operations from there on out are basically manipulating the values
in the array.

Patricia said:
Is it possible that you meant "outer" rather than "cross"?

i did mean cross product. i dont think i ever learned outter product
but it sounds like something i should implement at some point. 
 
P

Patricia Shanahan

hobbes said:
so just to clarify what i am doing, for reasons unknown i am making a
vector class in java and i want the vector object to be able to
perform all the operations that can be performed on a vector. the way
i am doing it now it could be possible to do this:

Vector v2d = new Vector(1, 2);
Vector v3d = new Vector(3, 4, 5);
Vector vx = v2d.cross(v3d);

i guess it should throw an exception here? i was looking for some
algorithm that could compute the cross product of vectors of arbitrary
length but it doesn't sound like i should be doing that in the first
place?

If you really want to do cross product with this form of Java call, I
suggest limiting it to length 3.

You could subclass IllegalArgumentException to report inappropriate inputs.

An alternative, which moves the checking to compile time, would be to
define a 3 dimensional subclass of your Vector, say Vector3, and only
provide cross product in class Vector3, as "Vector3 crossProduct(Vector3
v3d)"

Also, I suggest not using "Vector". I know you can distinguish it from
java.util.Vector through package name, but the functions are a bit too
similar to avoid all risk of confusion if someone reading your code
skips the import statements.
i also stumpled upon the java3d library and i think they are already
doing something like this but so far i dont like/understand the api
and it's kind of fun to do this anyway. but i notice their vector
classes inherit from tuple. is a vector a form of tuple and is the
cartesian product of a tuple the same as the cross product of a
vector? if so, can someone recommend an algorithm laid out somewhere i
can reference?

A tuple is one way of representing a vector, but a vector has specific
semantics, such as rules for addition and products, that are not
inherent to a tuple.

Cartesian product is more closely related to outer product than to cross
product, and you say you really want cross product, so it does not help.
so the vector coordinates could be read as int, float, or double for
what i am doing and actually the coordinates are stored as an array of
Point2D objects so that I can store the initial and terminal points in
pairs, which on second thought should be tuples which contain pairs of
"Number" instead of primitives?

What are "the initial and terminal points"?

I'm still not sure what you mean by "mathematically correct". You will
not, in general, get exact results using double or float, because of
rounding error.

Note that all possible values of int and float can be represented
exactly as double, so you could make things easier for yourself by
always storing double, and converting to float or int if you are asked
for those values.

Regardless of how you store your data, be careful to define rules for
rounding and overflows.

Patricia
 
L

Lasse Reichstein Nielsen

hobbes said:
Vector v2d = new Vector(1, 2);
Vector v3d = new Vector(3, 4, 5);
Vector vx = v2d.cross(v3d);

i guess it should throw an exception here?

Indeed. I would create a new exception for this, or simply use
UnsupportedOperationException.
i was looking for some algorithm that could compute the cross
product of vectors of arbitrary length but it doesn't sound like i
should be doing that in the first place?

No, it's only defined for 3-dimensional vectors.

For higher dimensions, I guess you could define something that required
n-1 vectors of n dimensions.
but i notice their vector classes inherit from tuple. is a vector a
form of tuple

Sure. An n-dimensional vector is an n-tuple, i.e., a member of the
(Cartesian) product of n sets.
and is the cartesian product of a tuple the same as the cross
product of a vector?

Cartesian product is a product of sets. The cross product is a product
on elements in a three-dimensional tuple space, typically R^3 or similar.
if so, can someone recommend an algorithm laid out somewhere i can
reference?

This one should be simple:
<URL:http://en.wikipedia.org/wiki/Cross_product#Coordinate_notation>
I.e.,
(a1,a2,a3) x (b1,b2,b3) = (a2*b3 - a3*b2, a3*b1 - a1*b3, a1*b2 - a2*b1)

/L
 
P

Patricia Shanahan

Lasse said:
Indeed. I would create a new exception for this, or simply use
UnsupportedOperationException.

I suggested subclassing IllegalArgumentException. I think the
distinction between that and UnsupportedOperationException is whether
there are any implementations that would support the operation.

IllegalArgumentException is "Thrown to indicate that a method has been
passed an illegal or inappropriate argument."

UnsupportedOperationException is "Thrown to indicate that the requested
operation is not supported." It is used, for example, for an attempt to
add an element to a set returned by Collections.unmodifiableSet. There
are other Set implementations for which adding an element is a valid
operation.

My reasoning was that attempting cross product of two vectors of
different length is more a case of an illegal or inappropriate argument.

Patricia
 
L

Lasse Reichstein Nielsen

Patricia Shanahan said:
I suggested subclassing IllegalArgumentException. I think the
distinction between that and UnsupportedOperationException is whether
there are any implementations that would support the operation.

IllegalArgumentException was my first idea too, but the argument is
fine (it's a 3-D vector), while the object that the method is called
on is not (it's 2-D). I.e., the v2d object does not support cross
products.

However, if you called v3d.cross(v2d), maybe it should be an illegal
argument exception. This inconsistency is why I would prefer a new
exception.
My reasoning was that attempting cross product of two vectors of
different length is more a case of an illegal or inappropriate argument.

It's definitly illegal, but it's not the argument that's at fault :)

/L
 
P

Patricia Shanahan

Lasse said:
IllegalArgumentException was my first idea too, but the argument is
fine (it's a 3-D vector), while the object that the method is called
on is not (it's 2-D). I.e., the v2d object does not support cross
products.

Good point.
However, if you called v3d.cross(v2d), maybe it should be an illegal
argument exception. This inconsistency is why I would prefer a new
exception.

This is, perhaps, an unfortunate consequence of the asymmetry introduced
into a naturally commutative operation by using the v2d.cross(v3d) notation.

If it had been a static method Vector.cross(v2d,v3d) I'm sure it should
be IllegalArgumentException. As it is, your new exception recommendation
is probably the way to go.

Patricia
 
H

hobbes

Not to beat a dead horse, but is it possible to view the cross product
of two vectors as the determinant of 3 matrices (the two matrices in
question and the standard unit component vector)? From my very limited
understanding of it from reading in wikipedia, it seems that it would
be possible to at least get a 2D & 3D cross product represented as the
cofactor expansion.

thanks for the jscience link by the way, i was looking around for
something similar but hadn't found it yet. it seems quite through
although complicated too. i wish more math and physics operations were
represented in the standard java api. for a languaged noted for having
a thorough built in api, it seems surprisingly sparse when it comes to
math and science. as far as i know there is just one final Math class
which doesn't do a lot.
 
C

Chip Eastham

Not to beat a dead horse, but is it possible
to view the cross product of two vectors as
the determinant of 3 matrices (the two matrices in
question and the standard unit component vector)?

Yes, this is a standard formulation which
I mention in my early post to this thread
(assuming by "the two matrices" you mean
the two operand vectors used as two rows
of the matrix whose determinant is taken).

This representation makes it clear why the
result is orthogonal to the two operand
vectors and points to a clumsy higher
dimensional analog (clumsy because N-1
input vectors are needed in N dimensions).

regards, chip
 
J

Joshua Cranmer

hobbes said:
thanks for the jscience link by the way, i was looking around for
something similar but hadn't found it yet. it seems quite through
although complicated too. i wish more math and physics operations were
represented in the standard java api. for a languaged noted for having
a thorough built in api, it seems surprisingly sparse when it comes to
math and science. as far as i know there is just one final Math class
which doesn't do a lot.

One proposal for Java 7 is to integrate parts of the JScience API into
the language.

Furthermore, I do not consider Java's lack of heavy-duty math/science
API's surprising. Typically, most applications requiring large-scale
matrices (for example) would prefer to use a platform that is less
expensive in terms of runtime efficiency (e.g. C). The largest math
applications would be run on supercomputers, a realm in which FORTRAN is
the most used (it's more intuitive for non-programmers than C-based
languages). Early Java had some severe speed problems, and, although the
picture has improved to the point that it is competitive with
native-code languages in the long-term, it still has not shaken off that
perception.
 
M

Mike Schilling

Chip Eastham said:
Yes, this is a standard formulation which
I mention in my early post to this thread
(assuming by "the two matrices" you mean
the two operand vectors used as two rows
of the matrix whose determinant is taken).

This representation makes it clear why the
result is orthogonal to the two operand
vectors and points to a clumsy higher
dimensional analog (clumsy because N-1
input vectors are needed in N dimensions).

I'm missing something. How can the cross product (which is a vector) be the
same as a determinant (which is a scalar)?
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,754
Messages
2,569,528
Members
45,000
Latest member
MurrayKeync

Latest Threads

Top