How can this code retrieve a 2D vector from a cross-product of two 2D vectors?

Question

I am in a lost. I have been trying to implement this code at:http://www.blackpawn.com/texts/pointinpoly/default.html

However, I don't know how is it possible that the cross-product present there between two 2D vectors can result also in a 2D vector. It does not make sense to me. That is also present in some examples of intersection between polygons and lines, in the fine book "Realtime Collision Detection" - where even scalar triples between 2D vectors appear in the codes (see page 189, for instance).

The issue is that, as far as I can think of it, the pseudo cross-product of two 2D vectors can only result in a scalar (v1.xv2.y-v1.yv2.x) or at most in a 3D vector if one adds two zeros, since that scalar represents the Z dimension. But how can it result in a 2D vector?

I am not the first one to ask this and, coincidently, when trying to use the same code example: Cross product of 2 2D vectors However, as can be easily seen, the answer, the original question when updated and the comments in that thread ended up being quite a mess, if I dare say so.

Does anyone know how should I get these 2D vectors from the cross-product of two 2D vectors? If code is to be provided, I can handle C#, JavaScript and some C++.

EDIT - here is a piece of the code in the book as I mentioned above:

int IntersectLineQuad(Point p, Point q, Point a, Point b, Point c, Point d,     Point &r)
{
Vector pq = q - p;
Vector pa = a - p;
Vector pb = b - p;
Vector pc = c - p;
// Determine which triangle to test against by testing against diagonal     first
Vector m = Cross(pc, pq);
float v = Dot(pa, m); // ScalarTriple(pq, pa, pc);
if (v >= 0.0f) {
   // Test intersection against triangle abc
   float u = -Dot(pb, m); // ScalarTriple(pq, pc, pb);
   if (u < 0.0f) return 0;
   float w = ScalarTriple(pq, pb, pa);
....

You're talking about "Same Side Technique", right? The cross product of 2 3d vectors in the XY plane is a vector parallel to the Z axis. The cross2d of 2 2d-vectors is the Z component of the 3d cross, so the dot product mentioned there can be obtained by simply multiplying the values of the two 2d crosses (I.e. dotting the 3d crosses which are parallel to the Z axis and hence each other). — dbc
Thanks for your comment. So, yes, that's the technique I had in mind. What you are saying is that the Dot product would be just a multiplication of the two scalars given by the cross-product of the 2 2D vectors? But take a look at the example from the book I've just included in original question. In that example I should just multiply the whole 2D vector pa by the scalar that results from the cross-product of pc and pq? — MAnd
@dbc Notice that in the provided example the author stores the cross-product of the 2D vectors pc and pq in a vector called "m". If I go direct to your suggestion and simply do the usual calculation for a cross-product between two 2D vectors, save it in "m" (declaring it as a float) and then direclty multiply "m" and the vector "pa", then "v" cannot be a float as in the example — MAnd
I wrote my comment using your original question that had no code sample, based on the linked algorithm. The code sample in the update doesn't seem to correspond to that algorithm -- it's something completely different. It appears to be working with 3d vectors not 2d. — dbc

Petr Petr · Accepted Answer · 2015-09-30T08:04:26

For the page you linked, it seems that they talk about a triangle in a 3d space:

Because the triangle can be oriented in any way in 3d-space, ...

Hence all the vectors they talk about are 3d vectors, and all the text and code makes perfect sense. Note that even for a 2d vectors everything also makes sense, if you consider a cross product to be a 3d vector pointing out of screen. And they mention it on the page too:

If you take the cross product of [B-A] and [p-A], you'll get a vector pointing out of the screen.

Their code is correct too, both for 2d and 3d cases:

function SameSide(p1,p2, a,b)
    cp1 = CrossProduct(b-a, p1-a)
    cp2 = CrossProduct(b-a, p2-a)
    if DotProduct(cp1, cp2) >= 0 then return true
    else return false

For 2d, both cp1 and cp2 are vectors pointing out of screen, and the (3d) dot product is exactly what you need to check; checking just the product of corresponding Z components is the same. If everything is 3d, this is also correct. (Though I would write simply return DotProduct(cp1, cp2) >= 0.)

For int IntersectLineQuad(), I can guess that the situation is the same: the Quad, whatever it is, is a 3d object, as well as Vector and Point in code. However, if you add more details about what is this function supposed to do, this will help.

In fact, it is obvious that any problem stated in 2d can be extended to 3d, and so any approach which is valid in 3d will also be valid for 2d case too, you just need to imagine a third axis pointing out of screen. So I think this is a valid (though confusing) technique to describe a 2d problem completely in 3d terms. You might yourself doing some extra work, because some values will always be zero in such an approach, but in turn the (almost) same code will work in a general 3d case too.

How can this code retrieve a 2D vector from a cross-product of two 2D vectors?

1 Answers