3

我在理解 ccw（逆时针）算法时遇到了一些麻烦：

int ccw (Point P0, Point P1, Point P2) {
    dx1 = P1.x - P0.x;
    dx2 = P2.x - P0.x;
    dy1 = P1.y - P0.y;
    dy2 = P1.y - P0.y;

    if (dy1 * dx2 > dy2 * dx1) return -1;
    if (dx1 * dy2 > dy1 * dx2) return 1;
    if ((dx1 * dx2 < 0) || (dy1 * dy2 < 0)) return 1;
    if ((dx1 * dx1 + dy1 * dy1) < (dx2 * dx2 + dy2 * dy2)) return -1;
    return 0;
}

此代码用于查看两条线是否相交：

bool intersect (Vector2D l1, Vector2D l2) {
    return (((ccw(l1.start, l1.end, l2.start) * ccw(l1.start, l1.end, l2.end)) <= 0)
    && ((ccw(l2.start, l2.end, l1.start) * ccw(l2.start, l2.end, l1.start)) <= 0))
}

intersect 函数里面的代码我能看懂，但是ccw 函数里面的代码我不是很懂。

为什么不使用叉积？

4

1 回答 1

5

函数内部的代码ccw是以一种相当特殊的方式编写的，但它确实使用了有时非常非正式地称为 2D 版本的cross product。对于两个向量(dx1, dy1)，并且(dx2, dy2)该乘积被定义为一个标量值，等于

CP = dx1 * dy2 - dx2 * dy1;

（在形式上正确的术语中，CP实际上是向量和的经典 3D 叉积的有符号幅度。）显然，该值只是一个标量（点）积，其中一个向量被其垂直线替换。(dx1, dy1, 0)(dx2, dy2, 0)

如果 的值为CP正，则从(dx1, dy1)到的最短径向扫掠(dx2, dy2)为逆时针方向。负数CP表示顺时针扫过。零CP表示共线向量。（所有这些都假设 Y 轴向上，X 轴向右。）

显然，CP > 0条件等价于dx1 * dy2 > dx2 * dy1条件，CP < 0等价于dx1 * dy2 < dx2 * dy1。这正是您的ccw函数在前两个ifs 中检查的内容。

剩下if的 s 正在处理共线的情况。

如果向量指向相反的方向（由第三个 检测到if），即P0位于 和 之间P1时P2，函数总是返回1，表示逆时针排序。好吧，我想这只是代码作者假设的约定。

最后，如果两个向量指向相同的方向，即P0位于P1-P2线段之外，则基于向量长度（第四个if）做出决定。如果P1比 更接近P2，P0则报告顺时针顺序。否则，如果P2更接近，则报告逆时针排序。这也只是代码作者假定的约定。

而且，从其余的代码来看，这不是两条线的交集。它是关于两个部分的交集。

于 2014-10-11T17:40:45.450 回答