c++ - ccw算法讲解

Question

我在理解 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函数里面的代码。

为什么不用叉积？

Answer 1

里面的代码ccw函数是以一种相当特殊的方式编写的，但它确实使用了有时非常非正式地称为 叉积 的 2D 版本的东西。对于两个 vector (dx1, dy1)和 (dx2, dy2)该产品被定义为标量值等于

CP = dx1 * dy2 - dx2 * dy1;

(在形式上正确的术语中，CP 实际上是 vector (dx1, dy1, 0) 和 (dx2, dy2, 0) 的经典 3D 叉积的有符号大小。)显然，该值只是一个 em>标量(点)乘积，其中一个 vector 被其垂线所取代。

如果值为CP为正，则从 (dx1, dy1) 开始的最短径向扫描至 (dx2, dy2)逆时针旋转。否定CP表示顺时针扫描。 CP 中的零表示共线 vector 。 (所有这些都假设 Y 轴指向上方，X 轴指向右侧。)

显然，CP > 0条件等同于 dx1 * dy2 > dx2 * dy1条件和 CP < 0相当于dx1 * dy2 < dx2 * dy1 .这正是你的 ccw前两个函数检查 if秒。

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

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

最后，如果两个 vector 指向同一方向，即当P0位于P1-P2之外段，决定基于 vector 长度(第四个 if )。如果P1比 P2 更近至 P0 , 报告顺时针顺序。否则，如果 P2更近，报告逆时针顺序。这也只是代码作者的约定。

而且，从其余代码来看，这与两条线的交集无关。它是关于两个片段的交集。