Самая длинная прямая линия в выпуклом многоугольнике с фиксированным наклоном и ограниченными конечными точками

Во-первых, вам нужно понять, что соединительный отрезок линии никогда не будет заканчиваться посередине ребер A и B.

Если бы это было так, и ребра A и B не параллельны, то перемещение в ту или иную сторону всегда приводило бы к более длинному отрезку соединительной линии. Если ребра A и B параллельны, вы можете двигаться в обоих направлениях, чтобы найти соединительные сегменты равной длины, пока не достигнете вершины, поэтому всегда будет решение максимальной длины, которое заканчивается вершиной.

Это сокращает список потенциальных соединительных отрезков до отрезков, заканчивающихся вершиной.

Итак, для каждой вершины A найдите (до) двух точек на линии заданного наклона, которая пересекает B, и выберите самую дальнюю точку (если есть). Это сегмент линии-кандидата.

Сделайте то же самое для каждой вершины B, найдя точку, где линия пересекает A.

Теперь выберите самый длинный отрезок линии из всех этих кандидатов.

Обратите внимание, что описанное выше будет работать и для вогнутых многоугольников. Просто будет более двух точек, в которых линия из вершины одного многоугольника пересекает ребро другого многоугольника.

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

Получите левую оболочку A и правую оболочку B. Мы имитируем линию, проходящую снизу вверх, выполняя отсортированное слияние вершин A с вершинами B. В каждой вершине определяем длину по горизонтали, которая будет определена уравнением для отрезка, соединяющего предыдущую вершину на этой оболочке со следующей.