二维叉积定义

Question

在 determine if line segment is inside polygon 中，我注意到接受的答案有一个不寻常的二维交叉产品定义：

(u1, u2) x (v1, v2) := (u1 - v2)*(u2 - v1)

我从来没有遇到过像这样的二维叉积的定义。谁能告诉我这个定义是从哪里来的？

Answer 1

不是数学专家，但 ND 中的 CROSS 乘积定义为 N-1 向量的运算，产生垂直于每个向量的向量。这些东西被计算为矩阵的行列式，其中它的第一行是单位方向向量(i,j,k,...)，其他每一行都包含每个向量操作数。所以对于 2D 是：

cross( (x0,y0) ) = | i  j  | = i*y0 - j*x0 = (y0,-x0)
                   | x0 y0 |

垂直于(x0,y0)。 所以你得到的不是二维叉积!!!

在 CG 中通常需要通过 3D 叉积获得某个 2D 表面的法向量：

cross( (x0,y0,z0),(x1,y1,z1) ) = | i  j  k  | = i*(y0*x1-z0*y1) + j*(z0*x1-x0*z1) + k*(x0*y1-y0*x1)
                                 | x0 y0 z0 |
                                 | x1 y1 z1 |

现在，如果两个向量 (x0,y0,z0),(x1,y1,z1) 是二维的，那么 z0,z1 都是零，所以：

cross( (x0,y0,z0),(x1,y1,z1) ) = i*(y0*x1-0*y1) + j*(0*x1-x0*0) + k*(x0*y1-y0*x1)
cross( (x0,y0,z0),(x1,y1,z1) ) = k*(x0*y1-y0*x1)
cross( (x0,y0,z0),(x1,y1,z1) ) = (0,0,x0*y1-y0*x1)

这与您的定义更相似，但看起来不一样，所以您拥有的是其中之一：

不同的东西不是叉积
用我还没有看到的一些数学恒等式转换的叉积。
那个答案中的错误（小错别字，或复制错误的代码行......我也经常遇到）
更多方程融合在一起（交叉只是该答案的一小部分）

在 linked 答案的上下文中 您需要 3D 叉积 z 坐标 结果：

z = x0*y1-y0*x1

哪个标志会告诉您关于多边形缠绕规则及其边缘之一的点是 CW 还是 CCW...

但为了绝对清楚，您应该直接在那个问题线程中问这个 Niklas B.（使用评论），因为您的代表很低，我会为您做，link 您的问题在那里。 ..

Answer 2

Wikipedia's entry on Cross Product, section "Computational geometry" 说明：

In computational geometry of the plane, the cross product is used to determine the sign of the acute angle defined by three points.

p₁ = (x₁,y₁), p₂=(x₂,y₂) and p₃ = (x₃, y₃). It corresponds to the direction (upward or downward) of the cross product of the two coplanar vectors defined by the two pairs of points (p₁, p₂) and (p₁, p₃). The sign of the acute angle is the sign of the expression

P = (x₂ − x₁)(y₃ − y₁) − (y₂ − y₁)(x₃ − x₁)

which is the signed length of the cross product of the two vectors.

the other question & answer you refer to中叉积的定义与此有偏差，不正确。

这里我提供了一个可运行的小片段，可以通过画一个角度来测试两个不同的公式。上面引用的p₁固定在中间。其他两个点可以通过鼠标按下 (u) 和拖动 (v) 来定义。在按住鼠标的同时，点 u 跟随光标。您可以同时查看两个竞争公式的计算值。显然，（正确的）叉积符号指示第三点相对于固定点和第二点在哪“边”。

let translation = { x: 150, y: 75 };
let zero = { x: 0, y: 0 };
let ctx = document.querySelector("canvas").getContext("2d");
let output1 = document.querySelector("#p1");
let output2 = document.querySelector("#p2");
let u;
let isMouseDown = false;

function drawLine(ctx, a, b, color="black") {
    ctx.beginPath();
    ctx.moveTo(a.x, a.y);
    ctx.lineTo(b.x, b.y);
    ctx.strokeStyle = color;
    ctx.stroke();
}

function text(ctx, a, txt, color) {
    ctx.fillStyle = color;
    ctx.fillText(txt, a.x+2, a.y-2);
}

function refresh(ctx, u, v) {
    ctx.setTransform(1,0,0,1,0,0);
    ctx.clearRect(0, 0, ctx.canvas.width, ctx.canvas.height);
    ctx.translate(translation.x, translation.y);
    drawLine(ctx, zero, u, "black");
    drawLine(ctx, zero, v, "red");
    text(ctx, u, "U", "black");
    text(ctx, v, "V", "red");
    output1.textContent = (u.x - v.y) * (u.y - v.x);
    output2.textContent = u.x * v.y - u.y * v.x;
}

let getXY = (e) => ({ 
    x: e.clientX-e.target.offsetLeft - translation.x,
    y: e.clientY-e.target.offsetTop - translation.y,
});

ctx.canvas.onmousedown = function(e) {
    u = getXY(e);
    refresh(ctx, u, u);
    isMouseDown = true;
}

ctx.canvas.onmouseup = () => isMouseDown = false;

ctx.canvas.onmousemove = function(e) {
    if (!isMouseDown) return;
    let v = getXY(e);
    refresh(ctx, u, v);
}

canvas { border: 1px solid; float: left }

<canvas width="300" height="150"></canvas>
<pre> Wrong: (u.x−v.y) * (u.y−v.x): <span id="p1"></span>
 Right: u.x * v.y − u.y * v.x: <span id="p2"></span>
</pre>

Answer 3

我建议你看看Exterior Algebra。它概括了叉积和行列式的概念。 "Motivation examples" 描述平面区域的部分完全回答了您的问题。

它适用于任何维度。 3D 是一种特殊情况，其中两个向量的叉积结果也有 3 个分量。但是，在 2D 中，只有一个结果分量，而在 4D 中，有 6 个。在 4D 中，您可以应用一种使用 3 个向量的叉积，这也给您 4 个分量。

需要注意的是，虽然3D叉积的结果有3个分量，但单位和含义是不同的。例如，x 分量具有面积单位，表示 YZ 平面中的面积，与 "standard" 向量相反，其中 x 分量具有长度单位，不同之处在于坐标。使用外代数，这些差异变得更加清晰，因为符号也不同（dx vs dy^dz）。

注意：您引用的答案有误。而不是(u1, u2) x (v1, v2) := (u1 - v2)*(u2 - v1)，应该是(u1, u2) x (v1, v2) := u1*v2 - u2*v1

二维叉积定义

2d cross product definition

algorithm

geometry

2d

linear-algebra