What is cross product in $2D$ space and how does it help detect if $2$ line segments intersect?

Question

I am having to solve a problem from computational geometry which involves finding out if $2$ given line segments intersect.

More about the problem I am trying to solve over here if anyone is interested.

Now I keep coming across the following calculation:

(v1.X*v2.Y) - (v1.Y*v2.X)

It is suppose to be the vector cross product in 2D.

Now I have a couple of questions:

1. What is the vector cross product in $2D$ ? Its not even defined there, so what is going on ?
2. If the cross product is used so extensively why is it called as "mathematical hack" ? Everyone seems to be expected to know about it.
3. How does it help when finding out if $2$ lines intersect or not ? What does it have to do with orientation like here.

I want to know how I can use this calculation to find out if $2$ lines intersect. What is the intuition behind it ?

How does it help ?

Thanks.

Answer 1

The "vector cross product in 2D" is neither a product (in the strict sense), nor a "vector", nor is it really in 2D. Other than that, it's well named. :(

The ordinary cross product takes a pair of nonzero vectors in 3-space, $u$ and $v$, and produces a new vector $w = u \times v$ whose length is the area of the parallelogram spanned by $u$ and $v$ (hence the length may be zero), and whose direction (if $w$ is nonzero) is perpendicular to $u$ and $v$, and has the property that $u, v, w$ (in that order) form a right-hand-oriented basis of 3-space.

If you have a pair of vectors $u$ adn $v$ in the plane, you can append a $0$ to each one, so if $u = (a, b)$, you get $U = (a, b, 0)$, and similarly for $v$. Then $W = U \times V$ is a vector in 3-space perpendicular to both (but possibly zero!). Well, perpendicular to both means that it must have the form $$ W = (0, 0, z) $$ and the expression you've written down is exactly the formula for that $z$ component. That means that if $u, v$ is a positively-oriented basis for the plane, then the "2D cross product" will be positive; if it's negatively oriented, the "product" will be negative. And if it's zero, then one of the vectors $u$ adn $v$ is a multiple of the other.

As for testing for intersection of segments, probably your best bet is to look for papers by Thomas Akenine-Moller, who has pretty much written the be-all and end-all of such papers. There's no reason to rehash the contents here.

Answer 2

There exists another product of vectors called the wedge product. The wedge product of two vectors creates a 2-dimensional directed/oriented object called a bivector, and the wedge product of a $m$-dimensional and a $n$-dimensional directed object is a $m+n$-dimensional directed object. These higher dimensional directed objects are usually called $k$-vectors. The wedge product is quite useful, as it could be used to find the area/volume of parallelograms and parallelopipeds (and higher-dimensional hyperparallelopipeds) bounded by the given vectors, for example.

For each $k$-vector in $n$-dimensional space, with $k \leq n$, there exists a dual object, a $(n - k)$-vector that is perpendicular to the original $k$-vector with the same magnitude. In 3 dimensions, the dual of a bivector yields a vector with the same magnitude perpendicular to the bivector, while in 2 dimensions, the dual of a bivector yields a scalar with the same magnitude (scalars are trivially perpendicular to higher-dimensional objects).

1. In any dimension, the cross product of two vectors can be defined as the dual of the wedge product of two vectors.
2. It is for the above reason that the cross product is called a hack, because the wedge product is more fundamental in linear algebra and geometry than the cross product. But due to historical reasons from fundamental 19th century physics, Gibb's vector algebra eventually became dominant in the study of electromagnetism, and so physicists and mathematicians use the cross product instead of the wedge product.
3. Two vectors are parallel if the wedge product (and consequently the cross product) of the two vectors is zero. The given formula calculates the magnitude of the wedge product of two vectors in two dimensions. In two dimensions, any two distinct lines lie on the same plane, and so if the wedge product of two vectors defining the two lines are zero, then the two lines are parallel; otherwise, they intersect.

See also:

https://en.wikipedia.org/wiki/Exterior_algebra#Motivating_examples