如何检查给定单元格是否阻塞了二维数组中两个单元格之间的直接路径？

Question

细胞A和细胞B之间的直线是否被细胞C阻塞，最简单的方法是什么？即

如果单元A为0，0，B为2，2，细胞C为1,1，则C单元阻塞单元A和B之间的路径。如果单元B是对角线上的任何其他单元(3、3、4、4等)，则C仍会阻塞单元A与B之间的路径，但如果单元C是任何其他单元，则不会阻塞该路径。

比如，使用A，B和C单元的位置，我需要检查哪些条件？

Answer 1

一些简单的线性代数。考虑两个向量，AB和AC，如果行列式为零，它们是平行的。如果点乘积是正的，它们指向相同的方向。C是沿着AB路径的，如果前面是真的，AC比AB短。为了看AC是否比AB短，我们可以比较它们长度的平方，避免平方根。

因此，我们可以在恒定的时间内用加法、减法和乘法来计算这一点。它甚至适用于所有的精确整数坐标；这些线不需要是水平的、垂直的或对角的。

#include <stdio.h>

struct vec { int x; int y; };

int determinant(struct vec a, struct vec b) {
    return a.x * b.y - b.x * a.y;
}

int dot_product(struct vec a, struct vec b) {
    return a.x * b.x + a.y * b.y;
}

int len_squared(struct vec v) {
    return dot_product(v, v);
}

int blocks(struct vec a, struct vec b, struct vec c) {
    struct vec ab = {b.x - a.x, b.y - a.y};
    struct vec ac = {c.x - a.x, c.y - a.y};

    return determinant(ab, ac) == 0 &&
           dot_product(ab, ac) > 0 &&
           len_squared(ac) < len_squared(ab);
}

int main(void) {
    struct vec a = {0, 0}, b = {2, 2}, c = {1, 1};
       
    if (blocks(a, b, c)) {
        puts("Blocks");
    }
    else {
        puts("Does not block");
    }
}