Пересечение линии с AABB Rectangle? - PullRequest
Новая
       86

Пересечение линии с AABB Rectangle?

16 голосов
/ 19 сентября 2010

Желательно без использования какого-либо цикла, так как это будет использоваться в игре.

Я хочу пересечь линию с прямоугольником произвольного размера. Но я также хотел бы, чтобы точка пересечения была возвращена.

Возможно, я немного погуглил, но все еще не решил.

Строка определяется с помощью (x1, y1, x2, y2). Прямоугольник также имеет эти две точки.

1 Ответ

43 голосов
/ 19 сентября 2010

Я бы порекомендовал просто выполнить проверку пересечения линия-сегмент-линия-сегмент на каждом отрезке (ребре), составляющем прямоугольник.Вот алгоритм обнаружения пересечения отрезка линии, который я написал несколько лет назад, взятый из одного из моих старых проектов XNA: 

// a1 is line1 start, a2 is line1 end, b1 is line2 start, b2 is line2 end
static bool Intersects(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 intersection)
{
    intersection = Vector2.Zero;

    Vector2 b = a2 - a1;
    Vector2 d = b2 - b1;
    float bDotDPerp = b.X * d.Y - b.Y * d.X;

    // if b dot d == 0, it means the lines are parallel so have infinite intersection points
    if (bDotDPerp == 0)
        return false;

    Vector2 c = b1 - a1;
    float t = (c.X * d.Y - c.Y * d.X) / bDotDPerp;
    if (t < 0 || t > 1)
        return false;

    float u = (c.X * b.Y - c.Y * b.X) / bDotDPerp;
    if (u < 0 || u > 1)
        return false;

    intersection = a1 + t * b;

    return true;
}

Я оставлю ввод каждого ребра в вышеописанный метод и собираю результаты в качестве упражнения длячитатель:)

Редактировать 1 год спустя, теперь я поступил в университет и прошел курс по графике:

Взгляните на алгоритм Коэна – Сазерленда сделать это эффективно, когда у вас есть большой набор линий, большинство из которых не пересекают прямоугольник.Он использует сетку из 9 сегментов, и вы помещаете каждую конечную точку линии в область указанной сетки:

grid

Используя это, мы можем сказать, не будет ли пересечений линий:

grid with lines

Например, здесь CD не будет пересекать прямоугольник (показан красным на первом изображении), так как C и D находятся в верхнем ряду ини один не будет AB.Для тех, где линия может пересекать прямоугольник, мы должны попробовать пересечения линии с линией.

Они обозначают / обозначают сечения, что позволяет нам просто сделать x AND y != 0 (где x и y - это метки сечений для каждой из конечных точек линии), чтобы определить, не будет ли пересечения.

Использование этого метода означает, что у нас будет намного, намного меньше пересечений линий и линий, что ускоряетвсе это массово.

...