Java Forum / General / August 2007
Algorithm for Vector Cross Product of N Dimensions
hobbes - 22 Aug 2007 14:13 GMT 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).
GArlington - 22 Aug 2007 14:26 GMT > 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- [quoted text clipped - 5 lines] > > (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.
Christian - 22 Aug 2007 14:26 GMT hobbes schrieb:
> 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- [quoted text clipped - 5 lines] > > (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
Twisted - 22 Aug 2007 14:43 GMT > If I remember correctly cross product is restricted to 3 diemnsional > Vectors. 3 and 7, wasn't it?
Virgil - 22 Aug 2007 20:42 GMT > > If I remember correctly cross product is restricted to 3 diemnsional > > Vectors. > > 3 and 7, wasn't it? So I have heard. Though the 7 dimensional case does not seem to come up very often.
Patricia Shanahan - 22 Aug 2007 14:30 GMT > 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- [quoted text clipped - 3 lines] > 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
Chip Eastham - 22 Aug 2007 14:38 GMT > 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- [quoted text clipped - 5 lines] > > (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
GArlington - 30 Aug 2007 16:18 GMT > > 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- [quoted text clipped - 32 lines] > > regards, chip I was just wondering: what is the difference between vectors X = (1,0,0) and Y = (1,0) and in fact Z = (1)?
Wildemar Wildenburger - 30 Aug 2007 19:22 GMT > I was just wondering: what is the difference between vectors X = > (1,0,0) and Y = (1,0) and in fact Z = (1)? Uhm ... the dimension?
/W
Patricia Shanahan - 22 Aug 2007 16:46 GMT > 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- [quoted text clipped - 5 lines] > > (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
hobbes - 22 Aug 2007 20:15 GMT 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?
>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[i] = new Point2D.Double(0, c[i]); //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.
>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.
Patricia Shanahan - 22 Aug 2007 20:42 GMT > 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 [quoted text clipped - 9 lines] > 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 [quoted text clipped - 3 lines] > 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.
>> 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. > [quoted text clipped - 3 lines] > 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
Lasse Reichstein Nielsen - 22 Aug 2007 20:45 GMT > 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
 Signature Lasse Reichstein Nielsen - lrn@hotpop.com DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html> 'Faith without judgement merely degrades the spirit divine.'
Patricia Shanahan - 22 Aug 2007 21:17 GMT >> Vector v2d = new Vector(1, 2); >> Vector v3d = new Vector(3, 4, 5); [quoted text clipped - 4 lines] > 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
Lasse Reichstein Nielsen - 22 Aug 2007 22:09 GMT >>> Vector vx = v2d.cross(v3d); >>> [quoted text clipped - 5 lines] > 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
 Signature Lasse Reichstein Nielsen - lrn@hotpop.com DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html> 'Faith without judgement merely degrades the spirit divine.'
Patricia Shanahan - 22 Aug 2007 22:21 GMT >>>> Vector vx = v2d.cross(v3d); >>>> [quoted text clipped - 9 lines] > 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
Hunter Gratzner - 22 Aug 2007 21:22 GMT > so just to clarify what i am doing, for reasons unknown i am making a > vector class in java http://jscience.org/api/org/jscience/mathematics/vector/package-summary.html
hobbes - 25 Aug 2007 00:49 GMT 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.
Chip Eastham - 25 Aug 2007 00:55 GMT > 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
Mike Schilling - 25 Aug 2007 01:35 GMT >> Not to beat a dead horse, but is it possible >> to view the cross product of two vectors as [quoted text clipped - 12 lines] > 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)?
Brian VanPelt - 25 Aug 2007 03:24 GMT >>> Not to beat a dead horse, but is it possible >>> to view the cross product of two vectors as [quoted text clipped - 15 lines] >I'm missing something. How can the cross product (which is a vector) be the >same as a determinant (which is a scalar)? The determinant he is speaking of is simply a mechanism that helps to remember how to compute a cross product. This "determinant" is not a scalar.
Check out this link
http://mathworld.wolfram.com/CrossProduct.html
and look at (3).
Brian
Mike Schilling - 25 Aug 2007 08:33 GMT >> I'm missing something. How can the cross product (which is a >> vector) be the same as a determinant (which is a scalar)? [quoted text clipped - 8 lines] > > and look at (3). That's clever. Thanks.
Joshua Cranmer - 25 Aug 2007 01:29 GMT > 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 [quoted text clipped - 3 lines] > 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.
 Signature Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
|
|