Пересечение линии и прямоугольника с максимальной длиной сегмента

Question

У меня есть вектор, представленный наклоном m.Тогда есть прямоугольник (предположим, что ось выровнена), который представлен верхним левым и нижним правым углом.Конечно, может быть много линий с наклоном m, пересекающих данный прямоугольник.Задача состоит в том, чтобы найти линию, длина пересечения которой внутри прямоугольника максимальна среди всех таких линий.то есть, если линия пересекает прямоугольник в точках P1 и P2, то проблема состоит в том, чтобы найти уравнение линии, для которой длина P1P2 максимальна.

Я поступил так.Пусть строка выглядит так: y = m * x + c.Затем найдите пересечение с каждой стороной прямоугольника и выясните максимумы для функции расстояния между каждой парой точек.Но это даст мне только длину отрезка, и, похоже, есть много угловых случаев для обработки.

Может ли кто-нибудь предложить лучший способ сделать это.

Заранее спасибо.

Answer 1

Думайте об этом, как будто вы хотите масштабировать треугольник, чтобы он поместился внутри прямоугольника. Рассмотрим треугольник с шириной основания 1.

мы знаем, что dy / dx = m, поэтому высота треугольника с таким же наклоном равна m.

Теперь возьмите свой прямоугольник и определите максимальный масштаб, который соответствует треугольнику внутри прямоугольника. Для положительного m:

min(rectWidth, rectHeight/m)

Это шкала, которую мы должны использовать, чтобы подогнать треугольник внутри прямоугольника. Теперь с помощью теоремы Пятигора легко получить длину пересечения

scale = min(rectWidth, abs(m/rectHeight)) // m could be negative so we take abs
length = sqrt(scale*scale + scale*m*scale*m)

Обратите внимание, что существует потенциально много возможных решений для линии этой длины, если мы уверены, что для положительного m (треугольник направлен вверх) она будет соответствовать левому нижнему углу прямоугольника, а для отрицательного m (треугольник направлен вниз) ) он поместится в правом верхнем углу.

Допустим, ваш прямоугольник состоит из 4 значений minX, minY, maxX, maxY

если m положительно, линия пересекается с minX minY и выходит из прямоугольника с

[minX + scale, minY + (m * scale)]

и если m отрицательно, линия пересекается в maxX maxY и выходит из прямоугольника в

[maX - scale, maxY + (m * scale)] (noting that m is negative)

Теперь все, что вам нужно, это наклон 0, что тривиально.