Ответ 1
Я бы рекомендовал просто выполнить проверку пересечения сегментов линии-сегмента на каждом сегменте линии (краю), который составляет прямоугольник. Вот алгоритм обнаружения пересечения сегментов линии, который я написал много лет назад, извлеченный из одного из моих старых проектов 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;
}
Я оставлю ввод каждого края в указанный выше метод и собирая результаты в виде упражнения для читателя:)
Редактировать Через год я поступил в университет и прошел курс Графика:
Взгляните на алгоритм Коэна-Сазерленда, чтобы сделать это эффективно, когда у вас есть большой набор строк, большинство из которых не пересекают прямоугольник, Он использует сетку с 9 сегментами, и вы помещаете каждую конечную точку линии в область указанной сетки:
Используя это, мы можем определить, нет ли пересечений линий:
Например, здесь CD не будет пересекать прямоугольник (показан на красном в первом изображении), так как C и D находятся в верхней строке, и не будет AB. Для тех, где линия может пересекаться с прямоугольником, мы должны попробовать пересечения линий.
Они, как разделы пронумерованы/помечены, позволяют нам просто делать x AND y != 0 (где x и y - это метки разделов для каждой из конечных точек линии), чтобы определить, не будет ли пересечения.
Использование этого метода означает, что у нас есть много, гораздо меньше пересечений линий, которые ускоряют все это в целом.