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

Question

Рассмотрим два выпуклых многоугольника A и B. Многоугольник B лежит полностью внутри многоугольника A. Я пытаюсь найти самый длинный отрезок (с фиксированным наклоном), такой что:

• Один конецотрезок линии лежит на границе многоугольника B, а другой конец отрезка линии лежит на границе многоугольника A.

Может кто-нибудь помочь мне с алгоритмом, чтобы найти эту длину?

Кроме того, это может быть расширено до следующего:

• Предположим, у вас есть два отрезка с разными наклонами (оба фиксированных наклона), так что они имеют одинаковую конечную точку на или внутри многоугольника B иих другие конечные точки (были бы разными для двух линий) на границе A. Как бы я максимизировал сумму их длин?
• Многогранники / многоугольники более высоких измерений?

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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