Блог

Главная - Вопросы по программированию - Как проверить, заблокирован ли прямой путь между двумя ячейками в 2D-массиве данной ячейкой?

Как проверить, заблокирован ли прямой путь между двумя ячейками в 2D-массиве данной ячейкой?

#c

#c

Вопрос:

Какой самый простой способ определить, заблокирована ли прямая линия между ячейкой 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, какие условия я должен был бы проверить для этого?

Комментарии:

1. они всегда горизонтальные, вертикальные или диагональные на 45 градусов или как?

2. Да, по горизонтали, вертикали или по любой диагонали 45 градусов.

3. Даже в общем случае вы можете рассматривать AB и AC как векторы, и если определитель равен нулю , они коллинеарны, тогда вам просто нужно посмотреть, находится ли AB в том же направлении, что и AC, и что AC короче AB

Ответ №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 amp;amp;
           dot_product(ab, ac) > 0 amp;amp;
           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");
    }
}