Я бы порекомендовал просто выполнить проверку пересечения линии-сегмента-линии-сегмента на каждом сегменте линии (ребре), из которого состоит прямоугольник. Вот алгоритм обнаружения пересечения отрезков, который я написал много лет назад, извлеченный из одного из моих старых проектов 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 сегментов, и вы помещаете каждую конечную точку линии в область указанной сетки:
Используя это, мы можем сказать, не будет ли пересечений линий:
Например, здесь CD
не будет пересекать прямоугольник (показан красным на первом изображении), так как C
и D
находятся в верхнем ряду, а AB
тоже. Для тех, где линия может пересекать прямоугольник, мы должны попробовать пересечения линии.
То, как секции пронумерованы/помечены, позволяет нам просто выполнить x AND y != 0
(где x
и y
— метки секций для каждой из конечных точек линии), чтобы определить, не будет ли пересечения.
Использование этого метода означает, что у нас будет намного меньше пересечений линий, что значительно ускоряет все это.
person
Callum Rogers
schedule
19.09.2010