Рассмотрим два выпуклых многоугольника A и B. Многоугольник B полностью лежит внутри многоугольника A. Я пытаюсь найти самый длинный отрезок прямой (с фиксированным наклоном), такой что:
- Один конец отрезка лежит на границе многоугольника B, а другой конец отрезка лежит на границе многоугольника A.
Может ли кто-нибудь помочь мне с алгоритмом, чтобы найти эту длину?
Далее, может ли это быть распространено на следующее:
- Предположим, у вас есть два линейных сегмента с разными наклонами (оба фиксированные), так что они имеют одну и ту же конечную точку на многоугольнике B или внутри него, а другие конечные точки (будут разными для двух линий) на границе A. Как мне максимизировать сумма их длин?
- Многогранники/многоугольники более высоких измерений?
Ответ 1 · Andreas
Во-первых, вам нужно понять, что соединительный отрезок линии никогда не будет заканчиваться посередине ребер A и B.
Если бы это было так, и ребра A и B не параллельны, то перемещение в ту или иную сторону всегда приводило бы к более длинному отрезку соединительной линии. Если ребра A и B параллельны, вы можете двигаться в обоих направлениях, чтобы найти соединительные сегменты равной длины, пока не достигнете вершины, поэтому всегда будет решение максимальной длины, которое заканчивается вершиной.
Это сокращает список потенциальных соединительных отрезков до отрезков, заканчивающихся вершиной.
Итак, для каждой вершины A найдите (до) двух точек на линии заданного наклона, которая пересекает B, и выберите самую дальнюю точку (если есть). Это сегмент линии-кандидата.
Сделайте то же самое для каждой вершины B, найдя точку, где линия пересекает A.
Теперь выберите самый длинный отрезок линии из всех этих кандидатов.
Обратите внимание, что описанное выше будет работать и для вогнутых многоугольников. Просто будет более двух точек, в которых линия из вершины одного многоугольника пересекает ребро другого многоугольника.
Ответ 2 · рейтинг 1 · David Eisenstat
Поверните полигоны так, чтобы наклон был горизонтальным (на практике это делается неявно с помощью векторной математики). Искомый отрезок имеет конец в вершине A или в вершине B (иначе мы могли бы удлинить отрезок, сместив его положение вверх или вниз).
Получите левую оболочку A и правую оболочку B. Мы имитируем линию, проходящую снизу вверх, выполняя отсортированное слияние вершин A с вершинами B. В каждой вершине определяем длину по горизонтали, которая будет определена уравнением для отрезка, соединяющего предыдущую вершину на этой оболочке со следующей.
