Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / August 2007

Tip: Looking for answers? Try searching our database.

Algorithm for Vector Cross Product of N Dimensions

Thread view: 
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 Magazines

Get 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 ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.